The k-component domination number γk(G) of G is the minimum cardinality of a dominating set S of G such that each component of GS has order at least k. Clearly, γ1(G) is the domination number of G ...and γ2(G) is the total domination number of G. With a finite set of exceptional graphs, McCuaig and Shepherd (1989) 13 proved that γ1(G)≤25n and Henning (2000) 11 proved that γ2(G)≤47n respectively. As an extension, Alvarado et al. (2016) 1 posed a conjecture which says that if G is a connected graph of order n≥k+1 and δ(G)≥2, then γk(G)≤2kn2k+3 unless G belongs to a set of exceptional graphs. In this paper, we confirm the validity of the above conjecture. Moreover, we characterize those graphs of order n which are edge-minimal with respect to satisfying G connected, δ(G)≥2 and γk(G)≥2kn2k+3. This strengthens a result of Alvarado, Dantas, and Rautenbach in the same paper.
Abstract
A subset
D
of the vertex set
V
(
G
) of a graph
G
is said to be a dominating set if every vertex not in
D
is adjacent to at least one vertex in
V
-
D
. A dominating set
D
is said to be an ...interior dominating set if every vertex v ∈
D
, is an interior vertex of
G
. The minimum of the cardinalities of the interiordominating sets of
G
is called the interiordomination number
γ
I
d
(
G
) of
G
.An interior dominating set
D
of
G
is a splitinteriordominating set if the induced subgraph <
V
-
D
> is disconnected An interior dominating set
D
of
G
is a strong split interior dominating set if the induced subgraph <
V
-
D
> is totally disconnected with at least two vertices. In this paper, we determine the number and
γ
s
I
d
and
γ
s
s
i
d
for some standard graphs and obtain bounds for general graphs.
k$-Efficient partitions of graphs M. Chellali; Teresa W. Haynes; Stephen T. Hedetniemi
Communications in combinatorics and optimization,
12/2019, Letnik:
4, Številka:
2
Journal Article
Recenzirano
Odprti dostop
A set $S = \{u_1,u_2, \ldots, u_t\}$ of vertices of $G$ is an efficient dominating set if every vertex of $G$ is dominated exactly once by the vertices of $S$. Letting $U_i$ denote the set of ...vertices dominated by $u_i$% , we note that $\{U_1, U_2, \ldots U_t\}$ is a partition of the vertex set of $G$ and that each $U_i$ contains the vertex $u_i$ and all the vertices at distance~1 from it in $G$. In this paper, we generalize the concept of efficient domination by considering $k$-efficient domination partitions of the vertex set of $G$, where each element of the partition is a set consisting of a vertex $u_i$ and all the vertices at distance~$d_i$ from it, where $d_i \in \{0,1, \ldots, k\}$. For any integer $k \geq 0$, the $k$% -efficient domination number of $G$ equals the minimum order of a $k$% -efficient partition of $G$. We determine bounds on the $k$-efficient domination number for general graphs, and for $k \in \{1,2\}$, we give exact values for some graph families. Complexity results are also obtained.
We mainly study two related dominating functions, namely, the weak Roman and 2-rainbow dominating functions. We show that for all graphs, the weak Roman domination number is bounded above by the ...2-rainbow domination number. We present bounds on the weak Roman domination number and the secure domination number in terms of the total domination number for specific families of graphs, and we show that the 2-rainbow domination number is bounded below by the total domination number for trees and for a subfamily of cactus graphs.
The aim of this paper is to obtain closed formulas for the perfect domination number, the Roman domination number and the perfect Roman domination number of lexicographic product graphs. We show that ...these formulas can be obtained relatively easily for the case of the first two parameters. The picture is quite different when it concerns the perfect Roman domination number. In this case, we obtain general bounds and then we give sufficient and/or necessary conditions for the bounds to be achieved. We also discuss the case of perfect Roman graphs and we characterize the lexicographic product graphs where the perfect Roman domination number equals the Roman domination number.
SECURE POINT SET DOMINATION IN GRAPHS Gupta, Purnima; Goyal, Alka
TWMS journal of applied and engineering mathematics,
04/2024, Letnik:
14, Številka:
2
Journal Article
Recenzirano
In this paper, we introduce the notion of secure point-set domination in graphs. A point-set dominating D of graph G is called a secure point-set dominating set if for every vertex u member of V - D, ...there exists a vertex v member of D intersection N (u) such that (D - {v}) union{u} is also a point-set dominating set of G. The minimum cardinality of a secure point-set dominating set is called secure point-set domination number of graph G and will be denoted by gamma.sub.spsd(G) (or simply gamma.sub.spsd). For any graph G of order n, gamma.sub.spsd(G) greater than or equal to 1 and equality holds if and only if G congruent to K.sub.n. Also, for any graph G of order n, gamma.sub.spsd(G) less than or equal to n - 1 and equality holds if and only if G congruent to K.sub.1,n-1. Here we characterize graphs G with gamma.sub.spsd(G) = 2. We also establish a family F of 11 graphs such that being F-free is necessary as well as sufficient for a graph G to satisfy gamma.sub.spsd(G) = n - 2. Keywords: Domination, Point-Set Domination, Secure Domination, Secure Point-Set Domination, Secure Point-Set Domination Number. AMS Subject Classification: 05C69.
In this paper, we continue the study of the domination game on graphs introduced by Brešar et al. (2010). Haynes and Henning in 2009 introduced a paired-domination version of the domination game. We ...study an alternative paired-domination version of the domination game played on a graph G by two players, named Dominator and Staller. The players take turns choosing a pair of adjacent vertices of G such that neither vertex in the pair has yet been chosen and the vertices in the pair must dominate at least one vertex not dominated by the previously chosen vertices. This process eventually produces a paired-dominating set of vertices of G; that is, a dominating set in G that induces a subgraph that contains a perfect matching. Dominator wishes to minimize the number of vertices chosen, while Staller wishes to maximize it. The game paired-domination number γgpr(G) of G is the number of vertices chosen when Dominator starts the game and both players play optimally, and the Staller-start game paired-domination number γgpr′(G) of G is the number of vertices chosen when Staller starts the game and both players play optimally. In this paper, we determine the paired-domination numbers γgpr(G) and γgpr′(G) when the graph G is a cycle.
A vertex v of a graph G=(V,E) is said to be undefended with respect to a function f:V⟶{0,1,2} if f(v)=0 and f(u)=0 for every vertex u adjacent to v. We call the function f a weak Roman dominating ...function if for every v such that f(v)=0 there exists a vertex u adjacent to v such that f(u)∈{1,2} and the function f′:V⟶{0,1,2} defined by f′(v)=1, f′(u)=f(u)−1 and f′(z)=f(z) for every z∈V∖{u,v}, has no undefended vertices. The weight of f is w(f)=∑v∈V(G)f(v). The weak Roman domination number of a graph G, denoted by γr(G), is the minimum weight among all weak Roman dominating functions on G. Henning and Hedetniemi (2003) showed that the problem of computing γr(G) is NP-Hard, even when restricted to bipartite or chordal graphs. This suggests finding γr(G) for special classes of graphs or obtaining good bounds on this invariant. In this article, we obtain closed formulae and tight bounds for the weak Roman domination number of lexicographic product graphs in terms of invariants of the factor graphs involved in the product.
PDF
![Roman [1,2]-domination of g...](http://api.summon.serialssolutions.com/2.0.0/image/issn/XR4PS5YY4K/0096-3003/small "Roman [1,2]-domination of graphs")
