Secure domination and secure total domination in graphs

William F. Klostermeyer; Christina M. Mynhardt

Displaying similar documents to “Secure domination and secure total domination in graphs”

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

On the total k-domination number of graphs

Adel P. Kazemi (2012)

Discussiones Mathematicae Graph Theory

Similarity:

Let k be a positive integer and let G = (V,E) be a simple graph. The k-tuple domination number $γ_{\times k} (G)$ of G is the minimum cardinality of a k-tuple dominating set S, a set that for every vertex v ∈ V, $| N_{G} [v] \cap S | \geq k$ . Also the total k-domination number $γ_{\times k, t} (G)$ of G is the minimum cardinality of a total k -dominating set S, a set that for every vertex v ∈ V, $| N_{G} (v) \cap S | \geq k$ . The k-transversal number τₖ(H) of a hypergraph H is the minimum size of a subset S ⊆ V(H) such that |S ∩e | ≥ k for every edge e ∈ E(H). We know that for...

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

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

Upper bounds for the domination numbers of toroidal queens graphs

Christina M. Mynhardt (2003)

Discussiones Mathematicae Graph Theory

Similarity:

We determine upper bounds for $γ (Q n^{t})$ and $i (Q ₙ^{t})$ , the domination and independent domination numbers, respectively, of the graph $Q ₙ^{t}$ obtained from the moves of queens on the n×n chessboard drawn on the torus.

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.

A note on the independent domination number versus the domination number in bipartite graphs

Shaohui Wang, Bing Wei (2017)

Czechoslovak Mathematical Journal

Similarity:

Let $γ (G)$ and $i (G)$ be the domination number and the independent domination number of $G$ , respectively. Rad and Volkmann posted a conjecture that $i (G) / γ (G) \leq Δ (G) / 2$ for any graph $G$ , where $Δ (G)$ is its maximum degree (see N. J. Rad, L. Volkmann (2013)). In this work, we verify the conjecture for bipartite graphs. Several graph classes attaining the extremal bound and graphs containing odd cycles with the ratio larger than $Δ (G) / 2$ are provided as well.

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

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

Paired domination in prisms of graphs

Christina M. Mynhardt, Mark Schurch (2011)

Discussiones Mathematicae Graph Theory

Similarity:

The paired domination number $γ_{p r} (G)$ of a graph G is the smallest cardinality of a dominating set S of G such that ⟨S⟩ has a perfect matching. The generalized prisms πG of G are the graphs obtained by joining the vertices of two disjoint copies of G by |V(G)| independent edges. We provide characterizations of the following three classes of graphs: $γ_{p r} (π G) = 2 γ_{p r} (G)$ for all πG; $γ_{p r} (K ₂ ☐ G) = 2 γ_{p r} (G)$ ; $γ_{p r} (K ₂ ☐ G) = γ_{p r} (G)$ .

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

Edit distance measure for graphs

Tomasz Dzido, Krzysztof Krzywdziński (2015)

Czechoslovak Mathematical Journal

Similarity:

In this paper, we investigate a measure of similarity of graphs similar to the Ramsey number. We present values and bounds for $g (n, l)$ , the biggest number $k$ guaranteeing that there exist $l$ graphs on $n$ vertices, each two having edit distance at least $k$ . By edit distance of two graphs $G$ , $F$ we mean the number of edges needed to be added to or deleted from graph $G$ to obtain graph $F$ . This new extremal number $g (n, l)$ is closely linked to the edit distance of graphs. Using probabilistic methods we show...

Distance independence in graphs

J. Louis Sewell, Peter J. Slater (2011)

Discussiones Mathematicae Graph Theory

Similarity:

For a set D of positive integers, we define a vertex set S ⊆ V(G) to be D-independent if u, v ∈ S implies the distance d(u,v) ∉ D. The D-independence number $β_{D} (G)$ is the maximum cardinality of a D-independent set. In particular, the independence number $β (G) = β_{1} (G)$ . Along with general results we consider, in particular, the odd-independence number $β_{O D D} (G)$ where ODD = 1,3,5,....

Remarks on $D$ -integral complete multipartite graphs

Pavel Híc, Milan Pokorný (2016)

Czechoslovak Mathematical Journal

Similarity:

A graph is called distance integral (or $D$ -integral) if all eigenvalues of its distance matrix are integers. In their study of $D$ -integral complete multipartite graphs, Yang and Wang (2015) posed two questions on the existence of such graphs. We resolve these questions and present some further results on $D$ -integral complete multipartite graphs. We give the first known distance integral complete multipartite graphs $K_{p_{1}, p_{2}, p_{3}}$ with $p_{1} < p_{2} < p_{3}$ , and $K_{p_{1}, p_{2}, p_{3}, p_{4}}$ with $p_{1} < p_{2} < p_{3} < p_{4}$ , as well as the infinite classes of distance integral...

A note on the double Roman domination number of graphs

Xue-Gang Chen (2020)

Czechoslovak Mathematical Journal

Similarity:

For a graph $G = (V, E)$ , a double Roman dominating function is a function $f : V \to {0, 1, 2, 3}$ having the property that if $f (v) = 0$ , then the vertex $v$ must have at least two neighbors assigned $2$ under $f$ or one neighbor with $f (w) = 3$ , and if $f (v) = 1$ , then the vertex $v$ must have at least one neighbor with $f (w) \geq 2$ . The weight of a double Roman dominating function $f$ is the sum $f (V) = \sum_{v \in V} f (v)$ . The minimum weight of a double Roman dominating function on $G$ is called the double Roman domination number of $G$ and is denoted by $γ_{dR} (G)$ . In this paper, we establish a new...

On 𝓕-independence in graphs

Frank Göring, Jochen Harant, Dieter Rautenbach, Ingo Schiermeyer (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let be a set of graphs and for a graph G let $α_{} (G)$ and $α *_{} (G)$ denote the maximum order of an induced subgraph of G which does not contain a graph in as a subgraph and which does not contain a graph in as an induced subgraph, respectively. Lower bounds on $α_{} (G)$ and $α *_{} (G)$ are presented.

Characterization by intersection graph of some families of finite nonsimple groups

Hossein Shahsavari, Behrooz Khosravi (2021)

Czechoslovak Mathematical Journal

Similarity:

For a finite group $G$ , $Γ (G)$ , the intersection graph of $G$ , is a simple graph whose vertices are all nontrivial proper subgroups of $G$ and two distinct vertices $H$ and $K$ are adjacent when $H \cap K \neq 1$ . In this paper, we classify all finite nonsimple groups whose intersection graphs have a leaf and also we discuss the characterizability of them using their intersection graphs.