how to calculate how many pairwise non-isomorphic graphs can be constructed from graph by adding one new edge. For example graph with 4 vertices.

  • $\begingroup$ A family of graphs is pairwise non-isomorphic if no two of the graphs are isomorphic. They want to know how many different graphs you can get by adding one new edge, where different means not isomorphic. $\endgroup$ – Brian M. Scott Oct 21 '16 at 20:47
  • $\begingroup$ "pairwise non-isomorphic" is another way of writing "they are all different", for some fitting interpretation of the word "different". $\endgroup$ – Arthur Oct 21 '16 at 20:55
  • 1
    $\begingroup$ What is the difference between "pairwise non-isomorphic graphs" and "non-isomorphic graphs"? $\endgroup$ – Del.del Oct 21 '16 at 21:33
  • $\begingroup$ A "family" of graphs is "pairwise non-isomorphic" if for "every" two graphs G and H from that family, G and H are not isomorphic. "Non-isomorphic graphs" are "two" graphs which are not isomorphic. $\endgroup$ – Pegah Pournajafi Oct 21 '16 at 21:56

As mentioned in the comments, a set of graphs (G) is pairwise non-isomorphic if for any pair of graphs (g, h) in G, g is not isomorphic to h.

You have a couple of options (at least). Lets call the starting set of graphs the base set and adding an edge to a graph an augmentation:

  1. Add a new edge everywhere you can for each graph in the base set then filter out duplicates
  2. Determine the symmetries of the graphs in the base set and add new edges to one representative of each attachment point

The first of these options is the easiest for small base sets (equivalently, for graphs on small numbers of vertices). For example, take the square - you can add a new edge to each of the vertices to get a graph on 5 vertices ... but of course all of these augmentations will be pairwise isomorphic.

The difficulty with the second approach is that augmenting different base graphs can lead to the same output graph. For example see this pair of augmentations:

pair of isomorphic augmentations

Of course, you can follow the same procedure as in the first approach of simply filtering out these duplicates, but this becomes computationally expensive for larger graphs. A far better approach is described by Brendan McKay of canonical path augmentation. This involves rejecting augmentations that would lead to non-canonical child graphs, but it's a little long for this answer and described better elsewhere.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.