Lucas Cube Graph


A Lucas cube graph of order n is a graph that can be defined based on the n-Fibonacci cube graph by forbidding vertex strings that have a 1 both in the first and last positions. Explicitly, it is a graph on the subset of (0,1) n-tuples that are cyclically free of adjacent 1's (i.e., consecutive 1's cannot occur in the middle of the string and 1's cannot be present in both first and last positions of the string), with vertices connected by edges iff they differ in exactly one position.

Munarini et al. (2001) determined many structural and enumerative properties of the Lucas cubes.

The nth Lucas cube graph is denoted L_n (Munarini et al. 2001) or Lambda_n (Ilić al 2012, Ilić and Milošević 2017).

Special cases are summarized in the following table.

L_n has vertex count equal to the Lucas number L_n.

The Lucas cube graphs are median graphs (Klavžar 2005, Došlić and Podrug 2023). The are also unit-distance.

See also

Fibonacci Cube Graph, Lucas Number, Pell Graph

Explore with Wolfram|Alpha


Castro, A.; Klavžar, S.; Mollard, M.; and Rho, T. "On the Domination Number and the 2-Packing Number of Fibonacci Cubes and Lucas Cubes." Comput. Math. Appl. 61, 2655-2660, 2011.Castro, A. and Mollard, M. "The Eccentricity Sequences of Fibonacci and Lucas Cubes." Disc. Math. 312, 1025-1037, 2012.Dedò, E.; Torri, D.; and Salvi, N. Z. "The Observability of the Fibonacci and the Lucas Cubes." Disc. Math. 255, 55-63, 2002.Došlić, T. and Podrug, L. "Metallic Cubes." 26 Jul 2023.ć, A. and Milošević, M. "The Parameters of Fibonacci and Lucas Cubes." Ars Math. Contemp. 12, 25-29, 2017.Ilić, A.; Klavžar, S.; and Rho, Y. "Generalized Lucas Cubes." Appl. Analysis Discr. Math. 6, 82-94, 2012.Klavžar, S. "On Median Nature and Enumerative Properties of Fibonacci-Like Cubes." Disc. Math. 299, 145-153, 2005.Klavžar, S.; Mollard, M.; and Petkovšek, M. "The Degree Sequence of Fibonacci and Lucas Cubes." Disc. Math. 311, 1310-1322, 2001.Munarini, E.; Cippo, C. P.; and Salvi, Z. N. "On the Lucas Cubes." Fibonacci Quart. 39, 12-21, 2001.

Cite this as:

Weisstein, Eric W. "Lucas Cube Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications