A quasi-regular graph is a graph such that the vertex degree of every vertex is the same except for a single vertex
whose vertex degree is
(Szádoczki et al. 2022). By the
handshaking lemma, such a graph
necessarily has odd graph
order and odd minimum
vertex degree: if it has
vertices, the sum
of its vertex degrees is
and must be even, so
is odd and hence both
and
are odd.
Quasi-regular graphs with , 5, ..., may be called
quasi-cubic, quasi-quintic,
etc.
For odd , the possible values of
are 1, 3, ...,
. Distinct values of
give distinct degree sequences,
so the total numbers of quasi-regular graphs and connected
quasi-regular graphs are obtained by summing the fixed-
counts over these values. There are
no quasi-regular graphs of even graph
order.
Let
and
denote the numbers of quasi-
graphs and connected
quasi-
graphs on
vertices, respectively, and
let
denote the number of
-regular graphs on
vertices,
with
and
. Every quasi-
graph has a unique component
containing its exceptional vertex, while all remaining
components are
-regular. Consequently,
|
(1)
| |||
|
(2)
| |||
|
(3)
|
where the last identity uses the corresponding ordinary generating functions. The total counts are and
, with the sums
over odd
.
For every odd , the
class consists of the single graph
disjoint union
, where
and
are path graphs. It is connected
only for
. Another disconnected
example is the graph disjoint union
of wheel graph
and tetrahedral
graph
.
For , 5, 7, 9, ..., the numbers of quasi-regular graphs
are 1, 2, 6, 50, 4085, 3289853, ... (OEIS A398642).
The corresponding numbers of connected quasi-regular
graphs are 1, 1, 5, 48, 4078, 3289810, ... (OEIS A398643).
At , the fixed-
contributions for
, 3, 5, 7, 9, and 11 are
1, 1999, 1877695, 1409285, 872, and 1. The corresponding connected
contributions are 0, 1958, 1877694, 1409285, 872, and 1. Hence 43 quasi-regular graphs
on 13 vertices are disconnected,
with fixed-
decomposition
for
, 3, and 5.
At , the fixed-
contributions for
, 3, 5, 7, 9, 11, and 13
are 1, 22186, 1505997049, 48750377244, 903496103, 7815, and 1. The corresponding
connected contributions are 0, 21879, 1505997026,
48750377244, 903496103, 7815, and 1. For
, all these graphs are
connected. Indeed, a disconnected
graph would require a quasi-
component on at
least
vertices and a nonempty
-regular component
on at least
vertices, for a total of at least
vertices. Hence
331 quasi-regular graphs on 15 vertices are disconnected,
with fixed-
decomposition
for
, 3, and 5.