Abstrakt. Vi undersöker det maximala antalet enkla cykler och det maximala antalet Hamiltonian cyklar i en planar graf G med n hörn. Med hjälp av överföringsmatrismetoden konstruerar vi en familj av grafer som har minst 2.4262 n enkla cykler och minst 2.0845 n Hamilton cykler. Baserat på att räkna argument för perfekta matchningar visar vi att 2.3404 n är en övre gräns för antalet Hamiltonska cykler. Dessutom får vi övre gränser för antalet enkla cykler av en given längd med en ansiktsfärgningsteknik. Tillsammans med båda visar vi att det inte finns någon planar graf med mer än 2.8927 n enkla cykler. Detta minskar det tidigare gapet mellan den övre och nedre gränsen för den exponentiella tillväxten från 1,03 till 0,46.
Buchin m.fl. REF förbättrar dessa gränser till 2.4262 n respektive 2.8927 n.
On the number of cycles in planar graphs
{'venue': 'in Proc. 13th COCOON', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}