On d-Fibonacci digraphs

C. Dalfó, M.A. Fiol

Abstract


The d-Fibonacci digraphs F(d, k), introduced here, have the number of vertices following some generalized Fibonacci-like sequences. They can be defined both as digraphs on alphabets and as iterated line digraphs. Here we study some of their nice properties. For instance, F(d, k) has diameter d + k − 2 and is semi-pancyclic; that is, it has a cycle of every length between 1 and ℓ, with ℓ ∈ {2k − 2, 2k − 1}. Moreover, it turns out that several other numbers of F(d, k) (of closed l-walks, classes of vertices, etc.) also follow the same linear recurrences as the numbers of vertices of the d-Fibonacci digraphs.


Keywords


n-step Fibonacci number, Fibonacci graph, digraph on alphabet, de Bruijn digraph, line digraph, adjacency matrix, spectrum

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2021.9.2.22

References

M. Aigner, On the linegraph of a directed graph, Math. Z. 102 (1967) 56–61.

C. Balbuena, D. Ferrero, X. Marcote, and I. Pelayo, Algebraic properties of a digraph and its line digraph, J. Interconnect. Networks 4, no. 4, (2003) 377–393.

J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics, Springer-Verlag London, Ltd., London, 2nd. edition, 2009.

G. Chartrand and L. Lesniak, Graphs & Digraphs, Chapman and Hall, third ed., London, 1996.

C. Dalfo, Iterated line digraphs are asymptotically dense, ´ Linear Algebra Appl. 529 (2017) 391–396.

R. Diestel, Graph Theory, Graduate Texts in Mathematics 173, fourth ed., Springer-Verlag, Heilderberg, 2010.

M.A. Fiol, J.L.A. Yebra, and I. Alegre, Line digraph iterations and the (d, k) digraph problem, IEEE Trans. Comput. C-33 (1984) 400–403.

F. Harary and R.Z. Norman, Some properties of line digraphs, Rend. Circ. Mat. Palermo 9, no. 4, (1960) 161–168.

E.P. Miles Jr., Generalized Fibonacci numbers and associated matrices, Amer. Math. Monthly 67, no. 8, (1960) 745–752.

W.-J. Hsu, C.V. Page, and J.-S. Liu, Fibonacci cubes: a class of self-similar graphs, Fib. Quart. 31 (1993) 65–72.

N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences, published on-line at http://oeis.org


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats