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, semi-duality.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-41.ps

DIMACS Home Page