Further results on the j-independence number of graphs

Document Type : Original paper

Authors

LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria

Abstract

In a graph G of minimum degree δ and maximum degree Δ, a subset S of vertices of G is j-independent, for some positive integer j, if every vertex in S has at most j−1 neighbors in S. The j-independence number βj(G) is the maximum cardinality of a j-independent set of G. We first establish an inequality between βj(G) and βΔ(G) for 1≤j≤δ−1. Then we characterize all graphs G with βj(G)=βΔ(G) for j∈{1,…,Δ−1}, where the particular cases j=1,2,δ−1 and
δ are well distinguished.

Keywords

Main Subjects

References

[1] M. Chellali, O. Favaron, A. Hansberg, and L. Volkmann, k-domination and k-independence in graphs: A survey, Graphs Combin. 28 (2012), no. 1, 1–55.  https://doi.org/10.1007/s00373-011-1040-3
[2] O. Favaron, k-domination and k-independence in graphs, Ars Combin. 25C (1988), 159–167.
[3] J.F. Fink, n-domination in graphs, Graph Theory with Applications to Algorithms and Computer Science, Wiley, 1985, pp. 282–300.
[4] A. Hansberg, On the k-domination number, the domination number and the cycle of length four, Util. Math. 98 (2015), 65–76.
[5] A. Hansberg, B. Randerath, and . Volkmann, Claw-free graphs with equal 2-domination and domination numbers, Filomat 30 (2016), no. 10, 2795–2801.
[6] M.S. Jacobson, K. Peters, and D.F. Rall, On n-irredundance and n-domination, Ars Combin. 29 (1990), 151–160.
[7] B. Reed, Paths, stars and the number three, Comb. Prob. Comp 5 (1996), no. 3, 277–295. https://doi.org/10.1017/S0963548300002042
Communications in Combinatorics and Optimization
Volume 9, Issue 1
March 2024
Pages 1-11

Files

Share

How to cite

Statistics