Article ID Journal Published Year Pages File Type
4646892 Discrete Mathematics 2014 5 Pages PDF
Abstract
We prove that each {claw, K4}-free 4-regular graph, with just one class of exceptions, is a line graph. Applying this result, we present lower bounds on the independence numbers for {claw, K4}-free 4-regular graphs and for {claw, diamond}-free 4-regular graphs. Furthermore, we characterize the extremal graphs attaining the bounds.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,