# The signed matchings in graphs

Discussiones Mathematicae Graph Theory (2008)

- Volume: 28, Issue: 3, page 477-486
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topChangping Wang. "The signed matchings in graphs." Discussiones Mathematicae Graph Theory 28.3 (2008): 477-486. <http://eudml.org/doc/270160>.

@article{ChangpingWang2008,

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 ∈ 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.},

author = {Changping Wang},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {signed matching; signed matching number; maximum signed matching; signed edge cover; signed edge cover number; strongly polynomial-time},

language = {eng},

number = {3},

pages = {477-486},

title = {The signed matchings in graphs},

url = {http://eudml.org/doc/270160},

volume = {28},

year = {2008},

}

TY - JOUR

AU - Changping Wang

TI - The signed matchings in graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2008

VL - 28

IS - 3

SP - 477

EP - 486

AB - 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.

LA - eng

KW - signed matching; signed matching number; maximum signed matching; signed edge cover; signed edge cover number; strongly polynomial-time

UR - http://eudml.org/doc/270160

ER -

## References

top- [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. Zbl1168.05343
- [5] S. Goodman, S. Hedetniemi and R.E. Tarjan, b-matchings in trees, SIAM J. Comput. 5 (1976) 104-108, doi: 10.1137/0205009. Zbl0324.05002
- [6] D. Hausmann, Adjacent vertices on the b-matching polyhedron, Discrete Math. 33 (1981) 37-51, doi: 10.1016/0012-365X(81)90256-9. Zbl0469.05053
- [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. Zbl1138.05052
- [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. Zbl0491.90068
- [9] A. Schrijver, Combinatorial Optimization: polyhedra and efficiency (Berlin, Springer, 2004). Zbl1072.90030
- [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. Zbl1119.05085
- [11] B. Xu, On signed edge domination numbers of graphs, Discrete Math. 239 (2001) 179-189, doi: 10.1016/S0012-365X(01)00044-9. Zbl0979.05081
- [12] B. Xu, Note On edge domination numbers of graphs, Discrete Math. 294 (2005) 311-316, doi: 10.1016/j.disc.2004.11.008. Zbl1062.05116
- [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. Zbl1091.05055

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.