The Pell graph is the graph defined as follows. Consider -tuples of such that maximal blocks of an odd number of 2's are forbidden. Take these as the vertices of the graph, and connect vertices with an edge whenever they are equivalent except for the exchange of a single 0 and 1 or a single 11 and 22.
The resulting graph has vertex count and edge count given by
(1)
| |||
(2)
|
where is a Pell number (using the convention that , ; note that Munarini 2019 uses the alternate shifted convention , ) and
(3)
| |||
(4)
|
is the numerator of the th convergent of with a Chebyshev polynomial of the first kind.
Special cases are summarized in the following table.
graph | |
0 | singleton graph |
1 | path graph |
2 | banner graph |
The Pell graphs are bipartite (Munarini 2019) and median graphs (Munarini 2019, Došlić and Podrug 2023). Since the Pell graph is an isometric subgraph of the hypercube for (Munarini 2019), it is also a unit-distance graph. It is also a subgraph of a Fibonacci cube (Munarini 2019).