Onq-Power Cycles in Cubic Graphs

• Autorzy: Julien Bensmail
• Języki publikacji: EN

Abstrakty

EN

In the context of a conjecture of Erdős and Gyárfás, we consider, for any q ≥ 2, the existence of q-power cycles (i.e., with length a power of q) in cubic graphs. We exhibit constructions showing that, for every q ≥ 3, there exist arbitrarily large cubic graphs with no q-power cycles. Concerning the remaining case q = 2 (which corresponds to the conjecture of Erdős and Gyárfás), we show that there exist arbitrarily large cubic graphs whose all 2-power cycles have length 4 only, or 8 only.

Słowa kluczowe

EN

cubic graphs; q-power cycles; Erdős-Gyárfás conjecture

Kategorie tematyczne

• 68R10: Graph theory (including graph drawing)
• 05C38: Paths and cycles

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 1
• Strony: 211-220

Daty

wydano

2017-02-01

otrzymano

2015-10-03

poprawiono

2016-03-18

zaakceptowano

2016-03-30

online

2017-01-13

Twórcy

autor

Julien Bensmail

• Department of Applied Mathematics and Computer Science, Technical University of Denmark, DK-2800 Lyngby,

Identyfikatory

DOI

10.7151/dmgt.1926