Independence, odd girth, and average degree | Zendy

Löwenstein, Christian | Zendy; Pedersen, Anders Sune | Zendy; Rautenbach, Dieter | Zendy; Regen Friedrich | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research