This article is cited in 2 papers

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

A. I. Bolotnikov

Lomonosov Moscow State University

Abstract: We consider a hyperplane arrangement constructed from a subset of the set of all simple paths in a graph. A relation of the constructed arrangement to the maximum matching problem is established. In addition, the problem of finding the characteristic polynomial is reduced to the case of a connected original graph. In the case where the original graph is a tree, a formula for the characteristic polynomial is obtained.

Keywords: hyperplane arrangement, graphical arrangement, partially ordered set, matroid, maximal matching problem.

UDC: 519.171

Received: 12.05.2022

DOI: 10.4213/dm1718

 English version: Discrete Mathematics and Applications, 2024, 34:5, 251–261

Bibliographic databases:

•