Weights of induced subgraphs in -free graphs

Let H be a subgraph of a given graph G . The weight w ( H ) is defined to be the degree sum of the vertices of H in G . Investigations of this parameter are initiated by the result of Kotzig in 1955 who proved that every 3-connected planar graph contains an edge of weight at most 13. In this paper,...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2012-08, Vol.312 (16), p.2429-2432
Main Authors: Pruchnewski, Anja, Voigt, Margit
Format: Article
Language:English
Subjects:
Graphs
Mathematical analysis
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let H be a subgraph of a given graph G . The weight w ( H ) is defined to be the degree sum of the vertices of H in G . Investigations of this parameter are initiated by the result of Kotzig in 1955 who proved that every 3-connected planar graph contains an edge of weight at most 13. In this paper, we seek a bound f depending on some parameters of G and H such that w ( H a2 ) aO f for every induced subgraph H a2 in G isomorphic to H . We obtain the following result for r < 3 : If H is an induced k -colorable subgraph of a K 1 , r -free graph G , and I a is a largest independent set in G , then w ( H ) aO k ( r a 1 ) ( n a I- ( G ) ) a a v a V ( H ) a I a ( ( k a 1 ) ( r a 1 ) a d H ( v ) ) .
ISSN:0012-365X
DOI:10.1016/j.disc.2012.04.025