0
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 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, 2021 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$
    – Fabius Wiesner
    Sep 26, 2021 at 17:49

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.