Article in press
Authors:
Title:
The probabilistic upper bounds on the isolation number of a graph
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2024-11-18 , Revised: 2025-03-24 , Accepted: 2025-03-24 , Available online: 2025-04-04 , https://doi.org/10.7151/dmgt.2583
Abstract:
Let $G=(V,E)$ be a graph.
A subset $S\subseteq V$ is an isolating set of $G$ if the graph induced by
the set $V\backslash N[S]$ contains no edge. The size of a smallest isolating
set of $G$ is called the isolation number, denoted by $\iota(G)$.
\iffalse
We say that a vertex $v$ $ve$-dominates each edge incident to a vertex in $N[v]$.
A subset $S\subseteq V$ is a vertex-edge dominating set ($ve$-dominating set) of
$G$, if there exists a vertex $v\in S$ such that $v$ $ve$-dominates $e$ for each
edge $e\in E$. The vertex-edge domination number ($ve$-domination number)
$\gamma_{ve}(G)$ is the minimum cardinality of a vertex-edge dominating set of
$G$. In fact, for any graph $G$, $\iota(G)$ is equal to $\gamma_{ve}(G)$.
\fi
In this paper, we obtain the upper bounds on $\iota(G)$ via probabilistic
method, and improve the previous bound on $\iota(G)$ given by Caro and Hansberg.
Keywords:
domination, isolating set, isolation number
References:
- N. Alon, J.H. Spencer, The Probabilistic Method (John Wiley $\&$ Sons, Inc., Chichester, 2000).
https://doi.org/10.1002/0471722154 - P. Borg, Isolation of connected graphs, Discrete Appl. Math. 339 (2023) 154–165.
https://doi.org/10.1016/j.dam.2023.05.004 - P. Borg, Isolation of cycles, Graphs Combin. 36 (2020) 631–637.
https://doi.org/10.1007/s00373-020-02143-2 - P. Borg and P. Kaemawichanurat, Partial domination of maximal outerplanar graphs, Discrete Appl. Math. 283 (2020) 306–314.
https://doi.org/10.1016/j.dam.2020.01.005 - P. Borg, K. Fenech and P. Kaemawichanurat, Isolation of $k$-cliques II, Discrete Math. 345(7) (2022) 112641.
https://doi.org/10.1016/j.disc.2021.112641 - P. Borg and P. Kaemawichanurat, Extensions of the Art Gallery Theorem, Ann. Comb. 27 (2023) 31–50.
https://doi.org/10.1007/s00026-022-00620-4 - Y. Caro and A. Hansberg, Partial domination–the isolation number of a graph, Filomat 31 (2017) 3925–3944.
https://doi.org/10.2298/FIL1712925C - J. Chen and S-J. Xu, $P_{5}$-isolation in graphs, Discrete Appl. Math. 340 (2023) 331–349.
https://doi.org/10.1016/j.dam.2023.07.018 - T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).
https://doi.org/10.1201/9781482246582 - T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Structures of Domination in Graphs, Dev. Math. 66 (Springer, Cham, 2021).
https://doi.org/10.1007/978-3-030-58892-2 - T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Domination in Graphs: Core Concepts, Springer Monogr. Math. (Springer, Cham, 2023).
https://doi.org/10.1007/978-3-031-09496-5 - P. Kaemawichanurat and O. Favaron, Partial domination and irredundance numbers in graphs, Appl. Math. Comput. 457 (2023) 128153.
https://doi.org/10.1016/j.amc.2023.128153 - O. Ore, Theory of Graphs, in: Amer. Math. Soc. Colloq. Publ. 38, (Providence, RI 1962) 206–212.
https://doi.org/10.1090/coll/038 - J.W. Peters, Theoretical and Algorithmic Results on Domination and Connectivity, PhD Thesis (Clemson University, Clemson, 1986).
- N.J. Rad, New probabilistic upper bounds on the domination number of a graph, Electron. J. Combin. 26(3) (2019) #P3.28.
https://doi.org/10.37236/8345 - S. Tokunaga, T. Jiarasuksakun and P. Kaemawichanurat, Isolation number of maximal outerplanar graphs, Discrete Appl. Math. 267 (2019) 215-218.
https://doi.org/10.1016/j.dam.2019.06.011 - J. Yan, Isolation of the Diamond Graph, Bull. Malays. Math. Sci. Soc. 45 (2022) 1169–1181.
https://doi.org/10.1007/s40840-022-01248-6 - Y. Yin, X. An and B. Wu, $K_{1,2}$-isolation number of claw-free cubic graphs, Bull. Malays. Math. Sci. Soc. 47 (2024) 75.
https://doi.org/10.1007/s40840-024-01672-w - G. Zhang and B. Wu, A Note on the cycle isolation number of graphs, Bull. Malays. Math. Sci. Soc. 47 (2024) 57.
https://doi.org/10.1007/s40840-024-01655-x
Close