Lucas-Run Graphs

In this paper, a new sub-family of Hypercubes called the Lucas-run graphs \({\mathcal {R}}^{l}_{n}\) ${\mathcal{R}}_n^l$ are introduced. The name of this new family of graphs is identified with the interesting fact that \(|V({\mathcal {R}}^{l}_{n})|\) $|V({\mathcal{R}}_n^l)|$ is equal to the n-th Lucas number. The definition of Lucas-run graph is motivated by the Fibonacci-run graph (Eǧecioǧlu and Iršič in Discrete Appl Math 295:70–84, 2021a; in Discrete Appl Math 300:56–71, 2021b). Various interesting structural and enumerative properties of Lucas-run graphs are investigated, including the analogue of the fundamental recursion, number of vertices and edges, radius, center, diameter and medianicity. Some future research directions and open problems concerning Lucas-run graphs are also proposed.