Article ID Journal Published Year Pages File Type
4649241 Discrete Mathematics 2010 15 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,