New approach to the k-independence number of a graph

All of RECERCAT

To access the full text documents, please follow this link: http://hdl.handle.net/2117/18603

Title:	New approach to the k-independence number of a graph
Author:	Caro, Yair; Hansberg Pastor, Adriana
Other authors:	Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada III; Universitat Politècnica de Catalunya. COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions
Abstract:	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].
Abstract:	Peer Reviewed
Subject(s):	-Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Combinatòria -Average degree -K-independence
Rights:
Document type:	Article - Published version Article
Share: