Connected domination critical graphs with respect to relative complements

Chen, Xue-Gang ; Sun, Liang

Czechoslovak Mathematical Journal, Tome 56 (2006) no. 2, pp. 417-423.

Résumé

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.

Détail

Classification : 05C35, 05C69
Mots-clés : connected domination number; connected domination critical graph relative to $K_{s,s}$ tree.