@article {
author = {Meddah, NacĂ©ra and Blidia, Mostafa and Chellali, Mustapha},
title = {On the 2-independence subdivision number of graphs},
journal = {Communications in Combinatorics and Optimization},
volume = {7},
number = {1},
pages = {105-112},
year = {2022},
publisher = {Azarbaijan Shahid Madani University},
issn = {2538-2128},
eissn = {2538-2136},
doi = {10.22049/cco.2021.27060.1186},
abstract = {A subset $S$ of vertices in a graph $G=(V,E)$ is $2$-independent if everyvertex of $S$ has at most one neighbor in $S.$ The $2$-independence numberis the maximum cardinality of a $2$-independent set of $G.$ In this paper,we initiate the study of the $2$-independence subdivision number $\mathrm{sd}%_{\beta _{2}}(G)$ defined as the minimum number of edges that must besubdivided (each edge in $G$ can be subdivided at most once) in order toincrease the $2$-independence number. We first show that for every connectedgraph $G$ of order at least three, $1\leq \mathrm{sd}_{\beta _{2}}(G)\leq 2,$and we give a necessary and sufficient condition for graphs $G$ attainingeach bound. Moreover, restricted to the class of trees, we provide aconstructive characterization of all trees $T$ with $\mathrm{sd}_{\beta_{2}}(T)=2,$ and we show that such a characterization suggests an algorithmthat determines whether a tree $T$\ has\textrm{\ }$\mathrm{sd}_{\beta_{2}}(T)=2$\ or $\mathrm{sd}_{\beta _{2}}(T)=1$\ in polynomial time.},
keywords = {trees,2-independence,subdivision numbers},
url = {http://comb-opt.azaruniv.ac.ir/article_14224.html},
eprint = {http://comb-opt.azaruniv.ac.ir/article_14224_e81b235babb9101de9451e1938646d95.pdf}
}