<abstract xmlns="http://www.w3.org/1999/xhtml">A set <italic>S</italic> ⊂ <italic>V</italic> is a <italic>dominating set</italic> of a graph <italic>G</italic> = (<italic>V</italic>, <italic>E</italic>) if every vertex <italic>υ</italic> ∈ <italic>V</italic> which does not belong to <italic>S</italic> has a neighbour in <italic>S</italic>. The <italic>domination number γ</italic>(<italic>G</italic>) of the graph <italic>G</italic> is the minimum cardinality of a dominating set in <italic>G</italic>. A dominating set <italic>S</italic> is a <italic>γ-set</italic> in <italic>G</italic> if <italic>|S|</italic> = γ(<italic>G</italic>).Some graphs have exponentially many <italic>γ</italic>-sets, hence it is worth to ask a question if a <italic>γ</italic>-set can be obtained by some transformations from another <italic>γ</italic>-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 <italic>γ.T</italic> of trees with diameter not greater than five will be presented. It will be shown that hypercubes <italic>Qk</italic> are among <italic>γ.T</italic> graphs. In the third section <italic>γ.T</italic> 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(<italic>T</italic> (<italic>γ</italic>)) = <italic>O</italic>(<italic>n</italic>)?</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)?

Gamma Graphs Of Some Special Classes Of Trees

Institute of Mathematics, University of Silesia, Bankowa 14 40-007 Katowice, Poland

Annales Mathematicae Silesianae

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"Gamma Graphs Of Some Special Classes Of Trees"}

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...

Gamma Graphs Of Some Special Classes Of Trees

Publié en ligne: 30 sept. 2015

Pages: 25 - 34

Reçu: 02 mai 2015

DOI: https://doi.org/10.1515/amsil-2015-0003

© Anna Bień

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.