Minimum Cycle Bases of Product Graphs

Preprint 01-08-044

Titel:
Minimum Cycle Bases of Product Graphs

Author(s):
Wilfried Imrich and Peter F. Stadler.

Abstract:
A construction for a minimal cycle basis for the Cartesian and the strong product of two graphs from the minimal length cycle bases of the factors is presented. Furthermore, we derive asymptotic expressions for the average length of the cycles in the minimal cycle bases of the powers (iterated products) of graphs. In the limit only triangles and squares play a role.

Keywords:
Cartesian graph product, strong graph product, minimal cycle basis.

AMS Subject Classification: 05C38 [paths and cycles]

Return to 2001 working papers list.