알스파흐의 추측

Alspach의 추측은 규정된 주기 길이로 완전한 그래프의 분리된 주기 커버의 특성을 나타내는 수학적 정리이다.그것은 1981년에 이것을 연구 문제로 제시한 브라이언 알스파치의 이름을 따서 명명되었다.대린 브라이언트, 대니얼 호슬리, 윌리엄 페터슨(2014)이 증명서를 발행했다.

공식화

이 문맥에서 분리 주기 커버는 그래프의 모든 에지를 포함하는 동일한 에지를 사용하는 두 개의 단순한 사이클 세트입니다.각 정점의 정도는 해당 정점을 포함하는 주기 수(짝수)의 2배이기 때문에 분리 주기 커버가 존재하기 위해서는 모든 정점에 짝수 도수가 있어야 합니다.또한 분리된 사이클 커버 내의 사이클이 주어진 길이의 컬렉션을 가지려면 주어진 사이클 길이의 합계가 주어진 그래프 내의 총 에지 수와 동일해야 합니다.Alspach는 완전한 그래프에 필요한 두 가지 조건도 충분하다고 추측했다$.$n { $displaystyle$ n$$}이$$ 홀수(도가 짝수인 경우)와 주어진 사이클 길이 리스트($모두{\displaystyle }$n { $displaystyle$n$\})$가 ${\displaystyle \genfrac{}{}{0ex}{}{\mathrm{n}}{}}$2 ${tbinom {n}{2}}($전체 에지의 수)에${\displaystyle }$더해지는 경우그래프) 완전한 $그래프{\displaystyle {}_{}}$ $(\$ K_${n})$은 항상 지정된 길이의 사이클로 분해할 수 있습니다.브라이언트, 호슬리, 그리고 페터슨이 증명한 것이 바로 이 진술이다.

짝수 정점에 대한 일반화

정점 수$n{\displaystyle }$$(\$displaystyle $n)$이 짝수인 완전한 $그래프{\displaystyle {}_{}}$ $(\displaystyle K_{n$})의$$ 경우, Alspach는 그래프를 항상 완벽한 매칭과${\displaystyle }$(${\displaystyle \genfrac{}{}{0ex}{}{\mathrm{n}}{}}$ ${\displaystyle 2}$)${\displaystyle }$- n /$(\display$ style {$tbinom$ {n$}-n/$2$)$에 이르는 소정의 길이의 사이클 집합으로 분해할 수 있다고 추측했다.이 경우 매칭은 각 정점에서 홀수 도를 제거하여 짝수 도 서브그래프를 남깁니다.나머지 조건은 사이클 길이의 합계가 커버되는 에지의 수와 같다는 것입니다.이 추측의 변형은 브라이언트, 호슬리, 그리고 페터슨에 의해서도 증명되었다.

관련 문제

완전한 그래프를 주어진 2-규칙 그래프의 복사본으로 분해하는 오버울파치 문제는 관련이 있지만, 다른 그래프의 특별한 경우는 아니다.G$(\displaystyle$ G$)$가 $n개의$$$정점이 $있는{\displaystyle }$ 2-정규 그래프인 $경우{\displaystyle }$,$G$(\$displaystyle$$$G$)$의 오버울파치 문제에 대한 해결책도 그래프 ${\displaystyle \mathrm{전체}}$를${\displaystyle }$(${\displaystyle \mathrm{n}}$- 1)${\displaystyle }$/ $(\displaystyle (n-1)/2)$개의$$ 복사본으로${\displaystyle }$분해할 수 있습니다.$G$의$$각 사이클(\$displaystyle$ G$).$ 단, $(\$을 이렇게 많은 크기의 사이클로 분해할 때마다 G$(\displaystyle$ G$)$의 $복사본$을 형성하는 분리 사이클로 그룹화할 수 있는 것은 아니며, 반면에 Alspach의 추측의 모든 인스턴스가 일련의 사이클(\displaystyle G$){\displaystyle }$을 포함하는 것은 아니다.${\displaystyle n}$-${\displaystyle 1}$) /$$ {\$displaystyle (n-1)/2}$ 카피$$.

레퍼런스

• Alspach, B. (1981), "Problem 3", Research problems, Discrete Mathematics, 36 (3): 333, doi:10.1016/s0012-365x(81)80029-5
• Bryant, Darryn; Horsley, Daniel; Pettersson, William (2014), "Cycle decompositions V: Complete graphs into cycles of arbitrary lengths", Proceedings of the London Mathematical Society, Third Series, 108 (5): 1153–1192, arXiv:1204.3709, doi:10.1112/plms/pdt051, MR 3214677
• Chartrand, Gary; Lesniak, Linda; Zhang, Ping (2015), "Alspach's conjecture", Graphs & Digraphs, Textbooks in Mathematics, vol. 39 (6th ed.), CRC Press, p. 349, ISBN 9781498735803