Minimum Cycle Bases of Product Graphs
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.
Year of publication: |
2001-08
|
---|---|
Authors: | Imrich, Wilfried ; Stadler, Peter F. |
Institutions: | Santa Fe Institute |
Subject: | Cartesian graph product | strong graph product minimal cycle basis |
Saved in:
Saved in favorites
Similar items by person
-
Cupal, Jan, (1999)
-
Canonical Approximation of Fitness Landscapes
Happel, Robert, (1995)
-
Interchangeability of Relevant Cycles in Graphs
Gleiss, Petra M., (1999)
- More ...