The independent isolation number of a tree

Quanli Hao; Xinhui An; Baoyindureng Wu

doi:10.5802/crmath.787

Article de recherche - Théorie du contrôle

The independent isolation number of a tree
[L’indice d’isolement indépendant d’un arbre]

Quanli Hao ¹ ; Xinhui An ¹ ; Baoyindureng Wu ¹

¹ College of Mathematics and System Science, Xinjiang University, Urumiqi 830046, Xinjiang, China

Comptes Rendus. Mathématique, Volume 363 (2025), pp. 1289-1299

Abstract (VO)
Résumé

Let $G$ be a simple graph. An isolating set of $G$ is a set $I$ of vertices such that removing $I$ and its neighborhood leaves no edge. In addition, the set $I$ is said to be an independent isolating set of $G$ if $I$ is an isolating set of $G$ and $G[I]$ has no edge, where $G[I]$ represents the subgraph of $G$ induced by $I$. The independent isolation number of $G$, denoted by $\iota ^i(G)$, is the minimum cardinality of among all independent isolating sets of $G$. In this paper, we prove that for every tree $T$ except a star,

\[ \frac{n(T)-\vert {L(T)}\vert -\vert {S(T)}\vert +3}{4}\le \iota ^i(T)\le \frac{n(T)- \vert {L(T)}\vert +2\vert {S(T)}\vert }{4}, \]

where $n(T)$, $L(T)$ and $S(T)$ represent the order, the sets of leaves and support vertices, respectively. Finally, we characterize the extremal trees attaining the bounds.

Soit $G$ un graphe simple. Un ensemble isolant de $G$ est un ensemble $I$ de sommets tel que la suppression de $I$ et de son voisinage laisse le graphe sans arêtes. De plus, l’ensemble $I$ est dit un ensemble isolant indépendant de $G$ si $I$ est un ensemble isolant de $G$ et si $G[I]$ ne contient pas d’arêtes, où $G[I]$ représente le sous-graphe de $G$ induit par $I$. Le nombre d’isolement indépendant de $G$, noté $ \iota ^i(G)$, est la cardinalité minimum parmi tous les ensembles isolants indépendants de $G$. Dans cet article, nous prouvons que pour chaque arbre $T$ sauf une étoile,

\[ \frac{n(T)-\vert {L(T)}\vert -\vert {S(T)}\vert +3}{4}\le \iota ^i(T)\le \frac{n(T)- \vert {L(T)}\vert +2\vert {S(T)}\vert }{4}, \]

où $n(T)$, $L(T)$ et $S(T)$ représentent respectivement l’ordre de $T$, l’ensemble des feuilles et l’ensemble des sommets de support. Enfin, nous caractérisons les arbres extrémaux atteignant les bornes.

Reçu le : 2025-01-27
Accepté le : 2025-08-14
Publié le : 2025-10-20

DOI : 10.5802/crmath.787

Classification : 05C05, 05C35
Keywords: Tree, independent isolating set, independent isolation number
Mots-clés : Arbre, ensemble isolant indépendant, numéro d’isolation indépendant

Affiliations des auteurs :

Quanli Hao ¹ ; Xinhui An ¹ ; Baoyindureng Wu ¹

¹ College of Mathematics and System Science, Xinjiang University, Urumiqi 830046, Xinjiang, China

Licence :

CC-BY 4.0

Droits d'auteur : Les auteurs conservent leurs droits

@article{CRMATH_2025__363_G12_1289_0,
     author = {Quanli Hao and Xinhui An and Baoyindureng Wu},
     title = {The independent isolation number of a tree},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {1289--1299},
     year = {2025},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {363},
     doi = {10.5802/crmath.787},
     language = {en},
}

TY  - JOUR
AU  - Quanli Hao
AU  - Xinhui An
AU  - Baoyindureng Wu
TI  - The independent isolation number of a tree
JO  - Comptes Rendus. Mathématique
PY  - 2025
SP  - 1289
EP  - 1299
VL  - 363
PB  - Académie des sciences, Paris
DO  - 10.5802/crmath.787
LA  - en
ID  - CRMATH_2025__363_G12_1289_0
ER  -

%0 Journal Article
%A Quanli Hao
%A Xinhui An
%A Baoyindureng Wu
%T The independent isolation number of a tree
%J Comptes Rendus. Mathématique
%D 2025
%P 1289-1299
%V 363
%I Académie des sciences, Paris
%R 10.5802/crmath.787
%G en
%F CRMATH_2025__363_G12_1289_0

Quanli Hao; Xinhui An; Baoyindureng Wu. The independent isolation number of a tree. Comptes Rendus. Mathématique, Volume 363 (2025), pp. 1289-1299. doi: 10.5802/crmath.787

Bibliographie
Cité par

[1] Geoffrey Boyer; Wayne Goddard Disjoint isolating sets and graphs with maximum isolation number, Discrete Appl. Math., Volume 356 (2024), pp. 110-116 | DOI | MR | Zbl

[2] Abel Cabrera-Martínez A new lower bound for the independent domination number of a tree, RAIRO, Oper. Res., Volume 57 (2023) no. 4, pp. 1951-1956 | DOI | MR | Zbl

[3] Abel Cabrera-Martínez An improved upper bound on the domination number of a tree, Discrete Appl. Math., Volume 343 (2024), pp. 44-48 | DOI | MR | Zbl

[4] Abel Cabrera-Martínez; Andrea Conchado Peiró On the ${2}$ -domination number of graphs, AIMS Math., Volume 7 (2022) no. 6, pp. 10731-10743 | DOI | MR

[5] Abel Cabrera-Martínez; Andrea Conchado Peiró; Juan Manuel Rueda-Vázquez Further results on the total Italian domination number of trees, AIMS Math., Volume 8 (2023) no. 5, pp. 10654-10664 | DOI | MR

[6] Yair Caro; Adriana Hansberg Partial domination—the isolation number of a graph, Filomat, Volume 31 (2017) no. 12, pp. 3925-3944 | DOI | MR | Zbl

[7] Mustapha Chellali; Nacéra Meddah Trees with equal 2-domination and 2-independence numbers, Discuss. Math., Graph Theory, Volume 32 (2012) no. 2, pp. 263-270 | DOI | MR | Zbl

[8] Xue-Gang Chen; Kai Yin; Ting Gao A note on independent vertex-edge domination in graphs, Discrete Optim., Volume 25 (2017), pp. 1-5 | DOI | MR | Zbl

[9] Nasrin Dehgardi; Seyed Mahmoud Sheikholeslami; Mina Valinavaz; Hamideh Aram; Lutz Volkmann Domination number, independent domination number and 2-independence number in trees, Discuss. Math., Graph Theory, Volume 41 (2021) no. 1, pp. 39-49 | DOI | MR | Zbl

[10] Odile Favaron A bound on the independent domination number of a tree, Vishwa Int. J. Graph Theory, Volume 1 (1992) no. 1, pp. 19-27 | MR

[11] Odile Favaron; Pawaton Kaemawichanurat Inequalities between the $K_{k}$ -isolation number and the independent $K_{k}$ -isolation number of a graph, Discrete Appl. Math., Volume 289 (2021), pp. 93-97 | DOI | MR | Zbl

[12] Balakrishna Krishnakumari; Yanamandram B. Venkatakrishnan; Marcin Krzywkowski Bounds on the vertex-edge domination number of a tree, C. R. Math., Volume 352 (2014) no. 5, pp. 363-366 | DOI | MR | Numdam | Zbl

[13] Magdalena Lemańska Lower bound on the domination number of a tree, Discuss. Math., Graph Theory, Volume 24 (2004) no. 2, pp. 165-169 | DOI | MR | Zbl

[14] Jason Robert Lewis Vertex-edge and edge-vertex domination in graphs, Ph. D. Thesis, Clemson University (USA) (2007)

[15] Jason Robert Lewis; Stephen T. Hedetniemi; Teresa W. Haynes; Gerd H. Fricke Vertex-edge domination, Util. Math., Volume 81 (2010), pp. 193-213 | Zbl | MR

[16] De-Xiang Ma; Xue-Gang Chen A note on connected bipartite graphs having independent domination number half their order, Appl. Math. Lett., Volume 17 (2004) no. 8, pp. 959-962 | DOI | MR | Zbl

[17] John D. McFall; Richard Nowakowski Strong independence in graphs, Congr. Numerantium, Volume 29 (1980), pp. 639-656 | MR | Zbl

[18] Gang Zhang; Baoyindureng Wu Domination, independent domination and $k$ -independence in trees, Taiwanese J. Math., Volume 26 (2022) no. 2, pp. 221-231 | DOI | MR | Zbl

[19] Gang Zhang; Baoyindureng Wu 2-independent domination in trees, J. Oper. Res. Soc. China, Volume 12 (2024) no. 2, pp. 485-494 | DOI | MR | Zbl

[20] Shumin Zhang; Tianxia Jia; Minhui Li Partial domination of network modelling, AIMS Math., Volume 8 (2023) no. 10, pp. 24225-24232 | DOI | MR

Cité par Sources :

Commentaires - Politique