Connected domination critical graphs with respect to relative complements

Title:

Connected domination critical graphs with respect to relative complements

Creator:

Chen, Xue-Gang and Sun, Liang

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:e47a1edc-42a1-43a9-9189-f0f5c1c97473
uuid:e47a1edc-42a1-43a9-9189-f0f5c1c97473

Subject:

connected domination number and connected domination critical graph relative to $K_{s,s}$ tree

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

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.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

417-423

Source:

Czechoslovak Mathematical Journal | 2006 Volume:56 | Number:2

Harvested from:

CDK

Metadata only:

false