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 βk(G). In this paper, we show that for every graph [xxx], where χ(G), s(G) and Lv 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.
@article{bwmeta1.element.doi-10_7151_dmgt_1677,
author = {Nac\'era Meddah and Mostafa Blidia},
title = {A Characterization of Trees for a New Lower Bound on the K-Independence Number},
journal = {Discussiones Mathematicae Graph Theory},
volume = {33},
year = {2013},
pages = {395-410},
zbl = {1293.05269},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1677}
}
Nacéra Meddah; Mostafa Blidia. A Characterization of Trees for a New Lower Bound on the K-Independence Number. Discussiones Mathematicae Graph Theory, Tome 33 (2013) pp. 395-410. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1677/
[1] S.T. Hedetniemi, Hereditary properties of graphs, J. Combin. Theory (B) 14 (1973) 94-99. doi:10.1016/S0095-8956(73)80009-7[Crossref]
[2] M. Blidia, M. Chellali, O. Favaron and N. Meddah, On k-independence in graphs with emphasis on trees, Discrete Math. 307 (2007) 2209-2216. doi:10.1016/j.disc.2006.11.007[Crossref] | Zbl 1123.05066
[3] M. Borowiecki and D. Michalak, Generalized independence and domination in graphs, Discrete Math. 191 (1998) 51-56. doi:10.1016/S0012-365X(98)00092-2[Crossref] | Zbl 0958.05102
[4] R.L. Brooks, On coloring the nodes of a network, Math. Proc. Cambridge Philos. Soc. 37 (1941) 194-197. doi:10.1017/S030500410002168X[Crossref]
[5] Y. Caro and Z. Tuza, Improved lower bounds on k-independence, J. Graph Theory 15 (1991) 99-107. doi:10.1002/jgt.3190150110[Crossref] | Zbl 0753.68079
[6] O. Favaron, k-domination and k-independence in graphs, Ars Combin. 25 (1988) 159-167. | Zbl 0820.05041
[7] O. Favaron, On a conjecture of Fink and Jacobson concerning k-domination and k-dependence, J. Combin. Theory (B) 39 (1985) 101-102. doi:10.1016/0095-8956(85)90040-1[Crossref] | Zbl 0583.05049
[8] J.F. Fink and M.S. Jacobson, n-domination in graphs, in: Graph Theory with Applications to Algorithms and Computer Science, John Wiley and Sons, New York (1985) 283-300.
[9] J.F. Fink and M.S. Jacobson, n-domination, n-dependence and forbidden subgraphs, in: Graph Theory with Applications to Algorithms and Computer Science, John Wiley and Sons, New York (1985) 301-311.
[10] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998). | Zbl 0890.05002
[11] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, Inc., New York, 1998). | Zbl 0883.00011
[12] L. Volkmann, A characterization of bipartite graphs with independence number half their order , Australas. J. Combin. 41 (2008) 219-222. | Zbl 1185.05112