Bounds on the Locating Roman Domination Number in Trees

Nader Jafari Rad; Hadi Rahbani

Displaying similar documents to “Bounds on the Locating Roman Domination Number in Trees”

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

Bounds On The Disjunctive Total Domination Number Of A Tree

Michael A. Henning, Viroshan Naicker (2016)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph with no isolated vertex. In this paper, we study a parameter that is a relaxation of arguably the most important domination parameter, namely the total domination number, γt(G). A set S of vertices in G is a disjunctive total dominating set of G if every vertex is adjacent to a vertex of S or has at least two vertices in S at distance 2 from it. The disjunctive total domination number, [...] γtd(G) $γ_{t}^{d} (G)$ , is the minimum cardinality of such a set. We observe that [...] γtd(G)≤γt(G)...

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.

Minimum degree, leaf number and traceability

Simon Mukwembi (2013)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a finite connected graph with minimum degree $δ$ . The leaf number $L (G)$ of $G$ is defined as the maximum number of leaf vertices contained in a spanning tree of $G$ . We prove that if $δ \geq \frac{1}{2} (L (G) + 1)$ , then $G$ is 2-connected. Further, we deduce, for graphs of girth greater than 4, that if $δ \geq \frac{1}{2} (L (G) + 1)$ , then $G$ contains a spanning path. This provides a partial solution to a conjecture of the computer program Graffiti.pc [DeLaVi na and Waller, Spanning trees with many leaves and average distance, Electron. J. Combin....

On $k$ -pairable graphs from trees

Zhongyuan Che (2007)

Czechoslovak Mathematical Journal

Similarity:

The concept of the $k$ -pairable graphs was introduced by Zhibo Chen (On $k$ -pairable graphs, Discrete Mathematics 287 (2004), 11–15) as an extension of hypercubes and graphs with an antipodal isomorphism. In the same paper, Chen also introduced a new graph parameter $p (G)$ , called the pair length of a graph $G$ , as the maximum $k$ such that $G$ is $k$ -pairable and $p (G) = 0$ if $G$ is not $k$ -pairable for any positive integer $k$ . In this paper, we answer the two open questions raised by Chen in the case that the graphs...

Spanning caterpillars with bounded diameter

Ralph Faudree, Ronald Gould, Michael Jacobson, Linda Lesniak (1995)

Discussiones Mathematicae Graph Theory

Similarity:

A caterpillar is a tree with the property that the vertices of degree at least 2 induce a path. We show that for every graph G of order n, either G or G̅ has a spanning caterpillar of diameter at most 2 log n. Furthermore, we show that if G is a graph of diameter 2 (diameter 3), then G contains a spanning caterpillar of diameter at most $c n^{3 / 4}$ (at most n).

A characterization of roman trees

Michael A. Henning (2002)

Discussiones Mathematicae Graph Theory

Similarity:

A Roman dominating function (RDF) on a graph G = (V,E) is a function f: V → 0,1,2 satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of f is $w (f) = \sum_{v \in V} f (v)$ . The Roman domination number is the minimum weight of an RDF in G. It is known that for every graph G, the Roman domination number of G is bounded above by twice its domination number. Graphs which have Roman domination number equal to twice their domination number...

Trees with unique minimum total dominating sets

Teresa W. Haynes, Michael A. Henning (2002)

Discussiones Mathematicae Graph Theory

Similarity:

A set S of vertices of a graph G is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. We provide three equivalent conditions for a tree to have a unique minimum total dominating set and give a constructive characterization of such trees.

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

Xue-Gang Chen (2007)

Czechoslovak Mathematical Journal

Similarity:

A set $S$ of vertices in a graph $G$ is called a paired-dominating set if it dominates $V$ and $〈 S 〉$ 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.

On the dominator colorings in trees

Houcine Boumediene Merouane, Mustapha Chellali (2012)

Discussiones Mathematicae Graph Theory

Similarity:

In a graph G, a vertex is said to dominate itself and all its neighbors. A dominating set of a graph G is a subset of vertices that dominates every vertex of G. The domination number γ(G) is the minimum cardinality of a dominating set of G. A proper coloring of a graph G is a function from the set of vertices of the graph to a set of colors such that any two adjacent vertices have different colors. A dominator coloring of a graph G is a proper coloring such that every vertex of V dominates...