Premium
Independence, odd girth, and average degree
Author(s) -
Löwenstein, Christian,
Pedersen, Anders Sune,
Rautenbach, Dieter,
Regen Friedrich
Publication year - 2011
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20518
Subject(s) - mathematics , combinatorics , independence number , degree (music) , girth (graph theory) , upper and lower bounds , discrete mathematics , odd graph , independent set , triangle free graph , order (exchange) , graph , extension (predicate logic) , independence (probability theory) , chordal graph , 1 planar graph , statistics , mathematical analysis , physics , finance , acoustics , economics , computer science , programming language
Abstract We prove several tight lower bounds in terms of the order and the average degree for the independence number of graphs that are connected and/or satisfy some odd girth condition. Our main result is the extension of a lower bound for the independence number of triangle‐free graphs of maximum degree at most three due to Heckman and Thomas [Discrete Math 233 (2001), 233–237] to arbitrary triangle‐free graphs. For connected triangle‐free graphs of order n and size m , our result implies the existence of an independent set of order at least (4 n − m −1)/7. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:96‐111, 2011