On maximum cycle packings in polyhedral graphs

Peter Recht, Stefan Stehling

Abstract


This paper addresses upper and lower bounds for the cardinality of a maximum vertex-/edge-disjoint cycle packing in a polyhedral graph G. Bounds on the cardinality of such packings are provided, that depend on the size, the order or the number of faces of G, respectively. Polyhedral graphs are constructed, that attain these bounds.

Keywords


Maximum cycle packing, polyhedral graphs, vertex-disjoint cycle, edge-disjoint cycle

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2014.2.1.2

Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats