1
$\begingroup$

An unlabeled graph is just an isomorphism class of graphs. I am trying to make a way to store an unlabeled graph in a computer without necessarily charactering it with a labeled graph.

For instance, take the labeled graph $G=(V,E)$, where $V=\{A,B,C,D\}$ and $E=\{\{A,B\},\{B,C\},\{B,D\},\{C,D\}\}$. Suppose I want to store this in a computer but without assigning labels to the vertex set, so I am merely storing the structure of the graph.

I know the degree sequence of $G$ is $D=(3,2,2,1)$. From here, I can create an multiset of 2-sets of $D$ that corresponds the edges in $G$: $E'=\{\{1,3\},\{2,3\},\{2,3\},\{2,2\}\}$. Note every 2-set in $E'$ is an edge in $G$, but written in terms of the degrees of the adjacent vertices, rather than the indices of the adjacent vertices. In other words $\{u,v\} \in E \iff \{\deg u, \deg v\} \in E'$.

It is clear any graph isomorphic to $G$ will have this same $E'$. Is it true that every unlabeled graph will have a unique $(D,E')$?

Is this a way to uniquely characterize every unlabeled graph? If not, am I missing something?

$\endgroup$
6
  • $\begingroup$ What do you mean by the "score" of a graph: is this its degree sequence? (And are you creating the multiset by saying, for each edge, the degrees of its endpoints?) $\endgroup$ Nov 20 '20 at 18:48
  • $\begingroup$ @MishaLavrov Yes, by score I mean the degree sequence in non-increasing order. And yes, I am in regards to the multiset. I will edit the thread to clarify. $\endgroup$ Nov 20 '20 at 18:52
  • $\begingroup$ @user21820 (though I expect the ping will not work): I have reverted the edit to the title because that's not what the question is asking. The question is not whether the degree sequence itself uniquely characterizes a graph; the multiset $E'$ also includes information on how many times a vertex of degree $d$ is adjacent to a vertex of degree $d'$ for all $d, d'$. $\endgroup$ Nov 21 '20 at 4:02
  • 1
    $\begingroup$ @MishaLavrov: The ping worked, but I didn't see it just now, sorry. In any case I didn't like the original title because it was completely vague. $\endgroup$
    – user21820
    Nov 21 '20 at 4:07
  • $\begingroup$ @user21820 That's fair, and the new title is much better (I just couldn't think of anything good, which is why I reverted instead of editing again). I didn't know pings worked on users that haven't posted or commented, but I guess editing the question also counts. $\endgroup$ Nov 21 '20 at 4:08
6
$\begingroup$

This approach will not work: in particular, any two $k$-regular $n$-vertex graphs will have the same multiset with $\{k,k\}$ occurring $\frac{kn}{2}$ times. The complete bipartite graph $K_{3,3}$ and the skeleton of a triangular prism are both $3$-regular graphs on $6$ vertices; these are just one of many pairs of graphs you will not be able to distinguish.

In general, if you were hoping for an easy way to do this, you're out of luck, because it would correspond to an easy way to check if two graphs are isomorphic. (We don't currently know of a polynomial-time algorithm to do this.)

If you are looking for a way to do this with software, a graph isomorphism tool such as bliss or nauty can generate a "canonical labeling" for a graph, which will be the same for two isomorphic graphs.

$\endgroup$
5
  • $\begingroup$ You are right, wow. I wonder if this method characterizes connected graphs at least.. $\endgroup$ Nov 20 '20 at 18:57
  • $\begingroup$ The graphs in my example are both connected... $\endgroup$ Nov 20 '20 at 18:58
  • $\begingroup$ You are right, my bad. I know that the brute force method of checking if two graphs are isomorphic is $O(n!n^2)$. Perhaps I can find a characterization that require that many computations, so it wouldn't exactly require finding a polynomial time algorithm. Thank you for your response! $\endgroup$ Nov 20 '20 at 19:00
  • 1
    $\begingroup$ So your ultimate goal is to just have the representation be compact? You're not going to save much over storing a labeled graph: there are $2^{\binom n2}$ labeled graphs, and very approximately $2^{\binom n2}/n!$ unlabeled graphs, which is $\binom n2$ bits vs. $\binom n2 - n \log_2 n$ bits even with a best-case method. $\endgroup$ Nov 20 '20 at 19:05
  • $\begingroup$ No, not a compact representation. Just a representation in general. I'm trying to do something with prime numbers, since such an algorithm will likely have a huge computation. $\endgroup$ Nov 20 '20 at 19:06
1
$\begingroup$

I think your "score" is the degree sequence.

I doubt that the degree sequence characterizes an arbitrary graph.

This is from https://faculty.math.illinois.edu/~kumbhat2/DSFpairs.pdf

The degree sequenced(G) of a graph G is the list (d1,d2,...,dn) of degrees of the vertices o G, written in non increasing order. We say a graph class C has a degree sequence characterization if it is possible to determine whether or not a graph G is in C based solely on the degree sequence of G. Degree sequence characterizations do not exist for most graph classes, but are extremely useful when they do exist.

$\endgroup$
1
  • $\begingroup$ Yes by score, I mean degree sequence. I re-edited the thread with that. You are right that the degree sequence doesn't character graphs. But this isn't just the degree sequence, it is the degree sequence and this augmented edge multiset. $\endgroup$ Nov 20 '20 at 18:56

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.