Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
7
1
2022
06
01
On the 2-independence subdivision number of graphs
105
112
14224
10.22049/cco.2021.27060.1186
EN
NacĂ©ra
Meddah
Department of Mathematics
University of Blida
B.P. 270, Blida, Algeria
Mostafa
Blidia
Department of Mathematics, University of Blida 1.
B.P. 270, Blida, Algeria
Mustapha
Chellali
Department of Mathematics
University of Blida 1, B.P. 270, Blida, Algeria
Journal Article
2020
12
24
A subset $S$ of vertices in a graph $G=(V,E)$ is $2$-independent if every<br />vertex of $S$ has at most one neighbor in $S.$ The $2$-independence number<br />is the maximum cardinality of a $2$-independent set of $G.$ In this paper,<br />we initiate the study of the $2$-independence subdivision number $mathrm{sd}%<br />_{beta _{2}}(G)$ defined as the minimum number of edges that must be<br />subdivided (each edge in $G$ can be subdivided at most once) in order to<br />increase the $2$-independence number. We first show that for every connected<br />graph $G$ of order at least three, $1leq mathrm{sd}_{beta _{2}}(G)leq 2,$<br />and we give a necessary and sufficient condition for graphs $G$ attaining<br />each bound. Moreover, restricted to the class of trees, we provide a<br />constructive characterization of all trees $T$ with $mathrm{sd}_{beta<br />_{2}}(T)=2,$ and we show that such a characterization suggests an algorithm<br />that determines whether a tree $T$ hastextrm{ }$mathrm{sd}_{beta<br />_{2}}(T)=2$ or $mathrm{sd}_{beta _{2}}(T)=1$ in polynomial time.
http://comb-opt.azaruniv.ac.ir/article_14224_e81b235babb9101de9451e1938646d95.pdf