PL EN

Preferencje
Język
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo

## Discussiones Mathematicae Graph Theory

2005 | 25 | 3 | 251-259
Tytuł artykułu

### Domination and leaf density in graphs

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
The domination number γ(G) of a graph G is the minimum cardinality of a subset D of V(G) with the property that each vertex of V(G)-D is adjacent to at least one vertex of D. For a graph G with n vertices we define ε(G) to be the number of leaves in G minus the number of stems in G, and we define the leaf density ζ(G) to equal ε(G)/n. We prove that for any graph G with no isolated vertex, γ(G) ≤ n(1- ζ(G))/2 and we characterize the extremal graphs for this bound. Similar results are obtained for the total domination number and the partition domination number.
Słowa kluczowe
EN
Kategorie tematyczne
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
251-259
Opis fizyczny
Daty
wydano
2005
otrzymano
2003-05-19
poprawiono
2003-10-01
Twórcy
autor
• Department of Mathematics, Aalborg University, Fredrik Bajers Vej 7G, DK 9220 Aalborg, Denmark
Bibliografia
• [1] R.C. Brigham, J.R. Carrington and R.P. Vitray, Connected graphs with maximum total domination number, J. Combin. Math. Combin. Comput. 34 (2000) 81-95.
• [2] E.J. Cockayne, R.M. Dawes and S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211-219, doi: 10.1002/net.3230100304.
• [3] J.F. Fink, M.S. Jacobson, L.F. Kinch and J. Roberts, On graphs having domination number half their order, Period. Math. Hungar. 16 (1985) 287-293, doi: 10.1007/BF01848079.
• [4] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness (Freeman, New York, 1979).
• [5] B.L. Hartnell and P.D. Vestergaard, Partitions and domination in a graph, J. Combin. Math. Combin. Comput. 46 (2003) 113-128.
• [6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of domination in graphs (Marcel Dekker, Inc., 1998).
• [7] A.M. Henning and P.D. Vestergaard, Domination in partitioned graphs with minimum degree two (Manuscript, 2002).
• [8] O. Ore, Theory of Graphs (Amer. Math. Soc. Colloq. Publ., 1962).
• [9] C. Payan and N.H. Xuong, Domination-balanced graphs, J. Graph Theory 6 (1982) 23-32, doi: 10.1002/jgt.3190060104.
• [10] S.M. Seager, Partition dominations of graphs of minimum degree 2, Congr. Numer. 132 (1998) 85-91.
• [11] Z. Tuza and P.D. Vestergaard, Domination in partitioned graphs, Discuss. Math. Graph Theory 22 (2002) 199-210, doi: 10.7151/dmgt.1169.
Typ dokumentu
Bibliografia
Identyfikatory