2022/04/25 by Donald G. Saari, Saari, Donald
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #G.2.2
paper · pdf · doi:10.48550/arxiv.2204.11987
openalex publication_date 2022/04/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Without imposing restrictions on a weighted graph's arc lengths, symmetry structures cannot be expected. But, they exist. To find them, the graphs are decomposed into a component that dictates all closed path properties (e.g., shortest and longest paths), and a superfluous component that can be removed. The simpler remaining graph exposes inherent symmetry structures that form the basis for all closed path properties. For certain asymmetric problems, the symmetry is that of three-cycles; for the general undirected setting it is a type of four-cycles; for general directed problems with asymmetric costs, it is a product of three and four cycles. Everything extends immediately to incomplete graphs.