| | |
| | |
Stat |
Members: 3667 Articles: 2'599'751 Articles rated: 2609
16 February 2025 |
|
| | | |
|
Article overview
| |
|
Multi-Switch: a Tool for Finding Potential Edge-Disjoint $1$-factors | Tyler Seacrest
; | Date: |
1 Aug 2015 | Abstract: | Let $n$ be even, let $pi = (d_1, ldots, d_n)$ be a graphic degree sequence,
and let $pi - k = (d_1 - k, ldots, d_n - k)$ also be graphic. Kundu proved
that $pi$ has a realization $G$ containing a $k$-factor, or $k$-regular graph.
Another way to state the conclusion of Kundu’s theorem is that $pi$
emph{potentially} contains a $k$-factor.
Busch, Ferrara, Hartke, Jacobsen, Kaul, and West conjectured that more was
true: $pi$ potentially contains $k$ edge-disjoint $1$-factors. Along these
lines, they proved $pi$ would potentially contain edge-disjoint copies of a
$(k-2)$-factor and two $1$-factors.
We follow the methods of Busch et al. but introduce a new tool which we call
a multi-switch. Using this new idea, we prove that $pi$ potentially has
edge-disjoint copies of a $(k-4)$-factor and four $1$-factors. We also prove
that $pi$ potentially has ($lfloor k/2
floor + 2$) edge-disjoint
$1$-factors, but in this case cannot prove the existence of a large regular
graph. | Source: | arXiv, 1508.0079 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|