Constructive characterizations concerning total outer-independent domination in subdivision trees
A. Cabrera-Martínez, J.L. López-Carmona, A. Serrano-Díaz · 2026
Read Constructive characterizations concerning total outer-independent domination in subdivision trees by A. Cabrera-Martínez, J.L. López-Carmona, A. Serrano-Díaz (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-22884.txt.
Introduction
Cabrera-Martínez and co-authors characterize trees that hit known bounds for a domination number. The target is total outer-independent domination in subdivision graphs. A subdivision graph splits each edge of a tree once. Earlier work bounded the domination number using leaf and support counts. This study gives constructive descriptions of the tree families that reach the lower bound. It does the same for the families that reach the upper bound. Such descriptions show exactly which tree shapes are extremal.
Catalog record
| CREATOR | A. Cabrera-Martínez, J.L. López-Carmona, A. Serrano-Díaz |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38709 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.22884
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Constructive characterizations concerning total outer-independent domination in subdivision trees A. Cabrera-Martínez, J.L. López-Carmona, A. Serrano-Díaz Abstract Let G G be a nontrivial connected graph with vertex set V ( G ) V(G) . A set of vertices D ⊆ V ( G ) D\subseteq V(G) is called a total outer-independent dominating set of G G if every vertex of G G is adjacent to at least one vertex in D D , and V ( G ) ∖ D V(G)\setminus D is an independent set of G G . The total outer-independent domination number of G G , denoted by γ t o i ( G ) \gamma_{t}^{oi}(G) , is the minimum cardinality among all total outer-independent dominating sets of G G . The subdivision graph of G G , denoted by 𝚂 ( G ) \mathtt{S}(G) , is the graph obtained from G G by subdividing every edge exactly once. Cabrera-Martínez et al. [On the total outer-independent domination number of subdivision graphs, Comput. Appl. Math. 45 (2026) 315] proved that 4 n ( T ) − l ( T ) − s ( T ) 3 ≤ γ t o i ( 𝚂 ( T ) ) ≤ 4 n ( T ) − l ( T ) + s ( T ) − 2 3 \tfrac{4n(T)-l(T)-s(T)}{3}\leq\gamma_{t}^{oi}(\mathtt{S}(T))\leq\tfrac{4n(T)-l(T)+s(T)-2}{3} for any nontrivial tree T T of order n ( T ) n(T) with l ( T ) l(T) leaves and s ( T ) s(T) support vertices. In this paper, we provide constructive characterizations of the families of trees that attain these bounds. Keywords : total outer-independent domination, subdivision graph, tree. Math. Subj. Class. (2020) : 05C05, 05C69, 05C75. 1 Introduction Let G(V(G),E(G)) be a simple connected graph of order n(G)=|V(G)| . We denote its vertex set by V(G)=\cup_{i\in\{1,\ldots,n(G)\}}\{v_{i}\} , and let us define V_{E}(G)=\{v^{i,j}:v_{i}v_{j}\in E(G)\} (remark that v^{i,j}=v^{j,i} ). Given any vertex v_{i}\in V(G) , N_{G}(v_{i}) represents the open neighborhood of vertex v_{i} , that is, N_{G}(v_{i})=\{v_{j}\in V(G):v_{i}v_{j}\in E(G)\} . A vertex v_{i}\in V(G) is called a leaf of G if |N_{G}(v_{i})|=1 , and v_{i} is a support vertex of G if it is adjacent to a leaf. The sets of leaves and support vertices are denoted by \mathcal{L}(G) and \mathcal{S}(G) , respectively. Moreover, we write l(G)=|\mathcal{L}(G)| and s(G)=|\mathcal{S}(G)| . By convention, for the path P_{2} we assume that one of its two vertices is a support vertex and the other is a leaf. A total outer-independent dominating set (TOIDS) of a nontrivial connected graph G is a set D\subseteq V(G) which satisfies that every vertex of G is adjacent to at least one vertex in D and that V(G)\setminus D is an independent set of G . The total outer-independent domination number of G is defined as \gamma_{t}^{oi}(G)=\min\{|D|:D\text{ is a TOIDS of }G\}. A \gamma_{t}^{oi}(G) - set is a TOIDS of G with cardinality \gamma_{t}^{oi}(G) . The concept of total outer-independent domination in graphs was introduced in 2012 by Soner et al. [ 10 ] , and has subsequently been investigated in several works, including [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ] . Given a nontrivial connected graph G , the subdivision graph \mathtt{S}(G) is obtained from G by subdividing each edge exactly once. Formally, V(\mathtt{S}(G))=V(G)\cup V_{E}(G) and E(\mathtt{S}(G))=\{v_{i}v^{i,j},v_{j}v^{i,j}:v^{i,j}\in V_{E}(G)\} . By definition, it is easy to check that if T is a tree, then \mathtt{S}(T) is also a tree. In Figure 1 we show a tree T and its corresponding graph \mathtt{S}(T) . For each of these two trees, the set of black vertices describes a TOIDS of minimum cardinality. v_{1} v_{2} v_{3} v_{4} v_{5} v_{6} v_{7} T v_{1} v_{2} v_{3} v_{4} v_{5} v_{6} v_{7} v^{1,2} v^{2,3} v^{2,4} v^{4,5} v^{5,6} v^{5,7} \mathtt{S}(T) Figure 1: A tree T , and the corresponding tree \mathtt{S}(T) . Recently, Cabrera-Martínez et al. [ 5 ] provided the following result, which gives lower and upper bounds for the total outer-independent domination number of the subdivision of a nontrivial tree. Theorem 1.1 . [ 5 ] For any nontrivial tree T , \frac{4n(T)-l(T)-s(T)}{3}\leq\gamma_{t}^{oi}(\mathtt{S}(T))\leq\frac{4n(T)-l(T)+s(T)-2}{3}. In this paper, we provide constructive characterizations of the families of trees that attain the bounds given in the previous theorem. 1.1 Additional notation and terminology, and some useful tools We use the notation P_{r} to denote the path graph of order r . Given a graph G , by attaching a path P_{r} to a vertex v_{i}\in V(G) we mean adding the path P_{r} and joining v_{i} by an edge to a leaf of P_{r} . Given a set S\subset V(G) , G-S denotes the graph obtained from G by removing all vertices in S together with all edges incident to them. Next, we define some sets that are relevant to our work. • \mathcal{S}_{s}(G)=\{v_{i}\in\mathcal{S}(G):|N_{G}(v_{i})\cap\mathcal{L}(G)|\geq 2\} is the set of strong support vertices of G . • \mathcal{L}_{s}(G)=\{v_{i}\in\mathcal{L}(G):|N_{G}(v_{i})\cap\mathcal{S}_{s}(G)|=1\} is the set of strong leaves of G . • \mathcal{L}_{w}(G)=\mathcal{L}(G)\setminus\mathcal{L}_{s}(G) is the set of weak leaves of G . • \mathcal{SS}(G)=\{v_{i}\in V(G)\setminus(\mathcal{S}(G)\cup\mathcal{L}(G)):|N_{G}(v_{i})\cap\mathcal{S}(G)|\geq 1\} is the set of semi-support vertices of G . • \mathcal{N}_{SS}(G)=\{v_{i}\in V(G)\setminus(\mathcal{SS}(G)\cup\mathcal{S}(G)):|N_{G}(v_{i})\cap\mathcal{SS}(G)|\geq 1\} is the set of vertices adjacent to semi-support vertices of G that are neither semi-support nor support vertices. A tree T is an acyclic connected graph. A rooted tree T is a tree with a distinguished vertex v_{r} , called the root. Let v_{i}\in V(T)\setminus\{v_{r}\} . A descendant of v_{i} is a vertex v_{j}\neq v_{i} such that the unique v_{r}-v_{j} path contains v_{i} . The set of descendants of v_{i} is denoted by D(v_{i}) . The maximal subtree at v_{i} is the subtree of T induced by D(v_{i})\cup\{v_{i}\} and is denoted by T_{v_{i}} . For an integer r\geq 2 , the tree Q_{r} is defined as the tree obtained from one copy of P_{1} and r copies of P_{3} by joining, with an edge, one leaf of each copy of P_{3} to the vertex of P_{1} . The unique vertex in \mathcal{N}_{SS}(Q_{r}) is called the central vertex of Q_{r} . In Figure 2 we show the tree Q_{3} and its central vertex v_{1} . v_{1} Figure 2: The tree Q_{3} and its central vertex v_{1} . We conclude this section with the following lemmas, which are useful tools in the proofs of the characterizations. Lemma 1.2 . [ 5 ] For any tree T of order at least three, there exists a \gamma_{t}^{oi}(\mathtt{S}(T)) -set D such that \mathcal{S}(T)\cup\mathcal{SS}(T)\subseteq D . Lemma 1.3 . The following statements hold for any nontrivial tree T . (i) If T is obtained from any nontrivial tree T^{\prime} by attaching a path P_{1} to any vertex in \mathcal{S}(T^{\prime}) , then \gamma_{t}^{oi}(\mathtt{S}(T))=\gamma_{t}^{oi}(\mathtt{S}(T^{\prime}))+1 . (ii) If T is obtained from any nontrivial tree T^{\prime} by attaching a path P_{2} to any vertex in \mathcal{S}(T^{\prime})\cup\mathcal{SS}(T^{\prime}) , then \gamma_{t}^{oi}(\mathtt{S}(T))=\gamma_{t}^{oi}(\mathtt{S}(T^{\prime}))+2 . (iii) If T is obtained from any nontrivial tree T^{\prime} by attaching a path P_{3} to any vertex in \mathcal{S}(T^{\prime})\cup\mathcal{L}_{w}(T^{\prime}) , then \gamma_{t}^{oi}(\mathtt{S}(T))=\gamma_{t}^{oi}(\mathtt{S}(T^{\prime}))+4 . (iv) If T is obtained from any nontrivial tree T^{\prime} by identifying the central vertex of the tree Q_{r} with a vertex in \mathcal{L}_{w}(T^{\prime}) , then \gamma_{t}^{oi}(\mathtt{S}(T))=\gamma_{t}^{oi}(\mathtt{S}(T^{\prime}))+4r .