Domination in partitioned graphs

Zsolt Tuza; Preben Dahl Vestergaard

Displaying similar documents to “Domination in partitioned graphs”

Distance in stratified graphs

Gary Chartrand, Lisa Hansen, Reza Rashidi, Naveed Sherwani (2000)

Czechoslovak Mathematical Journal

Similarity:

A graph $G$ is stratified if its vertex set is partitioned into classes, called strata. If there are $k$ strata, then $G$ is $k$ -stratified. These graphs were introduced to study problems in VLSI design. The strata in a stratified graph are also referred to as color classes. For a color $X$ in a stratified graph $G$ , the $X$ -eccentricity $e_{X} (v)$ of a vertex $v$ of $G$ is the distance between $v$ and an $X$ -colored vertex furthest from $v$ . The minimum $X$ -eccentricity among the vertices of $G$ is the $X$ -radius ${r a d}_{X} G$ of $G$ ...

Signed total domination number of a graph

Bohdan Zelinka (2001)

Czechoslovak Mathematical Journal

Similarity:

The signed total domination number of a graph is a certain variant of the domination number. If $v$ is a vertex of a graph $G$ , then $N (v)$ is its oper neighbourhood, i.e. the set of all vertices adjacent to $v$ in $G$ . A mapping $f : V (G) \to {- 1, 1}$ , where $V (G)$ is the vertex set of $G$ , is called a signed total dominating function (STDF) on $G$ , if $\sum_{x \in N (v)} f (x) \geq 1$ for each $v \in V (G)$ . The minimum of values $\sum_{x \in V (G)} f (x)$ , taken over all STDF’s of $G$ , is called the signed total domination number of $G$ and denoted by $γ_{s t} (G)$ . A theorem stating lower bounds for $γ_{s t} (G)$ is...

Restrained domination in unicyclic graphs

Johannes H. Hattingh, Ernst J. Joubert, Marc Loizeaux, Andrew R. Plummer, Lucas van der Merwe (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The restrained domination number of G, denoted by $γ_{r} (G)$ , is the minimum cardinality of a restrained dominating set of G. A unicyclic graph is a connected graph that contains precisely one cycle. We show that if U is a unicyclic graph of order n, then $γ_{r} (U) \geq ⎡ n / 3 ⎤$ , and provide a characterization of graphs achieving this bound.

Domination Subdivision Numbers

Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi, David P. Jacobs, James Knisely, Lucas C. van der Merwe (2001)

Discussiones Mathematicae Graph Theory

Similarity:

A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of V-S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the domination subdivision number $s d_{γ} (G)$ is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Arumugam conjectured that $1 \leq s d_{γ} (G) \leq 3$ for any graph G. We give a counterexample to this conjecture. On the other hand,...

Wiener index of graphs with fixed number of pendant or cut-vertices

Dinesh Pandey, Kamal Lochan Patra (2022)

Czechoslovak Mathematical Journal

Similarity:

The Wiener index of a connected graph is defined as the sum of the distances between all unordered pairs of its vertices. We characterize the graphs which extremize the Wiener index among all graphs on $n$ vertices with $k$ pendant vertices. We also characterize the graph which minimizes the Wiener index over the graphs on $n$ vertices with $s$ cut-vertices.

Matchings and total domination subdivision number in graphs with few induced 4-cycles

Odile Favaron, Hossein Karami, Rana Khoeilar, Seyed Mahmoud Sheikholeslami (2010)

Discussiones Mathematicae Graph Theory

Similarity:

A set S of vertices of a graph G = (V,E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γₜ(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number $s d_{γ ₜ (G)}$ is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. Favaron, Karami, Khoeilar and Sheikholeslami (Journal...

On the minus domination number of graphs

Hailong Liu, Liang Sun (2004)

Czechoslovak Mathematical Journal

Similarity:

Let $G = (V, E)$ be a simple graph. A $3$ -valued function $f V (G) \to {- 1, 0, 1}$ is said to be a minus dominating function if for every vertex $v \in V$ , $f (N [v]) = \sum_{u \in N [v]} f (u) \geq 1$ , where $N [v]$ is the closed neighborhood of $v$ . The weight of a minus dominating function $f$ on $G$ is $f (V) = \sum_{v \in V} f (v)$ . The minus domination number of a graph $G$ , denoted by $γ^{-} (G)$ , equals the minimum weight of a minus dominating function on $G$ . In this paper, the following two results are obtained. (1) If $G$ is a bipartite graph of order $n$ , then $γ^{-} (G) \geq 4 (\sqrt{n + 1} - 1) - n .$ (2) For any negative integer $k$ and any positive integer...