Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651239 | Discrete Mathematics | 2007 | 10 Pages |
Abstract
The gravity of a graph H in a given family of graphs HH is the greatest integer n with the property that for every integer m , there exists a supergraph G∈HG∈H of H such that each subgraph of G, which is isomorphic to H, contains at least n vertices of degree ⩾m⩾m in G . Madaras and Škrekovski introduced this concept and showed that the gravity of the path PkPk on k⩾2k⩾2 vertices in the family of planar graphs of minimum degree 2 is k-2k-2 for each k≠5,7,8,9k≠5,7,8,9. They conjectured that for each of the four excluded cases the gravity is k-3k-3. In this paper we show that this holds.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Z. Dvořák, R. Škrekovski, T. Valla,