New approach to the k-independence number of a graph

Home | About RECERCAT | Contact

Català | Castellano

All of RECERCAT

By Communities &
Collections By Defense Date By Authors By Titles By Subject

This Collection

By Defense Date By Authors By Titles By Subject

Statistics

View Statistics All RECERCAT

My RECERCAT

Other repositories directory

RECERCAT Home > Universitat Politècnica de Catalunya > Documents de recerca > View document

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

dc.contributor	Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada III
dc.contributor	Universitat Politècnica de Catalunya. COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions
dc.contributor.author	Caro, Yair
dc.contributor.author	Hansberg Pastor, Adriana
dc.date	2013
dc.identifier.citation	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.
dc.identifier.citation	1077-8926
dc.identifier.uri	http://hdl.handle.net/2117/18603
dc.language.iso	eng
dc.relation	http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i1p33/pdf
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Combinatòria
dc.subject	Average degree
dc.subject	K-independence
dc.title	New approach to the k-independence number of a graph
dc.type	info:eu-repo/semantics/publishedVersion
dc.type	info:eu-repo/semantics/article
dc.description.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].
dc.description.abstract	Peer Reviewed

Show simple item record

All of RECERCAT

This Collection

Statistics

My RECERCAT

Related documents

Other documents of the same author