On the total k-domination number of graphs

Adel P. Kazemi

Displaying similar documents to “On the total k-domination number of graphs”

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

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

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.

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

Secure domination and secure total domination in graphs

William F. Klostermeyer, Christina M. Mynhardt (2008)

Discussiones Mathematicae Graph Theory

Similarity:

A secure (total) dominating set of a graph G = (V,E) is a (total) dominating set X ⊆ V with the property that for each u ∈ V-X, there exists x ∈ X adjacent to u such that $(X - x) \cup u$ is (total) dominating. The smallest cardinality of a secure (total) dominating set is the secure (total) domination number $γ_{s} (G) (γ_{s t} (G))$ . We characterize graphs with equal total and secure total domination numbers. We show that if G has minimum degree at least two, then $γ_{s t} (G) \leq γ_{s} (G)$ . We also show that $γ_{s t} (G)$ is at most twice the clique covering...

The extremal irregularity of connected graphs with given number of pendant vertices

Xiaoqian Liu, Xiaodan Chen, Junli Hu, Qiuyun Zhu (2022)

Czechoslovak Mathematical Journal

Similarity:

The irregularity of a graph $G = (V, E)$ is defined as the sum of imbalances $| d_{u} - d_{v} |$ over all edges $u v \in E$ , where $d_{u}$ denotes the degree of the vertex $u$ in $G$ . This graph invariant, introduced by Albertson in 1997, is a measure of the defect of regularity of a graph. In this paper, we completely determine the extremal values of the irregularity of connected graphs with $n$ vertices and $p$ pendant vertices ( $1 \leq p \leq n - 1$ ), and characterize the corresponding extremal graphs.

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.

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.

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.

Proper connection number of bipartite graphs

Jun Yue, Meiqin Wei, Yan Zhao (2018)

Czechoslovak Mathematical Journal

Similarity:

An edge-colored graph $G$ is proper connected if every pair of vertices is connected by a proper path. The proper connection number of a connected graph $G$ , denoted by $pc (G)$ , is the smallest number of colors that are needed to color the edges of $G$ in order to make it proper connected. In this paper, we obtain the sharp upper bound for $pc (G)$ of a general bipartite graph $G$ and a series of extremal graphs. Additionally, we give a proper $2$ -coloring for a connected bipartite graph $G$ having $δ (G) \geq 2$ and a dominating...

On the intersection graph of a finite group

Hossein Shahsavari, Behrooz Khosravi (2017)

Czechoslovak Mathematical Journal

Similarity:

For a finite group $G$ , the intersection graph of $G$ which is denoted by $Γ (G)$ is an undirected graph such that its 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 groups whose intersection graphs are regular. Also, we find some results on the intersection graphs of simple groups and finally we study the structure of $Aut (Γ (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$ .

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

Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs

Éric Sopena (2012)

Discussiones Mathematicae Graph Theory

Similarity:

The oriented chromatic number of an oriented graph $^{\to} G$ is the minimum order of an oriented graph $^{\to} H$ such that $^{\to} G$ admits a homomorphism to $^{\to} H$ . The oriented chromatic number of an undirected graph G is then the greatest oriented chromatic number of its orientations. In this paper, we introduce the new notion of the upper oriented chromatic number of an undirected graph G, defined as the minimum order of an oriented graph $^{\to} U$ such that every orientation $^{\to} G$ of G admits a homomorphism to $^{\to} U$ . We give...

On the diameter of the intersection graph of a finite simple group

Xuanlong Ma (2016)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a finite group. The intersection graph $Δ_{G}$ of $G$ is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper nontrivial subgroups of $G$ , and two distinct vertices $X$ and $Y$ are adjacent if $X \cap Y \neq 1$ , where $1$ denotes the trivial subgroup of order $1$ . A question was posed by Shen (2010) whether the diameters of intersection graphs of finite non-abelian simple groups have an upper bound. We answer the question and show that the diameters...