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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

The independent isolation number of a tree

Xinhui An, Baoyindureng Wu, Quanli Hao
Comptes Rendus Mathématique
Advanced Graph Theory Research
article

The independent isolation number of a tree

Xinhui An, Baoyindureng Wu, Quanli Hao
article en

Abstract

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.

Comptes Rendus MathématiqueVol. 363(G12)
Openalex Percentile: Top 68%
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.