Premium
On weights of induced paths and cycles in claw‐free and K 1 ,r ‐free graphs
Author(s) -
Harant J.,
Voigt M.,
Jendrol S.,
Randerath B.,
Ryjáček Z.,
Schiermeyer I.
Publication year - 2001
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/1097-0118(200103)36:3<131::aid-jgt1001>3.0.co;2-o
Subject(s) - combinatorics , mathematics , corollary , graph , upper and lower bounds , induced path , independence number , claw , discrete mathematics , chordal graph , longest path problem , mechanical engineering , mathematical analysis , engineering
Let G be a K 1, r ‐free graph ( r ≥ 3) on n vertices. We prove that, for any induced path or induced cycle on k vertices in G ( k ≥ 2 r − 1 or k ≥ 2 r , respectively), the degree sum of its vertices is at most (2 r − 2)( n − α) where α is the independence number of G . As a corollary we obtain an upper bound on the length of a longest induced path and a longest induced cycle in a K 1, r ‐free graph. Stronger bounds are given in the special case of claw‐free graphs (i.e., r = 3). Sharpness examples are also presented. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 131–143, 2001