A short proof of Shih's isomorphism theorem on graphic subspaces (Q2663417)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A short proof of Shih's isomorphism theorem on graphic subspaces |
scientific article |
Statements
A short proof of Shih's isomorphism theorem on graphic subspaces (English)
0 references
16 April 2021
0 references
The authors reprove the result by \textit{C. H. Shih} [On graphic subspaces of graphic spaces. Columbus, OH: Ohio State University (PhD Thesis) (1982)], characterizing the relationship between two graphs, where the cycle space of the first is included in the cycle space of the second and the dimension of the cycle spaces differ by one. This is a generalization of the following result of \textit{H. Whitney} [Am. J. Math. 55, 245--254 (1933; Zbl 0006.37005)]: \par Let \(G\) and \(H\) be graphs on the same edge sets. Then \( \mathrm{cycle}(G) = \mathrm{cycle}(H)\), or equivalently \(\mathrm{cut}(G) = \mathrm{cut}(H)\), if and only if \(G\) and \(H\) are equivalent.\par Here, graphs that are related by a sequence of so-called Whitney-flips are called equivalent.\par A weaker form of the main result reads as follows.\par Let \(G, H\) be graphs with \(E(G) = E(H)\), where \(\mathrm{cycle}(G)\subset \mathrm{cycle}(H)\) and \par \(\dim(cycle\mathrm{cycle}(G)) = \dim(\mathrm{cycle}(H))-1\). Then, there exist \(G^\prime\) equivalent to \(G\) and \(H^\prime\) equivalent to \(H\) such that: \par a) \(H^\prime\) is obtained from \(G^\prime\) by identifying two distinct vertices, or \par b) \(G^\prime, H^\prime\) is a so-called wheel pair, or \par c) \(G^\prime, H^\prime\) is a so-called widget pair. \par Moreover, the authors mention applications to even-cycle matroids, even-cut matroids and frame matroids. For example: Any two signed-graph representations of a graphic even-cycle matroid are related by a sequence of Whitney-flips, Lovász-flips, and resignings.
0 references
cycle space
0 references
Whitney-flip
0 references
equivalent graphs
0 references
matroid
0 references