TOPICS
Search

Pell Graph


PellGraphs

The Pell graph Pi_n is the graph defined as follows. Consider n-tuples of (0,1,2) 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 Pi_n has vertex count and edge count given by

V(Pi_n)=P_(n+1)
(1)
E(Pi_n)=1/2n(P_n+a_n)
(2)

where P_n is a Pell number P_n (using the convention that P_0=0, P_1=1; note that Munarini 2019 uses the alternate shifted convention p_0=1, p_1=2) and

a_n=((1-sqrt(2))^n+(1+sqrt(2))^n)/2
(3)
=(-1)^nT_n(i)
(4)

is the numerator of the nth convergent of sqrt(2) with T_n(x) a Chebyshev polynomial of the first kind.

Special cases are summarized in the following table.

The Pell graphs are bipartite (Munarini 2019) and median graphs (Munarini 2019, Došlić and Podrug 2023). Since the Pell graph Pi_n is an isometric subgraph of the hypercube Q_(2n-1) for n>=1 (Munarini 2019), it is also a unit-distance graph. It is also a subgraph of a Fibonacci cube (Munarini 2019).


See also

Fibonacci Cube Graph, Lucas Cube Graph, Pell Number

Explore with Wolfram|Alpha

References

Došlić, T. and Podrug, L. "Metallic Cubes." 26 Jul 2023. https://arxiv.org/abs/2307.14054.Munarini, E. "Pell Graphs." Disc. Math. 342, 2415-2428, 2019.

Cite this as:

Weisstein, Eric W. "Pell Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PellGraph.html

Subject classifications