Wang, Changping The signed matchings in graphs. (English) Zbl 1175.05114 Discuss. Math., Graph Theory 28, No. 3, 477-486 (2008). Summary: Let \(G\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\). A signed matching is a function \(x:E(G)\to\{-1,1\}\) satisfying \(\sum_{e\in E_G(v)}x(e)\leq 1\) for every \(v\in V(G)\), where \(E_G(V)= \{uv\in E(G)\mid u\in V(G)\}\). The maximum of the values of \(\sum_{e\in E(G)} x(e)\), taken over all signed matchings \(x\), is called the signed matching number and is denoted by \(\beta_1'(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 \(\beta_1'(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 \(\beta_1'(G)\) of several classes of graphs are found. Cited in 1 ReviewCited in 2 Documents MSC: 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C22 Signed and weighted graphs 05C85 Graph algorithms (graph-theoretic aspects) Keywords:signed matching; signed matching number; maximum signed matching; signed edge cover; signed edge cover number; strongly polynomial-time PDFBibTeX XMLCite \textit{C. Wang}, Discuss. Math., Graph Theory 28, No. 3, 477--486 (2008; Zbl 1175.05114) Full Text: DOI Link