Edgeless graphs are the only universal fixers

Kirsti Wash

Displaying similar documents to “Edgeless graphs are the only universal fixers”

A bound on the $k$ -domination number of a graph

Lutz Volkmann (2010)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a graph with vertex set $V (G)$ , and let $k \geq 1$ be an integer. A subset $D \subseteq V (G)$ is called a if every vertex $v \in V (G) - D$ has at least $k$ neighbors in $D$ . The $k$ -domination number $γ_{k} (G)$ of $G$ is the minimum cardinality of a $k$ -dominating set in $G$ . If $G$ is a graph with minimum degree $δ (G) \geq k + 1$ , then we prove that $γ_{k + 1} (G) \leq \frac{| V (G) | + γ_{k} (G)}{2} .$ In addition, we present a characterization of a special class of graphs attaining equality in this inequality.

On domination number of 4-regular graphs

Hailong Liu, Liang Sun (2004)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a simple graph. A subset $S \subseteq V$ is a dominating set of $G$ , if for any vertex $v \in V - S$ there exists a vertex $u \in S$ such that $u v \in E (G)$ . The domination number, denoted by $γ (G)$ , is the minimum cardinality of a dominating set. In this paper we prove that if $G$ is a 4-regular graph with order $n$ , then $γ (G) \leq \frac{4}{11} n$ .

On total restrained domination in graphs

De-xiang Ma, Xue-Gang Chen, Liang Sun (2005)

Czechoslovak Mathematical Journal

Similarity:

In this paper we initiate the study of total restrained domination in graphs. Let $G = (V, E)$ be a graph. A total restrained dominating set is a set $S \subseteq V$ where every vertex in $V - S$ is adjacent to a vertex in $S$ as well as to another vertex in $V - S$ , and every vertex in $S$ is adjacent to another vertex in $S$ . The total restrained domination number of $G$ , denoted by $γ_{r}^{t} (G)$ , is the smallest cardinality of a total restrained dominating set of $G$ . First, some exact values and sharp bounds for $γ_{r}^{t} (G)$ are given in Section 2....

Displaying similar documents to “Edgeless graphs are the only universal fixers”

A bound on the k -domination number of a graph

On domination number of 4-regular graphs

On total restrained domination in graphs

A bound on the $k$ -domination number of a graph