Triangle-Free 2-Matchings Revisited

Details Triangle-Free 2-Matchings Revisited Triangle-Free 2-Matchings Revisited

2010-03-13

arxiv.org/abs/1003.2697v2

Mathematics

Combinatorics

COCOON2010

Scientific paper

A \emph{2-matching} in an undirected graph $G = (VG, EG)$ is a function $f \colon EG \to \set{0,1,2}$ such that for each node $v \in VG$ the sum of values $f(e)$ on all edges $e$ incident to $v$ does not exceed~2. The \emph{size} of $f$ is the sum $\sum_e f(e)$. If $\set{e \in EG \mid f(e) \ne 0}$ contains no triangles then $f$ is called \emph{triangle-free}. Cornu\'ejols and Pulleyblank devised a combinatorial $O(mn)$-algorithm that finds a triangle free 2-matching of maximum size (hereinafter $n := \abs{VG}$, $m := \abs{EG}$) and also established a min-max theorem. We claim that this approach is, in fact, superfluous by demonstrating how their results may be obtained directly from the Edmonds--Gallai decomposition. Applying the algorithm of Micali and Vazirani we are able to find a maximum triangle-free 2-matching in $O(m\sqrt{n})$-time. Also we give a short self-contained algorithmic proof of the min-max theorem. Next, we consider the case of regular graphs. It is well-known that every regular graph admits a perfect 2-matching. One can easily strengthen this result and prove that every $d$-regular graph (for $d \geq 3$) contains a perfect triangle-free 2-matching. We give the following algorithms for finding a perfect triangle-free 2-matching in a $d$-regular graph: an O(n)-algorithm for $d = 3$, an $O(m + n^{3/2})$-algorithm for $d = 2k$ ($k \ge 2$), and an $O(n^2)$-algorithm for $d = 2k + 1$ ($k \ge 2$). We also prove that there exists a constant $c > 1$ such that every 3-regular graph contains at least $c^n$ perfect triangle-free 2-matchings.

Affiliated with

Also associated with

No associations

Rating

Triangle-Free 2-Matchings Revisited does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Triangle-Free 2-Matchings Revisited, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Triangle-Free 2-Matchings Revisited will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-192047