Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
connected domination number; connected domination critical graph relative to $K_{s,s}$ tree.
connected domination number; connected domination critical graph relative to $K_{s,s}$ tree.
Summary:
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)<k$ 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.
References:
[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 10.1002/jgt.3190160305 | MR 1168581
[3] T. W. Haynes and M. A. Henning: Domination critical graphs with respect to relative complements. Australas J. Combin. 18 (1998), 115–126. MR 1658309
[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 1832203
[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 1914205
[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 1658130
[7] S. T. Hedetniemi: Renu Laskar, Connected domination in graphs. Graph Theory and Combinatorics (1984), 209–217. MR 0777177
[8] E. Sampathkumar and H. B. Walikar: The connected domination number of a graph. Math. Phys. Sci. 13 (1979), 607–613. MR 0575817
Search
Partner of
