A Characterization of Trees for a New Lower Bound on the K-Independence Number

Nacéra Meddah; Mostafa Blidia

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 2, page 395-410
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Nacéra Meddah, and Mostafa Blidia. "A Characterization of Trees for a New Lower Bound on the K-Independence Number." Discussiones Mathematicae Graph Theory 33.2 (2013): 395-410. <http://eudml.org/doc/267566>.

@article{NacéraMeddah2013,
abstract = {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.},
author = {Nacéra Meddah, Mostafa Blidia},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {domination; independence; k-independence; -independence},
language = {eng},
number = {2},
pages = {395-410},
title = {A Characterization of Trees for a New Lower Bound on the K-Independence Number},
url = {http://eudml.org/doc/267566},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Nacéra Meddah
AU - Mostafa Blidia
TI - A Characterization of Trees for a New Lower Bound on the K-Independence Number
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 2
SP - 395
EP - 410
AB - 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.
LA - eng
KW - domination; independence; k-independence; -independence
UR - http://eudml.org/doc/267566
ER -

References

top
  1. [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. [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] Zbl1123.05066
  3. [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] Zbl0958.05102
  4. [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. [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] Zbl0753.68079
  6. [6] O. Favaron, k-domination and k-independence in graphs, Ars Combin. 25 (1988) 159-167. Zbl0820.05041
  7. [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] Zbl0583.05049
  8. [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. [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. [10] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998). Zbl0890.05002
  11. [11] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, Inc., New York, 1998). Zbl0883.00011
  12. [12] L. Volkmann, A characterization of bipartite graphs with independence number half their order , Australas. J. Combin. 41 (2008) 219-222. Zbl1185.05112

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.