Minimum cycle bases of lexicographic products

Authors

  • Marc Hellmuth Saarland University, Germany
  • Philipp-Jens Ostermeier Max Planck Institute for Mathematics in the Sciences, Germany
  • Peter F. Stadler University Leipzig, Germany and Max Planck Institute for Mathematics in the Sciences, Germany and Fraunhofer Institut f. Zelltherapie und Immunologie, Germany and University of Vienna, Austria and Santa Fe Institute, United States

DOI:

https://doi.org/10.26493/1855-3974.172.8a7

Keywords:

Cycle space, Cycle basis, lexicographic product

Abstract

Minimum cycle bases of product graphs can in most situations be constructedfrom minimum cycle bases of the factors together with a suitable collectionof triangles and/or quadrangles determined by the product operation. Herewe give an explicit construction for the lexicographic product G o H that generalizes results by Berger and Jaradat to the case that H is notconnected.

Published

2012-03-06

Issue

Section

Articles