Gamma graphs of some special classes of trees. (English) Zbl 1367.05154
Summary: A set \(S \subset V\) is a dominating set of a graph \(G = (V, E)\) if every vertex \(\nu \in V\) which does not belong to \(S\) has a neighbour in \(S\). The domination number \(\gamma (G)\) of the graph \(G\) is the minimum cardinality of a dominating set in \(G\). A dominating set \(S\) is a \(\gamma\)-set in \(G\) if \(| S | = \gamma (G)\).
Some graphs have exponentially many \(\gamma\)-sets, hence it is worth to ask a question if a \(\gamma\)-set can be obtained by some transformations from another \(\gamma\)-set. The study of gamma graphs is an answer to this reconfiguration problem. We give a partial answer to the question which graphs are gamma graphs of trees. In the second section gamma graphs \(\gamma\).\(T\) of trees with diameter not greater than five will be presented. It will be shown that hypercubes \(Q_k\) are among \(\gamma\).\(T\) graphs. In the third section, \(\gamma\).\(T\) graphs of certain trees with three pendant vertices will be analysed. Additionally, some observations on the diameter of gamma graphs will be presented in response to an open question published by G. H. Fricke et al. [Discuss. Math., Graph Theory 31, No. 3, 517–531 (2011; Zbl 1229.05219)], if \(\mathrm{diam}(T (\gamma)) = O (n)\)?
Some graphs have exponentially many \(\gamma\)-sets, hence it is worth to ask a question if a \(\gamma\)-set can be obtained by some transformations from another \(\gamma\)-set. The study of gamma graphs is an answer to this reconfiguration problem. We give a partial answer to the question which graphs are gamma graphs of trees. In the second section gamma graphs \(\gamma\).\(T\) of trees with diameter not greater than five will be presented. It will be shown that hypercubes \(Q_k\) are among \(\gamma\).\(T\) graphs. In the third section, \(\gamma\).\(T\) graphs of certain trees with three pendant vertices will be analysed. Additionally, some observations on the diameter of gamma graphs will be presented in response to an open question published by G. H. Fricke et al. [Discuss. Math., Graph Theory 31, No. 3, 517–531 (2011; Zbl 1229.05219)], if \(\mathrm{diam}(T (\gamma)) = O (n)\)?
MSC:
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
Citations:
Zbl 1229.05219References:
| [1] | Diestel R., Graph theory, Springer-Verlag, Heidelberg, 2005.; · Zbl 1074.05001 |
| [2] | Fricke G.H., Hedetniemi S.M., Hedetniemi S.T., Hutson K.R., γ-graphs of graphs, Discuss. Math. Graph Theory 31 (2011), 517-531.; · Zbl 1229.05219 |
| [3] | Haas R., Seyffarth K., The k-dominating graph, Graphs Combin. 30 (2014), 609-617.; · Zbl 1294.05122 |
| [4] | Haynes T.W., Hedetniemi S.T., Slater P.J., Fundamentals on domination in graphs, CRC Press, New York, 1998.; · Zbl 0890.05002 |
| [5] | Lakshmanan S.A., Vijayakumar A., The gamma graph of a graph, AKCE J. Graphs Combin. 7 (2010), 53-59.; · Zbl 1223.05212 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
