there are many classes of graphs proved GI complete & many questions related to GI on tcs.se eg [1] & many others.

suppose a class both $X$ and not-$X$ of graphs are proven GI complete. what are the implications of that?

[1] open problems related to GI

  • 2
    $\begingroup$ What do you mean with the class $not-X$ ? Something like: the class of graph that have a certain property $P$ and the class of graphs that don't have that property? In this case I think that for many classes there are no implications at all; for example: $\mathcal{C} = \{ G \mid G \mbox{ has an even number of nodes } \}$ and "$not-{\mathcal{C}}$" are both GI-complete. $\endgroup$ – Vor Dec 20 '13 at 16:34
  • $\begingroup$ @vor for example regular graphs are GI complete. what is the implication if nonregular graphs are also GI complete? etc... is there always "no implication at all"? $\endgroup$ – vzn Dec 20 '13 at 16:47
  • 1
    $\begingroup$ a trivial note: if you pick $ \mathcal{C} = \{ (V, \emptyset) \}$ (the class of graphs with no edges), then if both $\mathcal{C}$ and not-$\mathcal{C}$ are GI-complete then $GI \in P$ $\endgroup$ – Vor Dec 20 '13 at 16:54
  • $\begingroup$ @vor idea, so does it seem to be related to question of whether recognition of the class is in P or NP etc? feel there might be some simple answer but cant quite figure it out immediately $\endgroup$ – vzn Dec 20 '13 at 17:12

Apparently, with graphs of class $X$ and not-$X$ you mean graphs that fulfill a property $X$ and those that don't. It is common that say a graph problem has a different complexity when the input graph is restricted to a certain class of graphs. In this sense, graph isomorphism is no different. As for your question, it is easy to come up with plenty of (even large) classes of graphs. For example, consider graphs that have an even number of vertices, and those that don't. Both are GI-complete, so at least in general, there are no implications.

If this is not satisfying, you need to address what you mean by "non-trivial graphs", but I don't think this would turn out to be too fruitful.

  • $\begingroup$ just take a look at all the classes proved GI complete in the wikipedia link cited. these are all "nontrivial". apparently for none is it known if the class not-$X$ is also GI complete. this seems interesting. it appears there is no nontrivial class known for which both $X$ and not-$X$ are GI complete. $\endgroup$ – vzn Dec 25 '13 at 18:08
  • 1
    $\begingroup$ @vzn Well, consider connected and disconnected graphs (we can trivially make any graph disconnected by adding an isolated vertex). Or consider the class of graphs that have diameter greater than 2 and radius greater than 1... $\endgroup$ – Juho Dec 25 '13 at 18:50

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.