Carregant...
Carregant...

Vés al contingut (premeu Retorn)

New approach to the k-independence number of a graph

Autor
Caro, Y.; Hansberg, A.
Tipus d'activitat
Article en revista
Revista
Electronic journal of combinatorics
Data de publicació
2013
Volum
20
Número
1
Pàgina inicial
1
Pàgina final
16
Repositori
http://hdl.handle.net/2117/18603 Obrir en finestra nova
URL
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i1p33/pdf Obrir en finestra nova
Resum
Let G = (V,E) be a graph and k > 0 an integer. A k-independent set S V is a set of vertices such that the maximum degree in the graph induced by S is at most k. With k(G) we denote the maximum cardinality of a k-independent set of G. We prove that, for a graph G on n vertices and average degree d, k(G) > k+1 dde+k+1n, improving the hitherto best general lower bound due to Caro and Tuza [Improved lower bounds on k-independence, J. Graph Theory 15 (1991), 99–107].
Citació
Caro, Y.; Hansberg, A. New approach to the k-independence number of a graph. "Electronic journal of combinatorics", 2013, vol. 20, núm. 1, p. 1-16.
Paraules clau
Average degree, K-independence
Grup de recerca
COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions

Participants

  • Caro, Yair  (autor)
  • Hansberg Pastor, Adriana  (autor)

Arxius