Bounds On The Disjunctive Total Domination Number Of A Tree

Michael A. Henning; Viroshan Naicker

Displaying similar documents to “Bounds On The Disjunctive Total Domination Number Of A Tree”

On locating and differentiating-total domination in trees

Mustapha Chellali (2008)

Discussiones Mathematicae Graph Theory

Similarity:

A total dominating set of a graph G = (V,E) with no isolated vertex is a set S ⊆ V such that every vertex is adjacent to a vertex in S. A total dominating set S of a graph G is a locating-total dominating set if for every pair of distinct vertices u and v in V-S, N(u)∩S ≠ N(v)∩S, and S is a differentiating-total dominating set if for every pair of distinct vertices u and v in V, N[u]∩S ≠ N[v] ∩S. Let $γ ₜ^{L} (G)$ and $γ ₜ^{D} (G)$ be the minimum cardinality of a locating-total dominating set and a differentiating-total...

Weak roman domination in graphs

P. Roushini Leely Pushpam, T.N.M. Malini Mai (2011)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph and f be a function f:V → 0,1,2. A vertex u with f(u) = 0 is said to be undefended with respect to f, if it is not adjacent to a vertex with positive weight. The function f is a weak Roman dominating function (WRDF) if each vertex u with f(u) = 0 is adjacent to a vertex v with f(v) > 0 such that the function f’: V → 0,1,2 defined by f’(u) = 1, f’(v) = f(v)-1 and f’(w) = f(w) if w ∈ V-u,v, has no undefended vertex. The weight of f is $w (f) = \sum_{v \in V} f (v)$ . The weak Roman domination...

On the (2,2)-domination number of trees

You Lu, Xinmin Hou, Jun-Ming Xu (2010)

Discussiones Mathematicae Graph Theory

Similarity:

Let γ(G) and $γ_{2, 2} (G)$ denote the domination number and (2,2)-domination number of a graph G, respectively. In this paper, for any nontrivial tree T, we show that $(2 (γ (T) + 1)) / 3 \leq γ_{2, 2} (T) \leq 2 γ (T)$ . Moreover, we characterize all the trees achieving the equalities.

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

Double domination critical and stable graphs upon vertex removal

Soufiane Khelifi, Mustapha Chellali (2012)

Discussiones Mathematicae Graph Theory

Similarity:

In a graph a vertex is said to dominate itself and all its neighbors. A double dominating set of a graph G is a subset of vertices that dominates every vertex of G at least twice. The double domination number of G, denoted $γ_{\times 2} (G)$ , is the minimum cardinality among all double dominating sets of G. We consider the effects of vertex removal on the double domination number of a graph. A graph G is $γ_{\times 2}$ -vertex critical graph ( $γ_{\times 2}$ -vertex stable graph, respectively) if the removal of any vertex different...

Arbitrarily vertex decomposable caterpillars with four or five leaves

Sylwia Cichacz, Agnieszka Görlich, Antoni Marczyk, Jakub Przybyło, Mariusz Woźniak (2006)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G of order n is called arbitrarily vertex decomposable if for each sequence (a₁,...,aₖ) of positive integers such that a₁+...+aₖ = n there exists a partition (V₁,...,Vₖ) of the vertex set of G such that for each i ∈ 1,...,k, $V_{i}$ induces a connected subgraph of G on $a_{i}$ vertices. D. Barth and H. Fournier showed that if a tree T is arbitrarily vertex decomposable, then T has maximum degree at most 4. In this paper we give a complete characterization of arbitrarily vertex decomposable...

Full domination in graphs

Robert C. Brigham, Gary Chartrand, Ronald D. Dutton, Ping Zhang (2001)

Discussiones Mathematicae Graph Theory

Similarity:

For each vertex v in a graph G, let there be associated a subgraph $H_{v}$ of G. The vertex v is said to dominate $H_{v}$ as well as dominate each vertex and edge of $H_{v}$ . A set S of vertices of G is called a full dominating set if every vertex of G is dominated by some vertex of S, as is every edge of G. The minimum cardinality of a full dominating set of G is its full domination number $γ_{F H} (G)$ . A full dominating set of G of cardinality $γ_{F H} (G)$ is called a $γ_{F H}$ -set of G. We study three types of full domination in...

A remark on branch weights in countable trees

Bohdan Zelinka (2004)

Mathematica Bohemica

Similarity:

Let $T$ be a tree, let $u$ be its vertex. The branch weight $b (u)$ of $u$ is the maximum number of vertices of a branch of $T$ at $u$ . The set of vertices $u$ of $T$ in which $b (u)$ attains its minimum is the branch weight centroid $B (T)$ of $T$ . For finite trees the present author proved that $B (T)$ coincides with the median of $T$ , therefore it consists of one vertex or of two adjacent vertices. In this paper we show that for infinite countable trees the situation is quite different.

Coalescing Fiedler and core vertices

Didar A. Ali, John Baptist Gauci, Irene Sciriha, Khidir R. Sharaf (2016)

Czechoslovak Mathematical Journal

Similarity:

The nullity of a graph $G$ is the multiplicity of zero as an eigenvalue in the spectrum of its adjacency matrix. From the interlacing theorem, derived from Cauchy’s inequalities for matrices, a vertex of a graph can be a core vertex if, on deleting the vertex, the nullity decreases, or a Fiedler vertex, otherwise. We adopt a graph theoretical approach to determine conditions required for the identification of a pair of prescribed types of root vertices of two graphs to form a cut-vertex...

Turán's problem and Ramsey numbers for trees

Zhi-Hong Sun, Lin-Lin Wang, Yi-Li Wu (2015)

Colloquium Mathematicae

Similarity:

Let T¹ₙ = (V,E₁) and T²ₙ = (V,E₂) be the trees on n vertices with $V = v ₀, v ₁, . . ., v_{n - 1}$ , $E ₁ = v ₀ v ₁, . . ., v ₀ v_{n - 3}, v_{n - 4} v_{n - 2}, v_{n - 3} v_{n - 1}$ and $E ₂ = v ₀ v ₁, . . ., v ₀ v_{n - 3}, v_{n - 3} v_{n - 2}, v_{n - 3} v_{n - 1}$ . For p ≥ n ≥ 5 we obtain explicit formulas for ex(p;T¹ₙ) and ex(p;T²ₙ), where ex(p;L) denotes the maximal number of edges in a graph of order p not containing L as a subgraph. Let r(G₁,G₂) be the Ramsey number of the two graphs G₁ and G₂. We also obtain some explicit formulas for $r (T ₘ, T ₙ^{i})$ , where i ∈ 1,2 and Tₘ is a tree on m vertices with Δ(Tₘ) ≤ m - 3.

Closure for spanning trees and distant area

Jun Fujisawa, Akira Saito, Ingo Schiermeyer (2011)

Discussiones Mathematicae Graph Theory

Similarity:

A k-ended tree is a tree with at most k endvertices. Broersma and Tuinstra [3] have proved that for k ≥ 2 and for a pair of nonadjacent vertices u, v in a graph G of order n with $d e g_{G} u + d e g_{G} v \geq n - 1$ , G has a spanning k-ended tree if and only if G+uv has a spanning k-ended tree. The distant area for u and v is the subgraph induced by the set of vertices that are not adjacent with u or v. We investigate the relationship between the condition on $d e g_{G} u + d e g_{G} v$ and the structure of the distant area for u and v. We prove...

Characterization of $n$ -vertex graphs with metric dimension $n - 3$

Mohsen Jannesari, Behnaz Omoomi (2014)

Mathematica Bohemica

Similarity:

For an ordered set $W = {w_{1}, w_{2}, ..., w_{k}}$ of vertices and a vertex $v$ in a connected graph $G$ , the ordered $k$ -vector $r (v | W) : = (d (v, w_{1}), d (v, w_{2}), ..., d (v, w_{k}))$ is called the metric representation of $v$ with respect to $W$ , where $d (x, y)$ is the distance between vertices $x$ and $y$ . A set $W$ is called a resolving set for $G$ if distinct vertices of $G$ have distinct representations with respect to $W$ . The minimum cardinality of a resolving set for $G$ is its metric dimension. In this paper, we characterize all graphs of order $n$ with metric dimension $n - 3$ .

On double domination in graphs

Jochen Harant, Michael A. Henning (2005)

Discussiones Mathematicae Graph Theory

Similarity:

In a graph G, a vertex dominates itself and its neighbors. A subset S ⊆ V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number $γ_{\times 2} (G)$ . A function f(p) is defined, and it is shown that $γ_{\times 2} (G) = m i n f (p)$ , where the minimum is taken over the n-dimensional cube $C ⁿ = p = (p ₁, . . ., p ₙ) | p_{i} \in I R, 0 \leq p_{i} \leq 1, i = 1, . . ., n$ . Using this result, it is then shown that if G has order n with minimum degree δ and average degree d, then $γ_{\times 2} (G) \leq ((l n (1 + d) + l n δ + 1) / δ) n$ .

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

San Ming Zhou (2000)

Czechoslovak Mathematical Journal

Similarity:

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 $γ_{f} (G)$ . In a similar way one can define the connected and total $f$ -domination numbers $γ_{c, f} (G)$ and $γ_{t, f} (G)$ . If $f (x) = 1$ for all vertices $x$ , then these are the ordinary domination number, connected domination number and total...