TY - JOUR
ID - 14224
TI - On the 2-independence subdivision number of graphs
JO - Communications in Combinatorics and Optimization
JA - CCO
LA - en
SN - 2538-2128
AU - Meddah, NacĂ©ra
AU - Blidia, Mostafa
AU - Chellali, Mustapha
AD - Department of Mathematics
University of Blida
B.P. 270, Blida, Algeria
AD - Department of Mathematics, University of Blida 1.
B.P. 270, Blida, Algeria
AD - Department of Mathematics
University of Blida 1, B.P. 270, Blida, Algeria
Y1 - 2022
PY - 2022
VL - 7
IS - 1
SP - 105
EP - 112
KW - trees
KW - 2-independence
KW - subdivision numbers
DO - 10.22049/cco.2021.27060.1186
N2 - 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, $1leq 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$ hastextrm{ }$mathrm{sd}_{beta_{2}}(T)=2$ or $mathrm{sd}_{beta _{2}}(T)=1$ in polynomial time.
UR - http://comb-opt.azaruniv.ac.ir/article_14224.html
L1 - http://comb-opt.azaruniv.ac.ir/article_14224_e81b235babb9101de9451e1938646d95.pdf
ER -