DIMACS TR: 93-41
On Edge Bijections of Graphs
Author: A. K. Kelmans
Let G_1 and G_2 be undirected graphs, and F_1(G_1) and
F_2(G_2) be families of edge sets of G_1 and G_2, respectively.
An ( F_1, F_2)-semi-isomorphism of G_1 onto G_2 is an edge
bijection between G_1 and G_2 that induces an injection from
F_1(G_1) to F_2(G_2). This concept generalizes a well known
concept of a circuit isomorphism of graphs due to H. Whitney.
If F_1(G_1) has a "dual nature" with respect to F_2(G_2)
then the concept of ( F_1, F_2)-semi-isomorphism of graphs
turns into a concept of an ( F_1, F_2)-semi-duality of graphs.
This gives a natural generalization of the circuit duality of
graphs due to H.Whitney.
In this paper we investigate ( F_1, F_2)-semi-isomorphisms
and ( F_1, F_2)-semi-dualities of graphs for verious families
F_1(G_1) and F_2(G_2). In particular, we consider families of
circuits and cocircuits of graphs from this point of view, and
obtain some strengthenings of Whitney's 2-isomorphism theorem
and Whitney's planarity criterion for 3-connected graphs.
KEYWORDS: graph, matroid, circuit, cocircuit, non-separating
circuit, non-separating cocircuit, planarity, semi-isomorphism,
Paper available at:
DIMACS Home Page