Does the following graph:

enter image description here

(with graph6 string FFzvO) have a name or belong to a special class?

The DIMACS (bliss) format of it is:

p edge 7 14
e 1 4
e 1 5
e 1 6
e 1 7
e 2 4
e 2 5
e 2 6
e 2 7
e 3 4
e 3 5
e 3 6
e 3 7
e 4 6
e 5 7

And another image, obtained after a permutation of vertices, is:

enter image description here

  • 3
    $\begingroup$ The graph is 4-regular. Are you looking for something more specific? Where does this graph come from? Is there a context where you care about it that's relevant here? $\endgroup$
    – JoshuaZ
    Sep 26 at 17:40
  • 1
    $\begingroup$ I was trying a canonical labeling algorithm and this is the smallest graph where it fails. Maybe another curiosity could be to know if it resembles any category in this list, where the smallest graphs are usually larger than 7 vertices / 14 edges. $\endgroup$
    – BillyJoe
    Sep 26 at 17:49

Looks like it's $\overline{C_3 \cup C_4}$: In your first diagram the vertices 1-2-3 are independent, so the complement of a triangle, and 4-5-6-7 are two independent edges, so the complement of 4-cycle. Every vertex in the co-triangle is adjacent to every vertex in the co-$C_4$.

Edit: Oh, this was supposed to be just a comment.


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.