On the matching arrangement of a graph and properties of its characteristic polynomial

2022/05/29 by A. E. Bolotnikov, Bolotnikov, Aleksey
Engineering · #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2205.14754

openalex publication_date 2022/05/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper considers a hyperplane arrangement constructed with a subset of a set of all simple paths in a graph. A connection of the constructed arrangement to the maximum matching problem is established. Moreover, the problem of finding the characteristic polynomial is reduced to the case of a connected initial graph. The formula of the characteristic polynomial was also found for the case, when the initial graph is a tree.

Related

• Characteristic Polynomial of Certain Hyperplane Arrangements through Graph Theory
• Enumeration of Graphs and the Characteristic Polynomial of the Hyperplane Arrangements J_n
• Two polynomial algorithms for special maximum matching constructing in trees
• Generalized threshold arrangements
• Paths, Trees, and Flowers