Alternate Lucas Cubes

Egecioglu O., SAYGI E., SAYGI Z.

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, vol.32, no.07, pp.871-899, 2021 (SCI-Expanded, Scopus) identifier identifier

  • Publication Type: Article / Article
  • Volume: 32 Issue: 07
  • Publication Date: 2021
  • Doi Number: 10.1142/s0129054121500271
  • Journal Name: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Aerospace Database, Applied Science & Technology Source, Business Source Elite, Business Source Premier, Communication Abstracts, Computer & Applied Sciences, Metadex, zbMATH, Civil Engineering Abstracts
  • Page Numbers: pp.871-899
  • Keywords: Hypercube, Fibonacci cube, Lucas cube, Alternate Lucas cube, FIBONACCI CUBES, HYPERCUBES
  • Hacettepe University Affiliated: Yes

Abstract

We introduce alternate Lucas cubes, a new family of graphs designed as an alternative for the well known Lucas cubes. These interconnection networks are subgraphs of Fibonacci cubes and have a useful fundamental decomposition similar to the one for Fibonacci cubes. The vertices of alternate Lucas cubes are constructed from binary strings that are encodings of Lucas representation of integers. As well as ordinary hypercubes, Fibonacci cubes and Lucas cubes, alternate Lucas cubes have several interesting structural and enumerative properties. In this paper we study some of these properties. Specifically, we give the fundamental decomposition giving the recursive structure, determine the number of edges, number of vertices by weight, the distribution of the degrees; as well as the properties of induced hypercubes, q-cube polynomials and maximal hypercube polynomials. We also obtain the irregularity polynomials of this family of graphs, determine the conditions for Hamiltonicity, and calculate metric properties such as the radius, diameter, and the center.