Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649241 | Discrete Mathematics | 2010 | 15 Pages |
Abstract
A graph HH is defined to be light in a family HH of graphs if there exists a finite number φ(H,H)φ(H,H) such that each G∈HG∈H which contains HH as a subgraph, contains also a subgraph K≅HK≅H such that the ΔG(K)≤φ(H,H)ΔG(K)≤φ(H,H). We study light graphs in families of polyhedral graphs with prescribed minimum vertex degree δδ, minimum face degree ρρ, minimum edge weight ww and dual edge weight w∗w∗. For those families, we show that there exists a variety of small light cycles; on the other hand, we also present particular constructions showing that, for certain families, the spectrum of short cycles contains irregularly scattered cycles that are not light.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Barbora Ferencová, Tomáš Madaras,