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 sdβ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≤sdβ2(G)≤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 sdβ2(T)=2, and we show that such a characterization suggests an algorithm
that determines whether a tree T\ has\textrm{\ }sdβ2(T)=2\ or sdβ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