Fix a positive integer n and consider the bipartite graph whose vertices are the 3-element subsets and the 2-element subsets of n={1,2,…,n}, and there is an edge between A and B if A⊂B. We prove that ...the domination number of this graph is n2−⌊(n+1)28⌋, we characterize the dominating sets of minimum size, and we observe that the minimum size dominating set can be chosen as an independent set. This is an exact version of an asymptotic result by Balogh, Katona, Linz and Tuza (2021). For the corresponding bipartite graph between the (k+1)-element subsets and the k-element subsets of n (k⩾3), we provide a new construction for small independent dominating sets. This improves on a construction by Gerbner, Kezegh, Lemons, Palmer, Pálvölgyi and Patkós (2012), who studied these independent dominating sets under the name saturating flat antichains.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPUK, ZAGLJ, ZRSKP
In 2011, Henning, Löwenstein, and Rautenbach observed that the domination number of a graph is bounded above by the product of the packing number and the maximum degree of the graph. In this paper, ...we prove a stronger statement in subcubic graphs: The independent domination number is at most three times the packing number.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPUK, ZAGLJ, ZRSKP
Given a graph G $G$, a dominating set of G $G$ is a set S $S$ of vertices such that each vertex not in S $S$ has a neighbor in S $S$. Let γ(
G
) $\gamma (G)$ denote the minimum size of a dominating ...set of G $G$. The independent domination number of G $G$, denoted i(
G
) $i(G)$, is the minimum size of a dominating set of G $G$ that is also independent. We prove that if G $G$ is a cubic graph without 4‐cycles, then i(
G
)
≤
5
14
∣
V(
G
)
∣ $i(G)\le \frac{5}{14}| V(G)| $, and the bound is tight. This result improves upon two results from two papers by Abrishami and Henning. Our result also implies that every cubic graph G $G$ without 4‐cycles satisfies i(
G
)γ(
G
)
≤
5
4 $\frac{i(G)}{\gamma (G)}\le \frac{5}{4}$, which supports a question asked by O and West.
Full text
Available for:
BFBNIB, FZAB, GIS, IJS, KILJ, NLZOH, NUK, OILJ, SAZU, SBCE, SBMB, UL, UM, UPUK
Let G be a nontrivial connected graph with vertex set V(G). A set D⊆V(G) is a double dominating set of G if |Nv∩D|≥2 for every vertex v∈V(G), where Nv represents the closed neighbourhood of v. The ...double domination number of G, denoted by γ×2(G), is the minimum cardinality among all double dominating sets of G. In this note we show that for any nontrivial tree T, n(T)−γ(T)+l(T)+s(T)+12≤γ×2(T)≤n(T)+γ(T)+l(T)2, where n(T), l(T), s(T) and γ(T) represent the order, the number of leaves, the number of support vertices and the classical domination number of T, respectively. In addition, we show that the established upper bound improves a well-known bound and as a consequence, derives two new results.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPUK, ZAGLJ, ZRSKP
Abstract The independent domination number i ( G ) of a graph G is the minimum cardinality of a maximal independent set of G , also called an i ( G )-set. The i -graph of G , denoted ℐ ( G ), is the ...graph whose vertices correspond to the i ( G )-sets, and where two i ( G )-sets are adjacent if and only if they differ by two adjacent vertices. Not all graphs are i -graph realizable, that is, given a target graph H , there does not necessarily exist a source graph G such that H = ℐ ( G ). We consider a class of graphs called “theta graphs”: a theta graph is the union of three internally disjoint nontrivial paths with the same two distinct end vertices. We characterize theta graphs that are i -graph realizable, showing that there are only finitely many that are not. We also characterize those line graphs and claw-free graphs that are i -graphs, and show that all 3-connected cubic bipartite planar graphs are i -graphs.
Let $G$ be a connected graph. A set $D\subseteq V(G)$ is called a connected outer-hop independent dominating if $D$ is a connected dominating set and $V(G)\s D$ is a hop independent set in $G$, ...respectively. The minimum cardinality of a connected outer-hop independent dominating set in $G$, denoted by $\gamma_{c}^{ohi}(G)$, is called the connected outer-hop independent domination number of $G$. In this paper, we introduce and investigated the concept of connected outer-hop independent domination in a graph. We show that the connected outer-hop independent domination number and connected outer-independent domination number of a graph are incomparable. In fact, we find that their absolute difference can be made arbitrarily large. In addition, we characterize connected outer-hop independent dominating sets in graphs under some binary operations. Furthermore, these results are used to give exact values or bounds of the parameter for these graphs.
Full text
Available for:
IZUM, KILJ, NUK, PILJ, PNG, SAZU, UL, UM, UPUK
A set
D
of vertices in a graph
G
is an independent dominating set of
G
if
D
is an independent set and every vertex not in
D
is adjacent to a vertex in
D
. The independent domination number of
G
, ...denoted by
i
(
G
), is the minimum cardinality among all independent dominating sets of
G
. In this paper we show that if
T
is a nontrivial tree, then
i
(
T
) ≥
n
(
T
)+γ(
T
)−
l
(
T
)+2/4, where
n
(
T
),
γ
(
T
) and
l
(
T
) represent the order, the domination number and the number of leaves of
T
, respectively. In addition, we characterize the trees achieving this new lower bound.
For a graph
, let
) be the domination number,
) be the independent domination number and
) be the 2-independence number. In this paper, we prove that for any tree
of order
≥ 2, 4
) − 3
) ≥ 3
), and ...we characterize all trees attaining equality. Also we prove that for every tree
of order
≥ 2,
, and we characterize all extreme trees.
Full text
Available for:
IZUM, KILJ, NUK, PILJ, PNG, SAZU, UL, UM, UPUK
Let G = (V, E) be a graph with vertex set V and edge set E. An independent dominating set S of G is a subset of V with the property that every vertex in V - S is adjacent to some vertex in S and no ...two vertices within S are adjacent. The number of vertices in a minimum independent dominating set in the graph G is called the independent domination number i(G) of G. In this article, the independent domination number of graphs obtained through vertex switching have been computed with appropriate illustration. Keywords: Graphs, independent domination, independent dominating set, independent domination number, vertex switching. AMS Subject Classification: 05C69, 05C76.
PDF
