Further results on the j-independence number of graphs

Document Type : Original paper

Authors

1 University of Médéa, Algeria

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

Abstract

In a graph $G$ of minimum degree $\delta$ and maximum degree $\Delta$, 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 $\beta_{j}(G)$ is the maximum cardinality of a $j$-independent set of $G$. We first establish an inequality between $\beta_{j}(G)$ and $\beta_{\Delta}(G)$ for $1\leq j\leq\delta-1$. Then we characterize all graphs $G$ with $\beta_{j}(G)=\beta_{\Delta}(G)$ for $j\in\{1,\dots,\Delta-1\}$, where the particular cases $j=1,2,\delta-1$ and
$\delta$ 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