PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2004 | 24 | 3 | 539-543
Tytuł artykułu

A Gallai-type equality for the total domination number of a graph

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
We prove the following Gallai-type equality
γₜ(G) + εₜ(G) = p
for any graph G with no isolated vertex, where p is the number of vertices of G, γₜ(G) is the total domination number of G, and εₜ(G) is the maximum integer s such that there exists a spanning forest F with s the number of pendant edges of F minus the number of star components of F.
Wydawca
Rocznik
Tom
24
Numer
3
Strony
539-543
Opis fizyczny
Daty
wydano
2004
otrzymano
2003-10-09
poprawiono
2004-04-14
Twórcy
autor
  • Department of Mathematics and Statistics, The University of Melbourne, Parkville, VIC 3010, Australia
Bibliografia
  • [1] B. Bollobás, E.J. Cockayne and C.M. Mynhardt, On Generalized Minimal Domination Parameters for Paths, Discrete Math. 86 (1990) 89-97, doi: 10.1016/0012-365X(90)90352-I.
  • [2] E.J. Cockayne, S.T. Hedetniemi and R. Laskar, Gallai Theorems for Graphs, Hypergraphs and Set Systems, Discrete Math. 72 (1988) 35-47, doi: 10.1016/0012-365X(88)90192-6.
  • [3] T. Gallai, Über Extreme Punkt-und Kantenmengen, Ann. Univ. Sci. Budapest Eötvös Sect. Math. 2 (1959) 133-138.
  • [4] S.T. Hedetniemi, Hereditary Properties of Graphs, J. Combin. Theory 14 (1973) 16-27.
  • [5] S.T. Hedetniemi and R. Laskar, Connected Domination in Graphs, in: B. Bollobás ed., Graph Theory and Combinatorics (Academic Press, 1984) 209-218.
  • [6] J. Nieminen, Two Bounds for the Domination Number of a Graph, J. Inst. Math. Appl. 14 (1974) 183-187, doi: 10.1093/imamat/14.2.183.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1251
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ć.