Gamma Graphs Of Some Special Classes Of Trees
Annales Mathematicae Silesianae (2015)
- Volume: 29, Issue: 1, page 25-34
- ISSN: 0860-2107
Access Full Article
top
Abstract
topHow to cite
topAnna Bień. "Gamma Graphs Of Some Special Classes Of Trees." Annales Mathematicae Silesianae 29.1 (2015): 25-34. <http://eudml.org/doc/276902>.
@article{AnnaBień2015,
abstract = {A set S ⊂ V is a dominating set of a graph G = (V, E) if every vertex υ ∈ V which does not belong to S has a neighbour in S. The domination number γ(G) of the graph G is the minimum cardinality of a dominating set in G. A dominating set S is a γ-set in G if |S| = γ(G). Some graphs have exponentially many γ-sets, hence it is worth to ask a question if a γ-set can be obtained by some transformations from another γ-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 γ.T of trees with diameter not greater than five will be presented. It will be shown that hypercubes Qk are among γ.T graphs. In the third section γ.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 Fricke et al., if diam(T (γ)) = O(n)?},
author = {Anna Bień},
journal = {Annales Mathematicae Silesianae},
keywords = {dominating set; gamma graph},
language = {eng},
number = {1},
pages = {25-34},
title = {Gamma Graphs Of Some Special Classes Of Trees},
url = {http://eudml.org/doc/276902},
volume = {29},
year = {2015},
}
TY - JOUR
AU - Anna Bień
TI - Gamma Graphs Of Some Special Classes Of Trees
JO - Annales Mathematicae Silesianae
PY - 2015
VL - 29
IS - 1
SP - 25
EP - 34
AB - A set S ⊂ V is a dominating set of a graph G = (V, E) if every vertex υ ∈ V which does not belong to S has a neighbour in S. The domination number γ(G) of the graph G is the minimum cardinality of a dominating set in G. A dominating set S is a γ-set in G if |S| = γ(G). Some graphs have exponentially many γ-sets, hence it is worth to ask a question if a γ-set can be obtained by some transformations from another γ-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 γ.T of trees with diameter not greater than five will be presented. It will be shown that hypercubes Qk are among γ.T graphs. In the third section γ.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 Fricke et al., if diam(T (γ)) = O(n)?
LA - eng
KW - dominating set; gamma graph
UR - http://eudml.org/doc/276902
ER -
References
top- [1] Diestel R., Graph theory, Springer-Verlag, Heidelberg, 2005.
- [2] Fricke G.H., Hedetniemi S.M., Hedetniemi S.T., Hutson K.R., γ-graphs of graphs, Discuss. Math. Graph Theory 31 (2011), 517–531. Zbl1229.05219
- [3] Haas R., Seyffarth K., The k-dominating graph, Graphs Combin. 30 (2014), 609–617.[Crossref] Zbl1294.05122
- [4] Haynes T.W., Hedetniemi S.T., Slater P.J., Fundamentals on domination in graphs, CRC Press, New York, 1998. Zbl0890.05002
- [5] Lakshmanan S.A., Vijayakumar A., The gamma graph of a graph, AKCE J. Graphs Combin. 7 (2010), 53–59. Zbl1223.05212
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.