Cycle lengths and circuit matroids of graphs (Q1199495)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Cycle lengths and circuit matroids of graphs |
scientific article |
Statements
Cycle lengths and circuit matroids of graphs (English)
0 references
16 January 1993
0 references
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.
0 references
chain group
0 references
circuit chain
0 references
cycle groups
0 references
circuit matroids
0 references