Přejít k obsahu


2-Factors in Claw-Free Graphs with Lower Bounds Cycle Lengths

Citace:
ČADA, R., CHIBA, S., YOSHIMOTO, K. 2-Factors in Claw-Free Graphs with Lower Bounds Cycle Lengths. GRAPHS AND COMBINATORICS, 2015, roč. 31, č. 1, s. 99-113. ISSN: 0911-0119
Druh: ČLÁNEK
Jazyk publikace: eng
Anglický název: 2-Factors in Claw-Free Graphs with Lower Bounds Cycle Lengths
Rok vydání: 2015
Autoři: Doc. Ing. Roman Čada Ph.D. , Shuya Chiba Ph.D. , Prof. Kiyoshi Yoshimoto Ph.D.
Abstrakt CZ: V článku je ukázáno, že každý graf bez K_{1,3} s minimálním stupněm \delta(G) alespoň 4 má 2-faktor jehož každá kružnice má délku alespoň \lceil\frac{\delta(G) - 1}{2}\rceil a každý 2-souvislý graf bez K_{1,3} s minimálním stupněm alespoň 3 má 2-faktor jehož každá kružnice má délku alespoň \delta(G). Ve 2-souvislém případě je dolní hranice nejlepší možná.
Abstrakt EN: In this article, we prove that every claw-free graph G with minimum degree at least 4 has a 2-factor in which each cycle contains at least \lceil\frac{\delta(G) - 1}{2}\rceil vertices and every 2-connected claw-free graph G with minimum degree at least 3 has a 2-factor in which each cycle contains at least \delta(G) vertices. For the case where G is 2-connected, the lower bound on the length of a cycle is best possible.
Klíčová slova

Zpět

Patička