Geodesic
Connected domination critical graphs with respect to relative complements
Czechoslovak Mathematical Journal, Tome 56 (2006) no. 2, pp. 417-423
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

A dominating set in a graph $G$ is a connected dominating set of $G$ if it induces a connected subgraph of $G$. The minimum number of vertices in a connected dominating set of $G$ is called the connected domination number of $G$, and is denoted by $\gamma _{c}(G)$. Let $G$ be a spanning subgraph of $K_{s,s}$ and let $H$ be the complement of $G$ relative to $K_{s,s}$; that is, $K_{s,s}=G\oplus H$ is a factorization of $K_{s,s}$. The graph $G$ is $k$-$\gamma _{c}$-critical relative to $K_{s,s}$ if $\gamma _{c}(G)=k$ and $\gamma _{c}(G+e)
A dominating set in a graph $G$ is a connected dominating set of $G$ if it induces a connected subgraph of $G$. The minimum number of vertices in a connected dominating set of $G$ is called the connected domination number of $G$, and is denoted by $\gamma _{c}(G)$. Let $G$ be a spanning subgraph of $K_{s,s}$ and let $H$ be the complement of $G$ relative to $K_{s,s}$; that is, $K_{s,s}=G\oplus H$ is a factorization of $K_{s,s}$. The graph $G$ is $k$-$\gamma _{c}$-critical relative to $K_{s,s}$ if $\gamma _{c}(G)=k$ and $\gamma _{c}(G+e)$ for each edge $e\in E(H)$. First, we discuss some classes of graphs whether they are $\gamma _{c}$-critical relative to $K_{s,s}$. Then we study $k$-$\gamma _{c}$-critical graphs relative to $K_{s,s}$ for small values of $k$. In particular, we characterize the $3$-$\gamma _{c}$-critical and $4$-$\gamma _{c}$-critical graphs.
Classification : 05C35, 05C69
Keywords: connected domination number; connected domination critical graph relative to $K_{s, s}$ tree. 
@article{CMJ_2006_56_2_a10,
     author = {Chen, Xue-Gang and Sun, Liang},
     title = {Connected domination critical graphs with respect to relative complements},
     journal = {Czechoslovak Mathematical Journal},
     pages = {417--423},
     year = {2006},
     volume = {56},
     number = {2},
     mrnumber = {2291746},
     zbl = {1164.05417},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2006_56_2_a10/}
}
TY  - JOUR
AU  - Chen, Xue-Gang
AU  - Sun, Liang
TI  - Connected domination critical graphs with respect to relative complements
JO  - Czechoslovak Mathematical Journal
PY  - 2006
SP  - 417
EP  - 423
VL  - 56
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/CMJ_2006_56_2_a10/
LA  - en
ID  - CMJ_2006_56_2_a10
ER  - 
%0 Journal Article
%A Chen, Xue-Gang
%A Sun, Liang
%T Connected domination critical graphs with respect to relative complements
%J Czechoslovak Mathematical Journal
%D 2006
%P 417-423
%V 56
%N 2
%U http://geodesic.mathdoc.fr/item/CMJ_2006_56_2_a10/
%G en
%F CMJ_2006_56_2_a10
Chen, Xue-Gang; Sun, Liang. Connected domination critical graphs with respect to relative complements. Czechoslovak Mathematical Journal, Tome 56 (2006) no. 2, pp. 417-423. http://geodesic.mathdoc.fr/item/CMJ_2006_56_2_a10/

[1] E. Cockaye: Variations on the Domination Number of a Graph. Lecture at the University of Natal, 1988.

[2] W. Goddard, M. A. Henning and H. C. Swart: Some Nordhaus-Gaddum-type results. J. Graph Theory 16 (1992), 221–231. | DOI | MR

[3] T. W. Haynes and M. A. Henning: Domination critical graphs with respect to relative complements. Australas J. Combin. 18 (1998), 115–126. | MR

[4] T. W. Haynes, M. A. Henning and L. C. van der Merwe: Domination and total domination critical trees with respect to relative complements. Ars Combin. 59 (2001), 117–127. | MR

[5] T. W. Haynes, M. A. Henning and L. C. van der Merwe: Total domination critical graphs with respect to relative complements. Ars Combin. 64 (2002), 169–179. | MR

[6] T. W. Haynes, C. M. Mynhardt and L. C. van der Merwe: Total domination edge critical graphs. Utilitas Math. 54 (1998), 229–240. | MR

[7] S. T. Hedetniemi: Renu Laskar, Connected domination in graphs. Graph Theory and Combinatorics (1984), 209–217. | MR

[8] E. Sampathkumar and H. B. Walikar: The connected domination number of a graph. Math. Phys. Sci. 13 (1979), 607–613. | MR