The independent isolation number of a tree
Let <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> be a simple graph. An isolating set of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> is a set <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>I</mml:mi> </mml:math> of vertices such that removing <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>I</mml:mi> </mml:math> and its neighborhood leaves no edge. In addition, the set <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>I</mml:mi> </mml:math> is said to be an independent isolating set of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> if <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>I</mml:mi> </mml:math> is an isolating set of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>[</mml:mo> <mml:mi>I</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> has no edge, where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>[</mml:mo> <mml:mi>I</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> represents the subgraph of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> induced by <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>I</mml:mi> </mml:math> . The independent isolation number of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> , denoted by <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>ι</mml:mi> <mml:mi>i</mml:mi> </mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , is the minimum cardinality of among all independent isolating sets of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> . In this paper, we prove that for every tree <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>T</mml:mi> </mml:math> except a star, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="block"> <mml:mrow> <mml:mfrac> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>(</mml:mo> <mml:mi>T</mml:mi> <mml:mo>)</mml:mo> <mml:mo>-</mml:mo> <mml:mo>|</mml:mo> <mml:mrow> <mml:mi>L</mml:mi> <mml:mo>(</mml:mo> <mml:mi>T</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>|</mml:mo> <mml:mo>-</mml:mo> <mml:mo>|</mml:mo> <mml:mrow> <mml:mi>S</mml:mi> <mml:mo>(</mml:mo> <mml:mi>T</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>|</mml:mo> <mml:mo>+</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> <mml:mn>4</mml:mn> </mml:mfrac> <mml:mo>≤</mml:mo> <mml:msup> <mml:mi>ι</mml:mi> <mml:mi>i</mml:mi> </mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>T</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>≤</mml:mo> <mml:mfrac> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>(</mml:mo> <mml:mi>T</mml:mi> <mml:mo>)</mml:mo> <mml:mo>-</mml:mo> <mml:mo>|</mml:mo> <mml:mrow> <mml:mi>L</mml:mi> <mml:mo>(</mml:mo> <mml:mi>T</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>|</mml:mo> <mml:mo>+</mml:mo> <mml:mn>2</mml:mn> <mml:mo>|</mml:mo> <mml:mrow> <mml:mi>S</mml:mi> <mml:mo>(</mml:mo> <mml:mi>T</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>|</mml:mo> </mml:mrow> <mml:mn>4</mml:mn> </mml:mfrac> <mml:mo>,</mml:mo> </mml:mrow> </mml:math> where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>(</mml:mo> <mml:mi>T</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>L</mml:mi> <mml:mo>(</mml:mo> <mml:mi>T</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>S</mml:mi> <mml:mo>(</mml:mo> <mml:mi>T</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> represent the order, the sets of leaves and support vertices, respectively. Finally, we characterize the extremal trees attaining the bounds.
Authors
- Xinhui An (ORCID: https://orcid.org/0000-0003-2048-0497)
- Baoyindureng Wu (ORCID: https://orcid.org/0000-0001-7164-3116)
- Quanli Hao
Publication Details
- Journal
- Comptes Rendus Mathématique
- Published
- 2025-10-20
- DOI
- https://doi.org/10.5802/crmath.787
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00