PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2010 | 30 | 3 | 475-487
Tytuł artykułu

Lower bounds for the domination number

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
In this note, we prove several lower bounds on the domination number of simple connected graphs. Among these are the following: the domination number is at least two-thirds of the radius of the graph, three times the domination number is at least two more than the number of cut-vertices in the graph, and the domination number of a tree is at least as large as the minimum order of a maximal matching.
Słowa kluczowe
Wydawca
Rocznik
Tom
30
Numer
3
Strony
475-487
Opis fizyczny
Daty
wydano
2010
otrzymano
2008-04-18
poprawiono
2009-04-29
zaakceptowano
2009-10-20
Twórcy
  • University of Houston - Downtown, Houston, TX, 77002, USA
autor
  • University of Houston - Downtown, Houston, TX, 77002, USA
autor
  • University of Houston - Downtown, Houston, TX, 77002, USA
Bibliografia
  • [1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (American Elsevier Publishing, 1976).
  • [2] F. Buckley and F. Harary, Distance in Graphs (Addison-Wesley, 1990).
  • [3] M. Chellali and T. Haynes, A Note on the Total Domination Number of a Tree, J. Combin. Math. Combin. Comput. 58 (2006) 189-193.
  • [4] F. Chung, The average distance is not more than the independence number, J. Graph Theory 12 (1988) 229-235, doi: 10.1002/jgt.3190120213.
  • [5] E. Cockayne, R. Dawes and S. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211-219, doi: 10.1002/net.3230100304.
  • [6] P. Dankelmann, Average distance and the independence number, Discrete Appl. Math. 51 (1994) 73-83, doi: 10.1016/0166-218X(94)90095-7.
  • [7] P. Dankelmann, Average distance and the domination number, Discrete Appl. Math. 80 (1997) 21-35, doi: 10.1016/S0166-218X(97)00067-X.
  • [8] E. DeLaViña, Q. Liu, R. Pepper, W. Waller and D.B. West, Some Conjectures of Graffiti.pc on Total Domination, Congr. Numer. 185 (2007) 81-95.
  • [9] E. DeLaViña, R. Pepper and W. Waller, A Note on Dominating Sets and Average Distance, Discrete Math. 309 (2009) 2615-2619, doi: 10.1016/j.disc.2008.03.018.
  • [10] A. Dobrynin, R. Entringer and I. Gutman, Wiener index of trees: Theory and applications, Acta Applicandae Mathematicae 66 (2001) 211-249, doi: 10.1023/A:1010767517079.
  • [11] P. Erdös, M. Saks and V. Sós, Maximum Induced Tress in Graphs, J. Graph Theory 41 (1986) 61-79.
  • [12] S. Fajtlowicz and W. Waller, On two conjectures of Graffiti, Congr. Numer. 55 (1986) 51-56.
  • [13] S. Fajtlowicz, Written on the Wall (manuscript), Web address: http://math.uh.edu/siemion.
  • [14] S. Fajtlowicz, A Characterization of Radius-Critical Graphs, J. Graph Theory 12 (1988) 529-532, doi: 10.1002/jgt.3190120409.
  • [15] O. Favaron, M. Maheo and J-F. Sacle, Some Results on Conjectures of Graffiti - 1, Ars Combin. 29 (1990) 90-106.
  • [16] M. Garey and D. Johnson, Computers and Intractability, W.H. Freeman and Co. (New York, Bell Telephone Lab., 1979).
  • [17] P. Hansen, A. Hertz, R. Kilani, O. Marcotte and D. Schindl, Average distance and maximum induced forest, pre-print, 2007.
  • [18] T. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Decker, Inc., NY, 1998).
  • [19] T. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Decker, Inc., NY, 1998).
  • [20] M. Lemańska, Lower Bound on the Domination Number of a Tree, Discuss. Math. Graph Theory 24 (2004) 165-170, doi: 10.7151/dmgt.1222.
  • [21] L. Lovász and M.D. Plummer, Matching Theory (Acedemic Press, New York, 1986).
  • [22] D.B. West, Open problems column #23, SIAM Activity Group Newsletter in Discrete Mathematics, 1996.
  • [23] D.B. West, Introduction to Graph Theory (2nd ed.) (Prentice-Hall, NJ, 2001).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1508
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ć.