Perfect connected-dominant graphs

Igor Edmundovich Zverovich

Discussiones Mathematicae Graph Theory (2003)

  • Volume: 23, Issue: 1, page 159-162
  • ISSN: 2083-5892

Abstract

top
If D is a dominating set and the induced subgraph G(D) is connected, then D is a connected dominating set. The minimum size of a connected dominating set in G is called connected domination number γ c ( G ) of G. A graph G is called a perfect connected-dominant graph if γ ( H ) = γ c ( H ) for each connected induced subgraph H of G.We prove that a graph is a perfect connected-dominant graph if and only if it contains no induced path P₅ and induced cycle C₅.

How to cite

top

Igor Edmundovich Zverovich. "Perfect connected-dominant graphs." Discussiones Mathematicae Graph Theory 23.1 (2003): 159-162. <http://eudml.org/doc/270408>.

@article{IgorEdmundovichZverovich2003,
abstract = {If D is a dominating set and the induced subgraph G(D) is connected, then D is a connected dominating set. The minimum size of a connected dominating set in G is called connected domination number $γ_c(G)$ of G. A graph G is called a perfect connected-dominant graph if $γ(H) = γ_c(H)$ for each connected induced subgraph H of G.We prove that a graph is a perfect connected-dominant graph if and only if it contains no induced path P₅ and induced cycle C₅.},
author = {Igor Edmundovich Zverovich},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Connected domination; perfect connected-dominant graph; connected domination; domination number},
language = {eng},
number = {1},
pages = {159-162},
title = {Perfect connected-dominant graphs},
url = {http://eudml.org/doc/270408},
volume = {23},
year = {2003},
}

TY - JOUR
AU - Igor Edmundovich Zverovich
TI - Perfect connected-dominant graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2003
VL - 23
IS - 1
SP - 159
EP - 162
AB - If D is a dominating set and the induced subgraph G(D) is connected, then D is a connected dominating set. The minimum size of a connected dominating set in G is called connected domination number $γ_c(G)$ of G. A graph G is called a perfect connected-dominant graph if $γ(H) = γ_c(H)$ for each connected induced subgraph H of G.We prove that a graph is a perfect connected-dominant graph if and only if it contains no induced path P₅ and induced cycle C₅.
LA - eng
KW - Connected domination; perfect connected-dominant graph; connected domination; domination number
UR - http://eudml.org/doc/270408
ER -

References

top
  1. [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. Zbl0933.05114
  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. [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. [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. Zbl0859.05053
  5. [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. Zbl0871.05037
  6. [6] D.V. Korobitsyn, On the complexity of determining the domination number in monogenic classes of graphs, Discrete Math. 2 (1990) 90-96. Zbl0729.05047
  7. [7] J.J. Paulrau and S. Arumugam, On connected cutfree domination in graphs, Indian J. Pure Appl. Math. 23 (1992) 643-647. Zbl0772.05054
  8. [8] L. Sun, Some results on connected domination of graphs, Math. Appl. 5 (1992) 29-34. Zbl0890.05039
  9. [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. Zbl0137.18105
  10. [10] E.S. Wolk, The comparability graph of a tree, Proc. Amer. Math. Soc. 13 (1962) 789-795. Zbl0109.16402

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.