Observability of the extended Fibonacci cubes
type: Item
instance of: scholarly article
title: Observability of the extended Fibonacci cubes
zbMATH Open document ID: 1021.05039
DOI: 10.1016/S0012-365X(02)00824-5
author: Yanyan Li
published in: Discrete Mathematics
publication date: 2003-06-09T00:00:00Z
review text: The Fibonacci cube \(\Gamma_n\) is the subgraph of the hypercube \(Q_n\) induced by the set of Fibonacci strings of order \(n\). By \(\text{obs}(G)\) we mean the minimum number of colours required for a strong edge colouring of \(G\). Let \(i\), \(n\) be positive integers with \(n\geq i+2\). The authors show that \(\text{obs}(\Gamma^i_n)= n+1\) for \(i= 1,2\) and, in general, \(n+ 1\leq \text{obs}(\Gamma^i_n)\leq m+ \lceil i/2\rceil\) where \(\Gamma^i_n\) is the \(i\)th extended Fibonacci cube of order \(n\). For \(i= 3, 4\) this upper bound is sharp. The value of \(\text{obs}(G\times Q_n)\), \(n\geq 2\), for a graph \(G\) containing at most one isolated vertex and no isolated edge is given, too.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1924782
zbMATH Keywords: hypercube
zbMATH Keywords: Fibonacci cube
zbMATH Keywords: edge colouring
zbMATH Keywords: observability
reviewed by: Jozef Fiamčík
MaRDI profile type: Publication
cites work: Vertex-distinguishing proper edge-colorings
cites work: Q4886768
cites work: Q4350166
cites work: The observability of the Fibonacci and the Lucas cubes
cites work: Q4865126
cites work: Asymptotic behaviour of the observability of \(Q_ n\)
cites work: Generalized fibonacci cubes are mostly hamiltonian
cites work: Structural and enumerative properties of the Fibonacci cubes
cites work: Q4863480
description: scientific article; zbMATH DE number 1924782