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)$ 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.
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/