Discussiones Mathematicae Graph Theory 28(3) (2008) 477-486
doi: 10.7151/dmgt.1421

[BIBTex] [PDF] [PS]

THE SIGNED MATCHINGS IN GRAPHS

Changping Wang

Department of Mathematics
Ryerson University
Toronto, ON, Canada, M5B 2K3
e-mail: cpwang@ryerson.ca

Abstract

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 ∈ EG(v) x(e) ≤ 1  for every v ∈ V(G), where EG(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 β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 β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 β1(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.

2000 Mathematics Subject Classification: 05C70, 05C85.

References

[1] R.P. Anstee, A polynomial algorithm for b-matchings: an alternative approach, Inform. Process. Lett. 24 (1987) 153-157, doi: 10.1016/0020-0190(87)90178-5.
[2] A. Bonato, K. Cameron and C. Wang, Signed b-edge covers of graphs, submitted.
[3] G. Chartrand and L. Lesniak, Graphs & Digraphs, third edition (Chapman and Hall, Boca Raton, 2000).
[4] W. Chena and E. Song, Lower bounds on several versions of signed domination number, Discrete Math. 308 (2008) 1837-1846, doi: 10.1016/j.disc.2006.09.050.
[5] S. Goodman, S. Hedetniemi and R.E. Tarjan, b-matchings in trees, SIAM J. Comput. 5 (1976) 104-108, doi: 10.1137/0205009.
[6] D. Hausmann, Adjacent vertices on the b-matching polyhedron, Discrete Math. 33 (1981) 37-51, doi: 10.1016/0012-365X(81)90256-9.
[7] H. Karami, S.M. Sheikholeslami and A. Khodkar, Some notes on signed edge domination in graphs, Graphs and Combin. 24 (2008) 29-35, doi: 10.1007/s00373-007-0762-8.
[8] W.R. Pulleyblank, Total dual integrality and b-matchings, Oper. Res. Lett. 1 (1981/82) 28-33, doi: 10.1016/0167-6377(81)90021-3.
[9] A. Schrijver, Combinatorial Optimization: polyhedra and efficiency (Berlin, Springer, 2004).
[10] C. Wang, The signed star domination numbers of the Cartesian product graphs, Discrete Appl. Math. 155 (2007) 1497-1505, doi: 10.1016/j.dam.2007.04.008.
[11] B. Xu, On signed edge domination numbers of graphs, Discrete Math. 239 (2001) 179-189, doi: 10.1016/S0012-365X(01)00044-9.
[12] B. Xu, Note On edge domination numbers of graphs, Discrete Math. 294 (2005) 311-316, doi: 10.1016/j.disc.2004.11.008.
[13] B. Xu, Two classes of edge domination in graphs, Discrete Appl. Math. 154 (2006) 1541-1546, doi: 10.1016/j.dam.2005.12.007.

Received 18 December 2007
Revised 8 May 2008
Accepted 28 July 2008