PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2015 | 29 | 1 | 25-34
Tytuł artykułu

Gamma Graphs Of Some Special Classes Of Trees

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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)?
Słowa kluczowe
Wydawca
Rocznik
Tom
29
Numer
1
Strony
25-34
Opis fizyczny
Daty
wydano
2015-09-01
otrzymano
2015-05-02
poprawiono
2015-06-04
online
2015-09-30
Twórcy
autor
  • Institute of Mathematics, University of Silesia, Bankowa 14 40-007 Katowice, Poland, anna.bien@us.edu.pl
Bibliografia
  • [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.
  • [3] Haas R., Seyffarth K., The k-dominating graph, Graphs Combin. 30 (2014), 609–617.[Crossref]
  • [4] Haynes T.W., Hedetniemi S.T., Slater P.J., Fundamentals on domination in graphs, CRC Press, New York, 1998.
  • [5] Lakshmanan S.A., Vijayakumar A., The gamma graph of a graph, AKCE J. Graphs Combin. 7 (2010), 53–59.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_1515_amsil-2015-0003
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.