Kakan graphs

1 Definition

We study a special kind of degree irregularity.

Definition 1. A graph G is a Kakan graph if it (i) contains no vertices of degree 0, and (ii) no pair of non-adjacent vertices in G have the same degree.

Source code for the Kakan graph project may be found in this Github repository.

2 Enumeration

For small orders we have generated all Kakan graphs. The graphs are listed in graph6-format on the Github:

n = 2	(1 graph)
n = 3	(1 graph)
n = 4	(2 graphs)
n = 5	(5 graphs)
n = 6	(16 graphs)
n = 7	(70 graphs)
n = 8	(498 graphs)
n = 9	(6057 graphs)
n = 10	(133686 graphs)

3 Problems

Problem 1. For any given natural number $n$, what is the number of Kakan graphs on $n$ vertices?