×

The signed matchings in graphs. (English) Zbl 1175.05114

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.

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)
PDFBibTeX XMLCite
Full Text: DOI Link