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
    0 references
    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
    0 references

    Identifiers