2021/10/23 by Ghouchan, Mohammad Farrokhi Derakhshandeh, Gharakhloo, Shekoofeh, Pour, Ali Akbar Yazdan
#05C38 (Primary) 05C62 #05C70 #05C78 #05E40 (Secondary) #Combinatorics (math.CO) #Commutative Algebra (math.AC) #FOS: Mathematics
paper · doi:10.48550/arxiv.2110.12168
A matching M in a graph Γ is positive if Γ has a vertex-labeling such that M coincides with the set of edges with positive weights. A positive matching decomposition (pmd) of Γ is an edge-partition M1,…,Mp of Γ such that Mi is a positive matching in Γ-M1∪⋯∪ Mi-1, for i=1,…,p. The pmds of graphs are used to study algebraic properties of the Lovász-Saks-Schrijver ideals arising from orthogonal representations of graphs. We give a characterization of pmds of graphs in terms of alternating closed walks and apply it to study pmds of various classes of graphs including complete multipartite graphs, (regular) bipartite graphs, cacti, generalized Petersen graphs, etc. We further show that computation of pmds of a graph can be reduced to that of its maximum pendant-free subgraph.