Fibonacci-run graphs. II: Degree sequences

DOI10.1016/J.DAM.2021.05.018MaRDI QIDQ2030245zbMATH OpenOpenAlexFDO

Authors Ömer Eğecioğlu, Vesna Iršič

Publication date 7 June 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2010.05521

zbMATH Keywords

degree sequenceFibonacci cubeFibonacci-run graphgenerating function

Mathematics Subject Classification ID

Vertex degrees (05C07) Enumeration in graph theory (05C30)

Abstract: Fibonacci cubes are induced subgraphs of hypercube graphs obtained by restricting the vertex set to those binary strings which do not contain consecutive 1s. This class of graphs has been studied extensively and generalized in many different directions. Induced subgraphs of the hypercube on binary strings with restricted runlengths as vertices define Fibonacci-run graphs. These graphs have the same number of vertices as Fibonacci cubes, but fewer edges and different graph theoretical properties. Basic properties of Fibonacci-run graphs are presented in a companion paper, while in this paper we consider the nature of the degree sequences of Fibonacci-run graphs. The generating function we obtain is a refinement of the generating function of the degree sequences, and has a number of corollaries, obtained as specializations. We also obtain several properties of Fibonacci-run graphs viewed as a partially ordered set, and discuss its embedding properties.

Recommendations

• Fibonacci-run graphs. I: Basic properties
• The degree sequence of Fibonacci and Lucas cubes
• The Fibonacci hypercube
• Structure of Fibonacci cubes: a survey
• Generalized Fibonacci cubes

Cites work

• \(q\)-cube enumerator polynomial of Fibonacci cubes
• Boundary enumerator polynomial of hypercubes in Fibonacci cubes
• Fibonacci-run graphs. I: Basic properties
• How Not to Repeatedly Differentiate a Reciprocal
• scientific article; zbMATH DE number 1409213 (Why is no real title available?)
• Non covered vertices in Fibonacci cubes by a maximum set of disjoint hypercubes
• On domination-type invariants of Fibonacci cubes and hypercubes
• On the irregularity of \(\pi \)-permutation graphs, Fibonacci cubes, and trees
• Some diameter notions of Fibonacci cubes
• Statistics on restricted Fibonacci words
• Structure of Fibonacci cubes: a survey
• The degree sequence of Fibonacci and Lucas cubes
• The irregularity polynomials of Fibonacci and Lucas cubes

Cited in

(10)

• The radius and center of Fibonacci-run graphs
• Gray codes for Fibonacci \(q\)-decreasing words
• Fibonacci-run graphs. I: Basic properties
• Generating cyclic 2-Gray codes for Fibonacci q-decreasing words
• Lucas-run graphs
• A note on the cube polynomials of Fibonacci and Lucas-Run graphs
• Distance cube polynomials of Fibonacci and Lucas-run graphs
• Associated Mersenne graphs
• On a conjecture of Eǧecioǧlu and Iršič
• Generating a cyclic 2-Gray code for Lucas words in constant amortized time

This page was built for publication: Fibonacci-run graphs. II: Degree sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2030245)