On Ulam’s conjecture for separable graphs
J. Adrian Bondy · Pacific Journal of Mathematics · 1969
Ulam's conjecture, that every graph of order greater than two is determined up to isomorphism by its collection of maximal subgraphs, is verified for the case of separable graphs which have no pendant vertices.Partial results are then obtained for the case of graphs with pendant vertices.Unless otherwise stated, the graphs dealt with in this paper will be finite and undirected, and may have loops and multiple edges.Any definitions and notation not given below can be found in Berge [1].A part G ι of a graph G is a subset of the vertices and edges1 and all edges of G which are joined to vertices of G 1 .Now let S be some distinguished set of parts of a graph, and let S(X) -{X 1 } be the labelled set of these parts in the graph X We call two graphs G,G\ H ι will be referred to as corresponding parts.In [8] Ulam proposed the following conjecture.CONJECTURE A. Vertex-equivalent graphs of order greater than two are isomorphic.Kelly [7] verified this conjecture for trees and, by exhaustion, for all graphs up to order seven.A related conjecture, intuitively simpler but also as yet unsolved, was suggested by Harary [4].CONJECTURE B. Edge-equivalent graphs with more than three edges are isomorphic.