Search

Start Over Subject domination number

1. A note on the domination number of a graph and its complement

Creator:
Marcu, Dănuţ
Format:
bez média and svazek
Type:
model:article and TEXT
Subject:
graphs, domination number, and graph’s complement
Language:
English
Description:
If G is a simple graph of size n without isolated vertices and G is its complement, we show that the domination numbers of G and G satisfy γ(G) + γ(G) ≤ { n − δ + 2 if γ(G) > 3, δ + 3 if γ(G) > 3, where δ is the minimum degree of vertices in G.
Rights:
http://creativecommons.org/publicdomain/mark/1.0/ and policy:public

2. An upper bound for domination number of 5-regular graphs

Creator:
Xing, Hua-Ming, Sun, Liang, and Chen, Xue-Gang
Format:
bez média and svazek
Type:
model:article and TEXT
Subject:
domination number, 5-regular graph, and upper bounds
Language:
English
Description:
Let $G=(V, E)$ be a simple graph. A subset $S\subseteq V$ is a dominating set of $G$, if for any vertex $u\in V-S$, there exists a vertex $v\in S$ such that $uv\in E$. The domination number, denoted by $\gamma (G)$, is the minimum cardinality of a dominating set. In this paper we will prove that if $G$ is a 5-regular graph, then $\gamma (G)\le {5\over 14}n$.
Rights:
http://creativecommons.org/publicdomain/mark/1.0/ and policy:public

3. Bounds concerning the alliance number

Creator:
Bullington, Grady, Eroh, Linda, and Winters, Steven J.
Format:
bez média and svazek
Type:
model:article and TEXT
Subject:
defensive alliance, global defensive alliance, and domination number
Language:
English
Description:
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 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 integers a, b, and c satisfying a ≤ c and b ≤ c, there is a graph G with a = a(G), b = γ(G), and c = γa(G). For any positive integers a, b, and c, provided a ≤ b ≤ c and c is not too much larger than a and b, there is a graph G with γ(G) = a, γa(G) = b, and γaˆ(G) = c. Given two connected graphs H1 and H2, where order(H1) ≤ order(H2), there exists a graph G with a unique minimum defensive alliance isomorphic to H1 and a unique minimum strong defensive alliance isomorphic to H2.
Rights:
http://creativecommons.org/publicdomain/mark/1.0/ and policy:public

4. Domination numbers on the Boolean function graph of a graph

Creator:
Janakiraman, T. N., Muthammai, S., and Bhanumathi, M.
Format:
bez média and svazek
Type:
model:article and TEXT
Subject:
domination number, point-set domination number, split domination number, and Boolean function graph
Language:
English
Description:
For any graph G, let V (G) and E(G) denote the vertex set and the edge set of G respectively. The Boolean function graph B(G, L(G), NINC) of G is a graph with vertex set V (G) ∪ E(G) and two vertices in B(G, L(G), NINC) are adjacent if and only if they correspond to two adjacent vertices of G, two adjacent edges of G or to a vertex and an edge not incident to it in G. For brevity, this graph is denoted by B1(G). In this paper, we determine domination number, independent, connected, total, cycle, point-set, restrained, split and non-split domination numbers of B1(G) and obtain bounds for the above numbers.
Rights:
http://creativecommons.org/publicdomain/mark/1.0/ and policy:public

5. Domination numbers on the complement of the Boolean function graph of a graph

Creator:
Janakiraman, T. N., Muthammai, S., and Bhanumathi, M.
Format:
bez média and svazek
Type:
model:article and TEXT
Subject:
domination number, eccentricity, radius, diameter, neighborhood, perfect matching, and Boolean function graph
Language:
English
Description:
For any graph G, let V (G) and E(G) denote the vertex set and the edge set of G respectively. The Boolean function graph B(G, L(G), NINC) of G is a graph with vertex set V (G) ∪ E(G) and two vertices in B(G, L(G), NINC) are adjacent if and only if they correspond to two adjacent vertices of G, two adjacent edges of G or to a vertex and an edge not incident to it in G. For brevity, this graph is denoted by B1(G). In this paper, we determine domination number, independent, connected, total, point-set, restrained, split and non-split domination numbers in the complement B1(G) of B1(G) and obtain bounds for the above numbers.
Rights:
http://creativecommons.org/publicdomain/mark/1.0/ and policy:public

6. Domination with respect to nondegenerate properties: vertex and edge removal

Creator:
Samodivkin, Vladimir
Format:
bez média and svazek
Type:
model:article and TEXT
Subject:
dominating set, domination number, bondage number, additive graph property, hereditary graph property, and induced-hereditary graph property
Language:
English
Description:
In this paper we present results on changing and unchanging of the domination number with respect to the nondegenerate property P, denoted by γP (G), when a graph G is modified by deleting a vertex or deleting edges. A graph G is (γP (G), k)P -critical if γP (G − S) < γP (G) for any set S ( V (G) with |S| = k. Properties of (γP , k)P -critical graphs are studied. The plus bondage number with respect to the property P, denoted b + P (G), is the cardinality of the smallest set of edges U ⊆ E(G) such that γP (G − U) > γP (G). Some known results for ordinary domination and bondage numbers are extended to γP (G) and b + P (G). Conjectures concerning b + P (G) are posed.
Rights:
http://creativecommons.org/publicdomain/mark/1.0/ and policy:public

7. Inequalities involving independence domination, $f$-domination, connected and total $f$-domination numbers

Creator:
Zhou, San Ming
Format:
bez média and svazek
Type:
model:article and TEXT
Subject:
domination number, independence domination number, $f$-domination number, and total $f$-domination number
Language:
English
Description:
Let $f$ be an integer-valued function defined on the vertex set $V(G)$ of a graph $G$. A subset $D$ of $V(G)$ is an $f$-dominating set if each vertex $x$ outside $D$ is adjacent to at least $f(x)$ vertices in $D$. The minimum number of vertices in an $f$-dominating set is defined to be the $f$-domination number, denoted by $\gamma _{f}(G)$. In a similar way one can define the connected and total $f$-domination numbers $\gamma _{c, f}(G)$ and $\gamma _{t, f}(G)$. If $f(x) = 1$ for all vertices $x$, then these are the ordinary domination number, connected domination number and total domination number of $G$, respectively. In this paper we prove some inequalities involving $\gamma _{f}(G), \gamma _{c, f}(G), \gamma _{t, f}(G)$ and the independence domination number $i(G)$. In particular, several known results are generalized.
Rights:
http://creativecommons.org/publicdomain/mark/1.0/ and policy:public

8. On domination number of 4-regular graphs

Creator:
Liu, Hailong and Sun, Liang
Format:
bez média and svazek
Type:
model:article and TEXT
Subject:
regular graph, dominating set, and domination number
Language:
English
Description:
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 $uv \in E (G)$. The domination number, denoted by $\gamma (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 $\gamma (G) \le \frac{4}{11}n$.
Rights:
http://creativecommons.org/publicdomain/mark/1.0/ and policy:public

9. Remarks on restrained domination and total restrained domination in graphs

Creator:
Zelinka, Bohdan
Format:
bez média and svazek
Type:
model:article and TEXT
Subject:
domination number, domatic number, total domination number, total domatic number, restrained domination number, restrained domatic number, total restrained domination number, and total restrained domatic number
Language:
English
Description:
The restrained domination number $\gamma ^r (G)$ and the total restrained domination number $\gamma ^r_t (G)$ of a graph $G$ were introduced recently by various authors as certain variants of the domination number $\gamma (G)$ of $(G)$. A well-known numerical invariant of a graph is the domatic number $d (G)$ which is in a certain way related (and may be called dual) to $\gamma (G)$. The paper tries to define analogous concepts also for the restrained domination and the total restrained domination and discusses the sense of such new definitions.
Rights:
http://creativecommons.org/publicdomain/mark/1.0/ and policy:public

10. Vertices contained in all minimum paired-dominating sets of a tree

Creator:
Chen, Xue-Gang
Format:
bez média and svazek
Type:
model:article and TEXT
Subject:
domination number, paired-domination number, and tree
Language:
English
Description:
A set $S$ of vertices in a graph $G$ is called a paired-dominating set if it dominates $V$ and $\langle S\rangle $ contains at least one perfect matching. We characterize the set of vertices of a tree that are contained in all minimum paired-dominating sets of the tree.
Rights:
http://creativecommons.org/publicdomain/mark/1.0/ and policy:public