On locating and differentiating-total domination in trees

Mustapha Chellali

Displaying similar documents to “On locating and differentiating-total domination in trees”

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.

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

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.

On locating-domination in graphs

Mustapha Chellali, Malika Mimouni, Peter J. Slater (2010)

Discussiones Mathematicae Graph Theory

Similarity:

A set D of vertices in a graph G = (V,E) is a locating-dominating set (LDS) if for every two vertices u,v of V-D the sets N(u)∩ D and N(v)∩ D are non-empty and different. The locating-domination number $γ_{L} (G)$ is the minimum cardinality of a LDS of G, and the upper locating-domination number, $Γ_{L} (G)$ is the maximum cardinality of a minimal LDS of G. We present different bounds on $Γ_{L} (G)$ and $γ_{L} (G)$ .

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

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

On a characterization of $k$ -trees

De-Yan Zeng, Jian Hua Yin (2015)

Czechoslovak Mathematical Journal

Similarity:

A graph $G$ is a $k$ -tree if either $G$ is the complete graph on $k + 1$ vertices, or $G$ has a vertex $v$ whose neighborhood is a clique of order $k$ and the graph obtained by removing $v$ from $G$ is also a $k$ -tree. Clearly, a $k$ -tree has at least $k + 1$ vertices, and $G$ is a 1-tree (usual tree) if and only if it is a $1$ -connected graph and has no $K_{3}$ -minor. In this paper, motivated by some properties of 2-trees, we obtain a characterization of $k$ -trees as follows: if $G$ is a graph with at least $k + 1$ vertices, then $G$ is...

Domination and independence subdivision numbers of graphs

Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi (2000)

Discussiones Mathematicae Graph Theory

Similarity:

The domination subdivision number $s d_{γ} (G)$ of a graph is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number. Arumugam showed that this number is at most three for any tree, and conjectured that the upper bound of three holds for any graph. Although we do not prove this interesting conjecture, we give an upper bound for the domination subdivision number for any graph G in terms of the minimum degrees of...

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

Fires on trees

Jean Bertoin (2012)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

We consider random dynamics on the edges of a uniform Cayley tree with $n$ vertices, in which edges are either flammable, fireproof, or burnt. Every flammable edge is replaced by a fireproof edge at unit rate, while fires start at smaller rate $n^{- α}$ on each flammable edge, then propagate through the neighboring flammable edges and are only stopped at fireproof edges. A vertex is called fireproof when all its adjacent edges are fireproof. We show that as $n \to \infty$ , the terminal density of fireproof...

The vertex detour hull number of a graph

A.P. Santhakumaran, S.V. Ullas Chandran (2012)

Discussiones Mathematicae Graph Theory

Similarity:

For vertices x and y in a connected graph G, the detour distance D(x,y) is the length of a longest x - y path in G. An x - y path of length D(x,y) is an x - y detour. The closed detour interval ID[x,y] consists of x,y, and all vertices lying on some x -y detour of G; while for S ⊆ V(G), $I_{D} [S] = ⋃_{x, y \in S} I_{D} [x, y]$ . A set S of vertices is a detour convex set if $I_{D} [S] = S$ . The detour convex hull ${[S]}_{D}$ is the smallest detour convex set containing S. The detour hull number dh(G) is the minimum cardinality among subsets S of...

On the adjacent eccentric distance sum of graphs

Halina Bielak, Katarzyna Wolska (2014)

Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica

Similarity:

In this paper we show bounds for the adjacent eccentric distance sum of graphs in terms of Wiener index, maximum degree and minimum degree. We extend some earlier results of Hua and Yu [Bounds for the Adjacent Eccentric Distance Sum, International Mathematical Forum, Vol. 7 (2002) no. 26, 1289–1294]. The adjacent eccentric distance sum index of the graph $G$ is defined as $ξ^{s v} (G) = \sum_{v \in V (G)} \frac{ε (v) D (v)}{d e g (v)},$ where $ε (v)$ is the eccentricity of the vertex $v$ , $d e g (v)$ is the degree of the vertex $v$ and $D (v) = \sum_{u \in V (G)} d (u, v)$ is the sum of all distances from...

Roman bondage in graphs

Nader Jafari Rad, Lutz Volkmann (2011)

Discussiones Mathematicae Graph Theory

Similarity:

A Roman dominating function on a graph G is a function f:V(G) → 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 a Roman dominating function is the value $f (V (G)) = \sum_{u \in V (G)} f (u)$ . The Roman domination number, $γ_{R} (G)$ , of G is the minimum weight of a Roman dominating function on G. In this paper, we define the Roman bondage $b_{R} (G)$ of a graph G with maximum degree at least two to be the minimum cardinality of all sets E’ ⊆ E(G)...

On the tree structure of the power digraphs modulo $n$

Amplify Sawkmie, Madan Mohan Singh (2015)

Czechoslovak Mathematical Journal

Similarity:

For any two positive integers $n$ and $k \geq 2$ , let $G (n, k)$ be a digraph whose set of vertices is ${0, 1, ..., n - 1}$ and such that there is a directed edge from a vertex $a$ to a vertex $b$ if $a^{k} \equiv b (mod n)$ . Let $n = \prod_{i = 1}^{r} p_{i}^{e_{i}}$ be the prime factorization of $n$ . Let $P$ be the set of all primes dividing $n$ and let $P_{1}, P_{2} \subseteq P$ be such that $P_{1} \cup P_{2} = P$ and $P_{1} \cap P_{2} = \emptyset$ . A fundamental constituent of $G (n, k)$ , denoted by $G_{P_{2}}^{*} (n, k)$ , is a subdigraph of $G (n, k)$ induced on the set of vertices which are multiples of $\prod_{p_{i} \in P_{2}} p_{i}$ and are relatively prime to all primes $q \in P_{1}$ . L. Somer and M. Křížek proved that the trees attached...

Some remarks on α-domination

Franz Dahme, Dieter Rautenbach, Lutz Volkmann (2004)

Discussiones Mathematicae Graph Theory

Similarity:

Let α ∈ (0,1) and let $G = (V_{G}, E_{G}$ ) be a graph. According to Dunbar, Hoffman, Laskar and Markus [3] a set $D \subseteq V_{G}$ is called an α-dominating set of G, if $| N_{G} (u) \cap D | \geq α d_{G} (u)$ for all $u \in V_{G} ∖ D$ . We prove a series of upper bounds on the α-domination number of a graph G defined as the minimum cardinality of an α-dominating set of G.

Stronger bounds for generalized degrees and Menger path systems

R.J. Faudree, Zs. Tuza (1995)

Discussiones Mathematicae Graph Theory

Similarity:

For positive integers d and m, let $P_{d, m} (G)$ denote the property that between each pair of vertices of the graph G, there are m internally vertex disjoint paths of length at most d. For a positive integer t a graph G satisfies the minimum generalized degree condition δₜ(G) ≥ s if the cardinality of the union of the neighborhoods of each set of t vertices of G is at least s. Generalized degree conditions that ensure that $P_{d, m} (G)$ is satisfied have been investigated. In particular, it has been shown,...

The Turán number of the graph $3 P_{4}$

Halina Bielak, Sebastian Kieliszek (2014)

Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica

Similarity:

Let $e x (n, G)$ denote the maximum number of edges in a graph on $n$ vertices which does not contain $G$ as a subgraph. Let $P_{i}$ denote a path consisting of $i$ vertices and let $m P_{i}$ denote $m$ disjoint copies of $P_{i}$ . In this paper we count $e x (n, 3 P_{4})$ .

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