Loading...
Loading...

Go to the content (press return)

A note on the order of iterated line digraphs

Author
Dalfo, C.; Fiol, M.
Type of activity
Journal article
Journal
Journal of graph theory
Date of publication
2017-06
Volume
85
Number
2
First page
395
Last page
399
DOI
https://doi.org/10.1002/jgt.22068 Open in new window
Project funding
Tecnicas de optimizacion en teoria de grafos, grupos y combinatoria. aplicaciones a redes, algoritmos y protocolos de comunicacion.
Repository
http://hdl.handle.net/2117/89923 Open in new window
URL
http://onlinelibrary.wiley.com/doi/10.1002/jgt.22068/abstract;jsessionid=6A32980A72E395C78DAD154E46B89E6F.f03t02 Open in new window
Abstract
Given a digraph G, we propose a new method to find the recurrence equation for the number of vertices n_k of the k-iterated line digraph L_k(G), for k>= 0, where L_0(G) = G. We obtain this result by using the minimal polynomial of a quotient digraph pi(G) of G. We show some examples of this method applied to the so-called cyclic Kautz, the unicyclic, and the acyclic digraphs. In the first case, our method gives the enumeration of the ternary length-2 squarefree words of any length.
Citation
Dalfo, C., Fiol, M. A note on the order of iterated line digraphs. "Journal of graph theory", 2017, vol. 85, núm. 2, p. 395-399.
Keywords
Line digraph, adjacency matrix, minimal polynomial, quotient digraph, recurrence, regular partition
Group of research
COMBGRAPH - Combinatorics, Graph Theory and Applications

Participants

Attachments