×

A characterization of trees for a new lower bound on the \(k\)-independence number. (English) Zbl 1293.05269

Summary: Let \(k\) be a positive integer and \(G = (V,E)\) a graph of order \(n\). A subset \(S\) of \(V\) is a \(k\)-independent set of \(G\) if the maximum degree of the subgraph induced by the vertices of \(S\) is less or equal to \(k-1\). The maximum cardinality of a \(k\)-independent set of \(G\) is the \(k\)-independence number \(\beta_k(G)\).
In this paper, we show that for every graph \(G\), \(\beta_k(G)\geq \lceil (n+( \chi (G)-1)\sum_{v\in S(G)}\min(|L_v| ,k-1))/\chi(G)\rceil\), where \(\chi (G)\), \(s(G)\) and \(L_v\) are the chromatic number, the number of supports vertices and the number of leaves neighbors of \(v\), in the graph \(G\), respectively. Moreover, we characterize extremal trees attaining these bounds.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: DOI