Unfoldings and Coverings of Weighted Graphs

DOI10.3233/FI-222150MaRDI QIDQ6094515zbMATH OpenOpenAlexFDO

Authors Bruno Courcelle

Publication date 14 September 2023

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2212.07205

zbMATH Keywords

characteristic polynomialgraph coveringgraph factorizationgraph unfoldingregular treeuniversal coveringweighted graph

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10)

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. We prove similar statements for unfoldings. Our study of the difficult proof of Leighton's Theorem lead us to generalize coverings and similarly, unfoldings, by attaching finite or infinite weights 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 infinite weights provides us with finite descriptions of regular trees having nodes of countably infinite degree. We also generalize to weighted graphs and their coverings a classical factorization theorem of their characteristic polynomials.

Recommendations

• On the weighted complexity of a regular covering of a graph
• Weighted zeta functions of graph coverings
• Comparing Universal Covers in Polynomial Time
• scientific article; zbMATH DE number 3978424
• Two generalisations of Leighton's theorem (with an appendix by Giles Gardam and Daniel J. Woodhouse)

Cites work

• A common cover of graphs and 2-cell embeddings
• Fibrations of graphs
• Finite common coverings of pairs of regular graphs
• Fundamental properties of infinite trees
• Graph structure and monadic second-order logic. A language-theoretic approach
• scientific article; zbMATH DE number 4173910 (Why is no real title available?)
• scientific article; zbMATH DE number 91031 (Why is no real title available?)
• scientific article; zbMATH DE number 557977 (Why is no real title available?)
• scientific article; zbMATH DE number 1142319 (Why is no real title available?)
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• Monadic second-order logic, graph coverings and unfoldings of transition systems
• On Leighton's graph covering theorem
• Revisiting Leighton’s theorem with the Haar measure
• Simulation of large networks on smaller networks
• The monadic second-order logic of graphs. IX: Machines and their behaviours
• Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
• Uniform Tree Lattices
• Universal covers of graphs: Isomorphism to depth \(n-1\) implies isomorphism to all depths
• Universal covers, color refinement, and two-variable counting logic: lower bounds for the depth

Cited in

(1)

• On regular trees defined from unfoldings and coverings

This page was built for publication: Unfoldings and Coverings of Weighted Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6094515)