Cycle lengths and circuit matroids of graphs
type: Item
instance of: scholarly article
title: Cycle lengths and circuit matroids of graphs
zbMATH Open document ID: 0764.05038
DOI: 10.1016/0012-365X(92)90149-A
published in: Discrete Mathematics
publication date: 1993-01-16T00:00:00Z
review text: For a graph \(G\) with edges \(e_ 1\), \(e_ 2,\dots,e_ m\) choose one of the two orientations of \(e_ i\) \((i=1,2,\dots,m)\) at random. The chain group \(C(\vec G)\) of the oriented graph \(\vec G\) is the free abelian group with the oriented edges \(\vec e_ 1\), \(\vec e_ 2,\dots,\vec e_ m\) as generators; its elements are \(c=\sum c_ ie_ i\) \((c_ 1,\dots,c_ m\) are integers, \(\sum^ m_{i=1}| c_ i|\) is the length of \(c)\). For each circuit \(C\) of \(G\), choose one of the two orientations of \(C\) at random so that it defines a circuit chain. Let \(Z(\vec G)\) be the subgroup of \(C(\vec G)\) generated by the circuit chains. \(Z(\vec G)\) is called the cycle group of \(G\). The purpose of the paper is to prove the following result: Let \(G\) and \(H\) be graphs without cut-edges. Then there is a length preserving group-isomorphism between the cycle groups of \(G\) and \(H\) iff \(G\) and \(H\) have isomorphic circuit matroids.
Mathematics Subject Classification ID: 05C25
Mathematics Subject Classification ID: 05B35
zbMATH DE Number: 94364
zbMATH Keywords: chain group
zbMATH Keywords: circuit chain
zbMATH Keywords: cycle groups
zbMATH Keywords: circuit matroids
author: Douglas R. Woodall
reviewed by: Ulrike Baumann
MaRDI profile type: Publication
cites work: Q3050437
cites work: Cycle Lengths and Graph Orientations
cites work: Lectures on matroids
cites work: Q4111952
full work available at URL: 0012-365x(92)90149-a
OpenAlex ID: W1992566020
description: scientific article; zbMATH DE number 94364