This is my first question on the mathematics stack exchange. I hope my question is at least a little interesting, then.
In any case, I was reading up on the subgraph isomorphism problem on wikipedia. In a nutshell, we want to check whether a graph 'g' of 'n' vertices is isomorphic to any subset of 'f', where f is a graph of at least 'n' vertices, right?
Obviously, this is a really difficult problem. My question, however, is about whether we can reduce the complexity of this problem by enforcing a standard mechanism of viewing the graphs.
For example, look at the following image:
Here we have an array of empty, ghostlike vertices, to which we can map the individual vertices of any graph. In order to do this, however, we have to follow two rules:
Vertices further south must have more or the same amount of edges than vertices further to the north.
Vertices further east must have more or the same amount of edges than vertices further to the west.
The idea is that, by enforcing a consistent structure over the position of the nodes in any graph, any two graphs can be compared more easily for similarities in structure. In particular, if two graphs have the same structure, then they should occupy the same positions within this enforced scheme, and the edges between them should trace through the same paths.
Obviously, I haven't done any rigorous testing on this. I can't say for certain that if two graphs look identical under this scheme, that they MUST NECESSARILY have the same underlying structure, and therefore, be isomorphic to each other.
Nevertheless, I thought I would post this question as my first one to the website. If any part of the question is unclear, I'll try my best to clarify.
Thanks very much for reading, haha. :D
p.s. Oh, I forgot to mention that the text in the image should read "more than or the same amount". I forgot to put the "same amount" in there, haha.
The structure you speak of can be replaced by the degree sequence of the graphs (see here : http://en.wikipedia.org/wiki/Degree_%28graph_theory%29#Degree_sequence).
If two graphs don't have the same degree sequence, they're not isomorphic.
However, many graphs can have the same degree sequence, in general. But two graphs with the same degree sequence will exhibit the same structure you speak of. So, this structure doesn't give us any information that the degree sequence doesn't.
In fact, that is intuitively why the graph isomorphism problem is difficult. Two graphs can have a similar structure in terms of numbers (e.g. number of edges per nodes) but be different.