✦ LIBER ✦

On Whitney's 2-isomorphism theorem for graphs

✍ Scribed by K. Truemper

Publisher: John Wiley and Sons
Year: 1980
Tongue: English
Weight: 355 KB
Volume: 4
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190040106

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let G and H be 2‐connected 2‐isomorphic graphs with n nodes. Whitney's 2‐isomorphism theorem states that G may be transformed to a graph G* isomorphic to H by repeated application of a simple operation, which we will term “switching”. We present a proof of Whitney's theorem that is much shorter than the original one, using a graph decomposition by Tutte. The proof also establishes a surprisingly small upper bound, namely n‐2, on the minimal number of switchings required to derive G* from G. The bound is sharp in the sense that for any integer N there exist graphs G and H with n ≥ N nodes for which the minimal number of switchings is n‐2.

📜 SIMILAR VOLUMES

Tellegen's theorem for 2-isomorphic netw

Tellegen's theorem for 2-isomorphic networks

✍ Cel, J. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 51 KB

Let N and N I be directed networks having the same number of branches labelled correspondingly. It is proved that one of them can be reorientated so that u2 i "i2u for all vectors of corresponding branch voltages u, u and currents i, i satisfying Kirchhoff 's voltage and current law in every loop an

A 2-Isomorphism Theorem for Hypergraphs

✍ Dirk Vertigan; Geoff Whittle 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 330 KB

One can associate a polymatroid with a hypergraph that naturally generalises the cycle matroid of a graph. Whitney's 2-isomorphism theorem characterises when two graphs have isomorphic cycle matroids. In this paper Whitney's theorem is generalised to hypergraphs and polymatroids by characterising wh

The divisibility theorem for isomorphic

The divisibility theorem for isomorphic factorizations of complete graphs

✍ Frank Harary; Robert W. Robinson; Nicholas C. Wormald 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 91 KB

On the Isomorphism Problem for Finite Ca

On the Isomorphism Problem for Finite Cayley Graphs of Bounded Valency

✍ C.H. Li; C.E. Praeger 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 187 KB

For a subset S of a group G such that 1 / ∈ S and S = S -1 , the associated Cayley graph Cay(G, S) is the graph with vertex set G such that {x, y} is an edge if and only if yx -1 ∈ S. Each σ ∈ Aut(G) induces an isomorphism from Cay(G, S) to the Cayley graph Cay(G, S σ ). For a positive integer m, th

Menger's theorem for infinite graphs wit

Menger's theorem for infinite graphs with ends

✍ Henning Bruhn; Reinhard Diestel; Maya Stein 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

## Abstract A well‐known conjecture of Erdős states that given an infinite graph __G__ and sets __A__, ⊆ __V__(__G__), there exists a family of disjoint __A__ − __B__ paths 𝓅 together with an __A__ − __B__ separator __X__ consisting of a choice of one vertex from each path in 𝓅. There is a natural

On greene's theorem for digraphs

✍ Irith Ben-Arroyo Hartman; Fathi Saleh; Daniel Hershkowitz 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 328 KB

## Abstract Greene's Theorem states that the maximum cardinality of an optimal __k__‐path in a poset is equal to the minimum __k__‐norm of a __k__‐optimal coloring. This result was extended to all acyclic digraphs, and is conjectured to hold for general digraphs. We prove the result for general dig