Observability of the extended Fibonacci cubes
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.
scientific article; zbMATH DE number 1924782