Unfoldings and Coverings of Weighted Graphs

DOI10.3233/fi-222150arXiv2212.07205OpenAlexW4287801194MaRDI QIDQ6094515

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 polynomialweighted graphregular treegraph coveringuniversal coveringgraph factorizationgraph unfolding

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• On Leighton's graph covering theorem
• The monadic second-order logic of graphs. IX: Machines and their behaviours
• Fundamental properties of infinite trees
• A common cover of graphs and 2-cell embeddings
• Finite common coverings of pairs of regular graphs
• Monadic second-order logic, graph coverings and unfoldings of transition systems
• Universal covers of graphs: Isomorphism to depth \(n-1\) implies isomorphism to all depths
• Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
• Uniform Tree Lattices
• Simulation of large networks on smaller networks
• Universal Covers, Color Refinement, and Two-Variable Counting Logic: Lower Bounds for the Depth
• Revisiting Leighton’s theorem with the Haar measure
• Fibrations of graphs