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....

Bounds concerning the alliance number

Grady Bullington, Linda Eroh, Steven J. Winters (2009)

Mathematica Bohemica

Similarity:

P. Kristiansen, S. M. Hedetniemi, and S. T. Hedetniemi, in Alliances in graphs, J. Combin. Math. Combin. Comput. 48 (2004), 157–177, and T. W. Haynes, S. T. Hedetniemi, and M. A. Henning, in Global defensive alliances in graphs, Electron. J. Combin. 10 (2003), introduced the defensive alliance number $a (G)$ , strong defensive alliance number $\hat{a} (G)$ , and global defensive alliance number $γ_{a} (G)$ . In this paper, we consider relationships between these parameters and the domination number $γ (G)$ . For any positive...

Minus total domination in graphs

Hua Ming Xing, Hai-Long Liu (2009)

Czechoslovak Mathematical Journal

Similarity:

A three-valued function $f V \to {- 1, 0, 1}$ defined on the vertices of a graph $G = (V, E)$ is a minus total dominating function (MTDF) if the sum of its function values over any open neighborhood is at least one. That is, for every $v \in V$ , $f (N (v)) \geq 1$ , where $N (v)$ consists of every vertex adjacent to $v$ . The weight of an MTDF is $f (V) = \sum f (v)$ , over all vertices $v \in V$ . The minus total domination number of a graph $G$ , denoted $γ_{t}^{-} (G)$ , equals the minimum weight of an MTDF of $G$ . In this paper, we discuss some properties of minus total domination on a graph...

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

Bounds concerning the alliance number

Minus total domination in graphs

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