In this paper, we introduce the Pell graphs, a new family of graphs similar to the Fibonacci cubes. They are defined on certain ternary strings (Pell strings) and turn out to be subgraphs of Fibonacci cubes of odd index. Moreover, as well as ordinary hypercubes and Fibonacci cubes, Pell graphs have several interesting structural and enumerative properties. Here, we determine some of them. Specifically, we obtain a canonical decomposition giving a recursive structure, some basic properties (bipartiteness and existence of maximal matchings), some metric properties (radius, diameter, center, periphery, medianicity), some properties on subhypercubes (cube coefficients and polynomials, cube indices, decomposition in subhypercubes), and, finally, the distribution of the degrees.

Pell graphs

E. Munarini
2019-01-01

Abstract

In this paper, we introduce the Pell graphs, a new family of graphs similar to the Fibonacci cubes. They are defined on certain ternary strings (Pell strings) and turn out to be subgraphs of Fibonacci cubes of odd index. Moreover, as well as ordinary hypercubes and Fibonacci cubes, Pell graphs have several interesting structural and enumerative properties. Here, we determine some of them. Specifically, we obtain a canonical decomposition giving a recursive structure, some basic properties (bipartiteness and existence of maximal matchings), some metric properties (radius, diameter, center, periphery, medianicity), some properties on subhypercubes (cube coefficients and polynomials, cube indices, decomposition in subhypercubes), and, finally, the distribution of the degrees.
2019
Hypercube, Fibonacci cube, Bipartite graph, Median graph, Subhypercube
File in questo prodotto:
File Dimensione Formato  
11311-1088084_Munarini.pdf

accesso aperto

: Pre-Print (o Pre-Refereeing)
Dimensione 358.27 kB
Formato Adobe PDF
358.27 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/1088084
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 6
social impact