Light graphs in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight

A graph H is defined to be light in a family H of graphs if there exists a finite number φ ( H , H ) such that each G ∈ H which contains H as a subgraph, contains also a subgraph K ≅ H such that the Δ G ( K ) ≤ φ ( H , H ) . We study light graphs in families of polyhedral graphs with prescribed mini...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2010-06, Vol.310 (12), p.1661-1675
Main Authors: Ferencová, Barbora, Madaras, Tomáš
Format: Article
Language:English
Subjects:
Construction
Edge weight
Graphs
Light graph
Mathematical analysis
Polyhedral graph
Weight reduction
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A graph H is defined to be light in a family H of graphs if there exists a finite number φ ( H , H ) such that each G ∈ H which contains H as a subgraph, contains also a subgraph K ≅ H such that the Δ G ( K ) ≤ φ ( H , H ) . We study light graphs in families of polyhedral graphs with prescribed minimum vertex degree δ , minimum face degree ρ , minimum edge weight w and dual edge weight 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.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2009.11.027