The signed matchings in graphs

Changping Wang

Discussiones Mathematicae Graph Theory (2008)

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

Abstract

top
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 ) = u v ∈ 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.

How to cite

top

Changping 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. [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. [2] A. Bonato, K. Cameron and C. Wang, Signed b-edge covers of graphs, submitted. 
  3. [3] G. Chartrand and L. Lesniak, Graphs & Digraphs, third edition (Chapman and Hall, Boca Raton, 2000). 
  4. [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. [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. [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. [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. [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. [9] A. Schrijver, Combinatorial Optimization: polyhedra and efficiency (Berlin, Springer, 2004). Zbl1072.90030
  10. [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. [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. [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. [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

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.