Girth and Independence Ratio

DOI10.4153/CMB-1982-024-9zbMath0436.05033OpenAlexW2333561420MaRDI QIDQ3875951

No author found.

Publication date: 1982

Published in: Canadian Mathematical Bulletin (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4153/cmb-1982-024-9

zbMATH Keywords

girthlower boundscubic graphsindependence ratiomaximum independent sets in graphsp-regular graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Related Items (12)

A compilation of relations between graph invariants—supplement I ⋮ Large independent sets in regular graphs of large girth ⋮ Properties of regular graphs with large girth via local algorithms ⋮ New lower bounds on independence number in triangle-free graphs in terms of order, maximum degree and girth ⋮ Locally Dense Independent Sets in Regular Graphs of Large Girth—An Example of a New Approach ⋮ Cubic graphs with small independence ratio ⋮ Computing independent sets in graphs with large girth ⋮ A note on the independence number of triangle-free graphs. II ⋮ Randomized Greedy Algorithms for Independent Sets and Matchings in Regular Graphs: Exact Results and Finite Girth Corrections ⋮ Induced forests in cubic graphs ⋮ An invariant for minimum triangle-free graphs ⋮ Graphs with unique maximum independent sets

This page was built for publication: Girth and Independence Ratio