Geodesic
The signed matchings in graphs
Discussiones Mathematicae. Graph Theory, Tome 28 (2008) no. 3, pp. 477-486

Voir la notice de l'article provenant de la source Library of Science

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 ∑_e ∈ E_G(v) x(e) ≤ 1 for every v ∈ V(G), where E_G(v) = uv ∈ E(G)| u ∈ V(G). The maximum of the values of ∑_e ∈ E(G) x(e), 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.
Keywords: signed matching, signed matching number, maximum signed matching, signed edge cover, signed edge cover number, strongly polynomial-time 
@article{DMGT_2008_28_3_a7,
     author = {Wang, Changping},
     title = {The signed matchings in graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {477--486},
     publisher = {mathdoc},
     volume = {28},
     number = {3},
     year = {2008},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2008_28_3_a7/}
}
TY  - JOUR
AU  - Wang, Changping
TI  - The signed matchings in graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2008
SP  - 477
EP  - 486
VL  - 28
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2008_28_3_a7/
LA  - en
ID  - DMGT_2008_28_3_a7
ER  - 
%0 Journal Article
%A Wang, Changping
%T The signed matchings in graphs
%J Discussiones Mathematicae. Graph Theory
%D 2008
%P 477-486
%V 28
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2008_28_3_a7/
%G en
%F DMGT_2008_28_3_a7
Wang, Changping. The signed matchings in graphs. Discussiones Mathematicae. Graph Theory, Tome 28 (2008) no. 3, pp. 477-486. http://geodesic.mathdoc.fr/item/DMGT_2008_28_3_a7/