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.

=================

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.

– Brian M. Scott

2 days ago

“pairwise non-isomorphic” is another way of writing “they are all different”, for some fitting interpretation of the word “different”.

– Arthur

2 days ago

1

What is the difference between “pairwise non-isomorphic graphs” and “non-isomorphic graphs”?

– Del.del

2 days ago

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.

– Pegah Pournajafi

2 days ago

=================

1 Answer

1

=================

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:

Add a new edge everywhere you can for each graph in the base set then filter out duplicates

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:

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.