| Title:
|
Connected domination critical graphs with respect to relative complements (English) |
| Author:
|
Chen, Xue-Gang |
| Author:
|
Sun, Liang |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
56 |
| Issue:
|
2 |
| Year:
|
2006 |
| Pages:
|
417-423 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
connected domination number |
| Keyword:
|
connected domination critical graph relative to $K_{s,s}$ tree. |
| MSC:
|
05C35 |
| MSC:
|
05C69 |
| idZBL:
|
Zbl 1164.05417 |
| idMR:
|
MR2291746 |
| . |
| Date available:
|
2009-09-24T11:34:16Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/128076 |
| . |
| Reference:
|
[1] E. Cockaye: Variations on the Domination Number of a Graph.Lecture at the University of Natal, 1988. |
| Reference:
|
[2] W. Goddard, M. A. Henning and H. C. Swart: Some Nordhaus-Gaddum-type results.J. Graph Theory 16 (1992), 221–231. MR 1168581, 10.1002/jgt.3190160305 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[7] S. T. Hedetniemi: Renu Laskar, Connected domination in graphs.Graph Theory and Combinatorics (1984), 209–217. MR 0777177 |
| Reference:
|
[8] E. Sampathkumar and H. B. Walikar: The connected domination number of a graph.Math. Phys. Sci. 13 (1979), 607–613. MR 0575817 |
| . |
