Discussiones Mathematicae Graph Theory 28(3) (2008)
477-486
doi: 10.7151/dmgt.1421
Changping Wang
Department of Mathematics
Ryerson University
Toronto, ON, Canada, M5B 2K3
e-mail: cpwang@ryerson.ca
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.
[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