Full domination in graphs

Robert C. Brigham; Gary Chartrand; Ronald D. Dutton; Ping Zhang

Displaying similar documents to “Full 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 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)...

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

Characterizing finite groups whose enhanced power graphs have universal vertices

David G. Costanzo, Mark L. Lewis, Stefano Schmidt, Eyob Tsegaye, Gabe Udell (2024)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a finite group and construct a graph $Δ (G)$ by taking $G ∖ {1}$ as the vertex set of $Δ (G)$ and by drawing an edge between two vertices $x$ and $y$ if $〈 x, y 〉$ is cyclic. Let $K (G)$ be the set consisting of the universal vertices of $Δ (G)$ along the identity element. For a solvable group $G$ , we present a necessary and sufficient condition for $K (G)$ to be nontrivial. We also develop a connection between $Δ (G)$ and $K (G)$ when $| G |$ is divisible by two distinct primes and the diameter of $Δ (G)$ is 2.

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

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

Turán number of two vertex-disjoint copies of cliques

Caiyun Hu (2024)

Czechoslovak Mathematical Journal

Similarity:

The Turán number of a given graph $H$ , denoted by $ex (n, H)$ , is the maximum number of edges in an $H$ -free graph on $n$ vertices. Applying a well-known result of Hajnal and Szemerédi, we determine the Turán number $ex (n, K_{p} \cup K_{q}$ ) of a vertex-disjoint union of cliques $K_{p}$ and $K_{q}$ for all values of $n$ .

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

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.

Degree sums of adjacent vertices for traceability of claw-free graphs

Tao Tian, Liming Xiong, Zhi-Hong Chen, Shipeng Wang (2022)

Czechoslovak Mathematical Journal

Similarity:

The line graph of a graph $G$ , denoted by $L (G)$ , has $E (G)$ as its vertex set, where two vertices in $L (G)$ are adjacent if and only if the corresponding edges in $G$ have a vertex in common. For a graph $H$ , define ${\bar{σ}}_{2} (H) = min {d (u) + d (v) : u v \in E (H)}$ . Let $H$ be a 2-connected claw-free simple graph of order $n$ with $δ (H) \geq 3$ . We show that, if ${\bar{σ}}_{2} (H) \geq \frac{1}{7} (2 n - 5)$ and $n$ is sufficiently large, then either $H$ is traceable or the Ryjáček’s closure $cl (H) = L (G)$ , where $G$ is an essentially $2$ -edge-connected triangle-free graph that can be contracted to one of the two graphs of order 10...

On upper bounds for total $k$ -domination number via the probabilistic method

Saylí Sigarreta, Saylé Sigarreta, Hugo Cruz-Suárez (2023)

Kybernetika

Similarity:

For a fixed positive integer $k$ and $G = (V, E)$ a connected graph of order $n$ , whose minimum vertex degree is at least $k$ , a set $S \subseteq V$ is a total $k$ -dominating set, also known as a $k$ -tuple total dominating set, if every vertex $v \in V$ has at least $k$ neighbors in $S$ . The minimum size of a total $k$ -dominating set for $G$ is called the total $k$ -domination number of $G$ , denoted by $γ_{k t} (G)$ . The total $k$ -domination problem is to determine a minimum total $k$ -dominating set of $G$ . Since the exact problem is in general quite difficult...

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

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

On the domination of triangulated discs

Noor A&amp;#039;lawiah Abd Aziz, Nader Jafari Rad, Hailiza Kamarulhaili (2023)

Mathematica Bohemica

Similarity:

Let $G$ be a $3$ -connected triangulated disc of order $n$ with the boundary cycle $C$ of the outer face of $G$ . Tokunaga (2013) conjectured that $G$ has a dominating set of cardinality at most $\frac{1}{4} (n + 2)$ . This conjecture is proved in Tokunaga (2020) for $G - C$ being a tree. In this paper we prove the above conjecture for $G - C$ being a unicyclic graph. We also deduce some bounds for the double domination number, total domination number and double total domination number in triangulated discs.

Recognizability of finite groups by Suzuki group

Alireza Khalili Asboei, Seyed Sadegh Salehi Amiri (2019)

Archivum Mathematicum

Similarity:

Let $G$ be a finite group. The main supergraph $𝒮 (G)$ is a graph with vertex set $G$ in which two vertices $x$ and $y$ are adjacent if and only if $o (x) ∣ o (y)$ or $o (y) ∣ o (x)$ . In this paper, we will show that $G ≅ S z (q)$ if and only if $𝒮 (G) ≅ 𝒮 (S z (q))$ , where $q = 2^{2 m + 1} \geq 8$ .

The small Ree group $^{2} G_{2} (3^{2 n + 1})$ and related graph

Alireza K. Asboei, Seyed S. S. Amiri (2018)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

Let $G$ be a finite group. The main supergraph $𝒮 (G)$ is a graph with vertex set $G$ in which two vertices $x$ and $y$ are adjacent if and only if $o (x) ∣ o (y)$ or $o (y) ∣ o (x)$ . In this paper, we will show that $G ≅^{2} G_{2} (3^{2 n + 1})$ if and only if $𝒮 (G) ≅ 𝒮 (^{2} G_{2} (3^{2 n + 1}))$ . As a main consequence of our result we conclude that Thompson’s problem is true for the small Ree group $^{2} G_{2} (3^{2 n + 1})$ .