The signed matchings in graphs

Let G be a graph with vertex set V(G) and edge set E(G). A signed matching is a function x: E(G) → {-1,1} satisfying ${\displaystyle {\sum }_{e\in E_G\left(v\right)}x\left(e\right)\le 1}$ for every v ∈ V(G), where ${\displaystyle E_G\left(v\right)=\{uv\in E\left(G\right)\mid u\in V\left(G\right)\}}$. The maximum of the values of ${\displaystyle {\sum }_{e\in E\left(G\right)}x\left(e\right)}$, taken over all signed matchings x, is called the signed matching number and is denoted by β'₁(G). In this paper, we study the complexity of the maximum signed matching problem. We show that a maximum signed matching can be found in strongly polynomial-time. We present sharp upper and lower bounds on β'₁(G) for general graphs. We investigate the sum of maximum size of signed matchings and minimum size of signed 1-edge covers. We disprove the existence of an analogue of Gallai's theorem. Exact values of β'₁(G) of several classes of graphs are found.