Unfoldings and Coverings of Weighted Graphs

Article type: Research Article

Authors: Courcelle, Bruno^{; *}

Affiliations: LaBRI, CNRS (UMR 5800), University of Bordeaux, France, courcell@labri.fr

Correspondence: [*] Address for correspondence: Bordeaux University, LaBRI, F-33400 Talence, France.

Abstract: Coverings of undirected graphs are used in distributed computing, and unfoldings of directed graphs in semantics of programs. We study these two notions from a graph theoretical point of view so as to highlight their similarities, as they are both defined in terms of surjective graph homomorphisms. In particular, universal coverings and complete unfoldings are infinite trees that are regular if the initial graphs are finite. Regularity means that a tree has finitely many subtrees up to isomorphism. Two important theorems have been established by Leighton and Norris for coverings of finite graphs. We prove similar results for unfoldings of finite directed graphs. Moreover, we generalize coverings and similarly, unfoldings to graphs and digraphs equipped with finite or infinite weights attached to edges of the covered or unfolded graphs. This generalization yields a canonical “factorization” of the universal covering of any finite graph, that (provably) does not exist without using weights. Introducing ω as an infinite weight provides us with finite descriptions of regular trees having nodes of countably infinite degree. Regular trees (trees having finitely many subtrees up to isomorphism) play an important role in the extension of Formal Language Theory to infinite structures described in finitary ways. Our weighted graphs offer effective descriptions of the above mentioned regular trees and yield decidability results. We also generalize to weighted graphs and their coverings a classical factorization theorem of their characteristic polynomials.

Keywords: graph unfolding, graph covering, universal covering, regular tree, weighted graph, characteristic polynomial, graph factorization

DOI: 10.3233/FI-222150

Journal: Fundamenta Informaticae, vol. 189, no. 1, pp. 1-47, 2022