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

Mohsen Jannesari; Behnaz Omoomi

Displaying similar documents to “Characterization of $n$ -vertex graphs with metric dimension $n - 3$ ”

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

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

On-line ranking number for cycles and paths

Erik Bruoth, Mirko Horňák (1999)

Discussiones Mathematicae Graph Theory

Similarity:

A k-ranking of a graph G is a colouring φ:V(G) → 1,...,k such that any path in G with endvertices x,y fulfilling φ(x) = φ(y) contains an internal vertex z with φ(z) > φ(x). On-line ranking number $χ *_{r} (G)$ of a graph G is a minimum k such that G has a k-ranking constructed step by step if vertices of G are coming and coloured one by one in an arbitrary order; when colouring a vertex, only edges between already present vertices are known. Schiermeyer, Tuza and Voigt proved that $χ *_{r} (P ₙ) < 3 l o g ₂ n$ for n ≥ 2....

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

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

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

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

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

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

The total {k}-domatic number of digraphs

Seyed Mahmoud Sheikholeslami, Lutz Volkmann (2012)

Discussiones Mathematicae Graph Theory

Similarity:

For a positive integer k, a total k-dominating function of a digraph D is a function f from the vertex set V(D) to the set 0,1,2, ...,k such that for any vertex v ∈ V(D), the condition $\sum_{u \in N^{-} (v)} f (u) \geq k$ is fulfilled, where N¯(v) consists of all vertices of D from which arcs go into v. A set $f ₁, f ₂, . . ., f_{d}$ of total k-dominating functions of D with the property that $\sum_{i = 1}^{d} f_{i} (v) \leq k$ for each v ∈ V(D), is called a total k-dominating family (of functions) on D. The maximum number of functions in a total k-dominating family on D is...

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

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 order of certain close to regular graphs without a matching of given size

Sabine Klinkenberg, Lutz Volkmann (2007)

Czechoslovak Mathematical Journal

Similarity:

A graph $G$ is a ${d, d + k}$ -graph, if one vertex has degree $d + k$ and the remaining vertices of $G$ have degree $d$ . In the special case of $k = 0$ , the graph $G$ is $d$ -regular. Let $k, p \geq 0$ and $d, n \geq 1$ be integers such that $n$ and $p$ are of the same parity. If $G$ is a connected ${d, d + k}$ -graph of order $n$ without a matching $M$ of size $2 | M | = n - p$ , then we show in this paper the following: If $d = 2$ , then $k \geq 2 (p + 2)$ and (i) $n \geq k + p + 6$ . If $d \geq 3$ is odd and $t$ an integer with $1 \leq t \leq p + 2$ , then (ii) $n \geq d + k + 1$ for $k \geq d (p + 2)$ , (iii) $n \geq d (p + 3) + 2 t + 1$ for $d (p + 2 - t) + t \leq k \leq d (p + 3 - t) + t - 3$ , (iv) $n \geq d (p + 3) + 2 p + 7$ for $k \leq p$ . If $d \geq 4$ is even, then (v) $n \geq d + k + 2 - η$ for $k \geq d (p + 3) + p + 4 + η$ , (vi) $n \geq d + k + p + 2 - 2 t = d (p + 4) + p + 6$ for $k = d (p + 3) + 4 + 2 t$ and $p \geq 1$ ,...

On the heterochromatic number of circulant digraphs

Hortensia Galeana-Sánchez, Víctor Neumann-Lara (2004)

Discussiones Mathematicae Graph Theory

Similarity:

The heterochromatic number hc(D) of a digraph D, is the minimum integer k such that for every partition of V(D) into k classes, there is a cyclic triangle whose three vertices belong to different classes. For any two integers s and n with 1 ≤ s ≤ n, let $D_{n, s}$ be the oriented graph such that $V (D_{n, s})$ is the set of integers mod 2n+1 and $A (D_{n, s}) = (i, j) : j - i \in 1, 2, . . ., n ∖ s . .$ In this paper we prove that $h c (D_{n, s}) \leq 5$ for n ≥ 7. The bound is tight since equality holds when s ∈ n,[(2n+1)/3].

A remark on the (2,2)-domination number

Torsten Korneffel, Dirk Meierling, Lutz Volkmann (2008)

Discussiones Mathematicae Graph Theory

Similarity:

A subset D of the vertex set of a graph G is a (k,p)-dominating set if every vertex v ∈ V(G)∖D is within distance k to at least p vertices in D. The parameter $γ_{k, p} (G)$ denotes the minimum cardinality of a (k,p)-dominating set of G. In 1994, Bean, Henning and Swart posed the conjecture that $γ_{k, p} (G) \leq (p / (p + k)) n (G)$ for any graph G with δₖ(G) ≥ k+p-1, where the latter means that every vertex is within distance k to at least k+p-1 vertices other than itself. In 2005, Fischermann and Volkmann confirmed this conjecture...

On vertex stability with regard to complete bipartite subgraphs

Aneta Dudek, Andrzej Żak (2010)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G is called (H;k)-vertex stable if G contains a subgraph isomorphic to H ever after removing any of its k vertices. Q(H;k) denotes the minimum size among the sizes of all (H;k)-vertex stable graphs. In this paper we complete the characterization of $(K_{m, n}; 1)$ -vertex stable graphs with minimum size. Namely, we prove that for m ≥ 2 and n ≥ m+2, $Q (K_{m, n}; 1) = m n + m + n$ and $K_{m, n} * K ₁$ as well as $K_{m + 1, n + 1} - e$ are the only $(K_{m, n}; 1)$ -vertex stable graphs with minimum size, confirming the conjecture of Dudek and Zwonek.

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

Displaying similar documents to “Characterization of n -vertex graphs with metric dimension n - 3 ”

Displaying similar documents to “Characterization of $n$ -vertex graphs with metric dimension $n - 3$ ”