- Tytuł:
- The signed matchings in graphs
- Autorzy:
- Wang, Changping
- Powiązania:
- https://bibliotekanauki.pl/articles/743079.pdf
- Data publikacji:
- 2008
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
signed matching
signed matching number
maximum signed matching
signed edge cover
signed edge cover number
strongly polynomial-time - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2008, 28, 3; 477-486
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł