The degree sequence of Fibonacci and Lucas cubes |
| |
Authors: | Sandi Klav?ar Michel Mollard Marko Petkovšek |
| |
Institution: | aFaculty of Mathematics and Physics, University of Ljubljana, Slovenia;bFaculty of Natural Sciences and Mathematics, University of Maribor, Slovenia;cCNRS Université Joseph Fourier, Institut Fourier, BP 74, 100 rue des Maths, 38402 St Martin d’Hères Cedex, France |
| |
Abstract: | The Fibonacci cube Γn is the subgraph of the n-cube induced by the binary strings that contain no two consecutive 1’s. The Lucas cube Λn is obtained from Γn by removing vertices that start and end with 1. It is proved that the number of vertices of degree k in Γn and Λn is and , respectively. Both results are obtained in two ways, since each of the approaches yields additional results on the degree sequences of these cubes. In particular, the number of vertices of high resp. low degree in Γn is expressed as a sum of few terms, and the generating functions are given from which the moments of the degree sequences of Γn and Λn are easily computed. |
| |
Keywords: | Fibonacci cube Lucas cube Degree sequence Generating function |
本文献已被 ScienceDirect 等数据库收录! |
|