On the 2-independence subdivision number of graphs

Document Type : Original paper

Authors

1 Department of Mathematics University of Blida B.P. 270, Blida, Algeria

2 Department of Mathematics, University of Blida 1. B.P. 270, Blida, Algeria

3 Department of Mathematics University of Blida 1, B.P. 270, Blida, Algeria

Abstract

A subset $S$ of vertices in a graph $G=(V,E)$ is $2$-independent if every
vertex of $S$ has at most one neighbor in $S.$ The $2$-independence number
is 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 be
subdivided (each edge in $G$ can be subdivided at most once) in order to
increase the $2$-independence number. We first show that for every connected
graph $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$ attaining
each bound. Moreover, restricted to the class of trees, we provide a
constructive characterization of all trees $T$ with $\mathrm{sd}_{\beta
_{2}}(T)=2,$ and we show that such a characterization suggests an algorithm
that determines whether a tree $T$\ has\textrm{\ }$\mathrm{sd}_{\beta
_{2}}(T)=2$\ or $\mathrm{sd}_{\beta _{2}}(T)=1$\ in polynomial time.

Keywords

Main Subjects

References

[1] M. Atapour, S.M. Sheikholeslami, A. Hansberg, L. Volkmann, and A. Khodkar, 2-domination subdivision number of graphs, AKCE Int. J. Graphs. Combin. 5 (2008), no. 2, 165–173.
[2] M. Atapour, S.M. Sheikholeslami, and A. Khodkar, Roman domination subdivision number of graphs, Aequationes Math. 78 (2009), no. 3, 237–245.
[3] M. Chellali, O. Favaron, A. Hansberg, and L. Volkmann, k-domination and kindependence in graphs: A survey, Graphs Combin. 28 (2012), no. 1, 1–55.
[4] M. Chellali, O. Favaron, T.W. Haynes, and D. Raber, Ratios of some domination parameters in trees, Discrete Math. 308 (2008), no. 17, 3879–3887.
[5] J.F. Fink and M.S. Jacobson, On n-domination, n-dependence and forbidden subgraphs, Graph Theory with Applications to Algorithms and Computer Science, John Wiley and Sons. New York, 1985, pp. 301–311.
[6] T.W. Haynes, S.M. Hedetniemi, and S.T. Hedetniemi, Domination and independence subdivision numbers of graphs, Discuss. Math. Graph Theory 20 (2000), no. 2, 271–280.
[7] T.W. Haynes, S.T. Hedetniemi, and L.C. van des Merwe, Total domination subdivision numbers, J. Combin. Math. Combin. Comput. 44 (2003), no. 3, 115–128.
 
Communications in Combinatorics and Optimization
Volume 7, Issue 1
June 2022
Pages 105-112

Files

Share

How to cite

Statistics