General versus connected versions

Description

Given a graph property $p$ which can be polynomial-time tested for graphs, the graph isomorphism problem for graphs with property $p$ is the problem of checking whether two graphs, both of which satisfy property $p$, are isomorphic.

The connected version is the problem of asking whether two graphs, both of which are connected and satisfy property $p$, are isomorphic.

For a complement-closed graph property

Suppose $p$ is a graph property such that the complement of any graph with property $p$ also has property $p$. Then, we can pass from the general version to the connected version as follows:

• Check for each graph whether it is connected
• If one graph is connected and the other is not, then the two graphs are isomorphic
• If both are connected, the problem reduces to the connected version
• If neither is connected, take the complements of both graphs. We know that either a graph or its complement must be connected. Hence, the two complement graphs are graphs with property $p$ which are connected. Appeal to the connected version for each.

For a component-closed property

Suppose $p$ is a graph property such that every connected component of any grpah with proeprty $p$ also has property $p$. Then we can do the following:

• Split both graphs into their connected components
• Pick one connected component of the first graph. Traverse all the connected components of the second graph, and check for each whether it is isomorphic to this connected component. (for this, appeal to the connected version). If none of them is isomorphic, then the two graphs are not isomorphic. Otherwise remove the isomorphic pair from both and inductively proceed with the rest.