Weights of induced subgraphs in K-1,K-r-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, we seek a bound f depending on some parameters of G and H such that w(H') <= f for every induced subgraph H' 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,K-r-free graph G, and I* is a largest independent set in G, then w(H) <= k(r - 1)(n - alpha(G)) - Sigma(v is an element of V(H)-I*) (k - 1) (r - 1) - d(H)(v)). Moreover, we give some sharpness examples. (C) 2012 Elsevier B.V. All rights reserved.

VIVO