PL EN


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

Graphs without induced P₅ and C₅

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
Zverovich [Discuss. Math. Graph Theory 23 (2003), 159-162.] has proved that the domination number and connected domination number are equal on all connected graphs without induced P₅ and C₅. Here we show (with an independent proof) that the following stronger result is also valid: Every P₅-free and C₅-free connected graph contains a minimum-size dominating set that induces a complete subgraph.
Wydawca
Rocznik
Tom
24
Numer
3
Strony
503-507
Opis fizyczny
Daty
wydano
2004
otrzymano
2003-07-21
poprawiono
2004-02-05
Twórcy
autor
  • Computer and Automation Institute, Hungarian Academy of Sciences, 1111 Budapest, Kende u. 13-17, Hungary
autor
  • Computer and Automation Institute, Hungarian Academy of Sciences, 1111 Budapest, Kende u. 13-17, Hungary
Bibliografia
  • [1] G. Bacsó and Zs. Tuza, Dominating cliques in P₅-free graphs, Periodica Math. Hungar. 21 (1990) 303-308, doi: 10.1007/BF02352694.
  • [2] G. Bacsó and Zs. Tuza, Structural domination of graphs, Ars Combinatoria 63 (2002) 235-256.
  • [3] F.R.K. Chung, A. Gyárfás, W.T. Trotter and Zs. Tuza, The maximum number of edges in 2K₂-free graphs of bounded degree, Discrete Math. 81 (1990) 129-135, doi: 10.1016/0012-365X(90)90144-7.
  • [4] M.B. Cozzens and L.L. Kelleher, Dominating cliques in graphs, Discrete Math. 86 (1990) 101-116, doi: 10.1016/0012-365X(90)90353-J.
  • [5] W. Goddard and M.A. Henning, Total domination perfect graphs, to appear in Bull. ICA.
  • [6] I.E. Zverovich, Perfect connected-dominant graphs, Discuss. Math. Graph Theory 23 (2003) 159-162, doi: 10.7151/dmgt.1192.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1248
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ć.