Premium
Size and independence in triangle‐free graphs with maximum degree three
Author(s) -
Jones Kathryn Fraughnaugh
Publication year - 1990
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.3190140503
Subject(s) - combinatorics , mathematics , independence number , upper and lower bounds , discrete mathematics , degree (music) , graph , independence (probability theory) , triangle free graph , chordal graph , 1 planar graph , statistics , mathematical analysis , physics , acoustics
Let C be the class of triangle‐free graphs with maximum degree at most three. A lower bound for the number of edges in a graph of C is derived in terms of the number of vertices and the independence. Several classes of graphs for which this bound is attained are given. As corollaries, we obtain the best possible lower bound for the independence ratio of a graph in C and evaluate some Ramsey‐type numbers.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom