Discussiones
Mathematicae Graph Theory 23(1) (2003)
159-162
doi: 10.7151/dmgt.1192
Igor Edmundovich Zverovich
RUTCOR, Rutgers University
640 Bartholomew Rd., Piscataway, NJ 08854 USA
e-mail: igor@rutgers.rutcor.edu
We prove that a graph is a perfect connected-dominant graph if and only if it contains no induced path P_{5} and induced cycle C_{5}.
Keywords: Connected domination, perfect connected-dominant graph.
2000 Mathematics Subject Classification: 05C69.
[1] | S. Arumugam and J.J. Paulraj, On graphs with equal domination and connected domination numbers, Discrete Math. 206 (1999) 45-49, doi: 10.1016/S0012-365X(98)00390-2. |
[2] | K. Arvind and R.C. Pandu, Connected domination and Steiner set on weighted permutation graphs, Inform. Process. Lett. 41 (1992) 215-220, doi: 10.1016/0020-0190(92)90183-V. |
[3] | H. Balakrishnan, A. Rajaram and R.C. Pandu, Connected domination and Steiner set on asteroidal triple-free graphs, Lecture Notes Math. 709 (1993) 131-141. |
[4] | C. Bo and B. Liu, Some inequalities about connected domination number, Discrete Math. 159 (1996) 241-245, doi: 10.1016/0012-365X(95)00088-E. |
[5] | J.E. Dunbar, J.W. Grossman, J.H. Hattingh, S.T. Hedetniemi and A.A. McRae, On weakly connected domination in graphs, Discrete Math. 167/168 (1997) 261-269, doi: 10.1016/S0012-365X(96)00233-6. |
[6] | D.V. Korobitsyn, On the complexity of determining the domination number in monogenic classes of graphs, Discrete Math. 2 (1990) 90-96. |
[7] | J.J. Paulrau and S. Arumugam, On connected cutfree domination in graphs, Indian J. Pure Appl. Math. 23 (1992) 643-647. |
[8] | L. Sun, Some results on connected domination of graphs, Math. Appl. 5 (1992) 29-34. |
[9] | E.S. Wolk, A note on 'The comparability graph of a tree', Proc. Amer. Math. Soc. 16 (1966) 17-20, doi: 10.1090/S0002-9939-1965-0172274-5. |
[10] | E.S. Wolk, The comparability graph of a tree, Proc. Amer. Math. Soc. 13 (1962) 789-795. |
Received 16 August 2001