Späť

Ľahké hrany v rovinných grafoch s daným obvodom
Light edges in plane graphs with given girth

RNDr. Mária Maceková
Univerzita Pavla Jozefa Šafárika v Košiciach, Prírodovedecká fakulta

Abstrakt:
V tomto príspevku budeme uvažovať 2-súvislé rovinné grafy bez slučiek a multihrán. Budeme využívať štandardnú grafovú terminológiu podľa knihy [1]. Pod váhou hrany budeme rozumieť súčet stupňov jej koncových vrcholov. Hovoríme, že hrana je ľahká, ak jej váha je konečné číslo. Ďalej hovoríme, že hrana e=uv je typu (x,y), ak stupeň vrchola u je najviac ak x, a stupeň vrchola v je najviac ak y. V roku 1955 Kotzig dokázal, že každý 3-súvislý rovinný graf obsahuje hranu váhy najviac ak 13, čo bolo neskôr rozšírené na existenciu hrany typu (3,10), (4,7) alebo (5,6) v takýchto grafoch. Hranice 10, 7 a 6 v daných typoch sú pritom najlepšie možné. Kompletný bipartitný graf s jednou partiou na 2 vrcholoch a druhou partiou ľubovoľne veľkou ale neobsahuje žiadnu ľahkú hranu. Tento príklad ukazuje, že požiadavku na 3-súvislosť grafu nemožno vynechať, ak sa pokúšame Kotzigovu vetu rozšíriť na 2-súvislé rovinné grafy. Situácia sa ale podstatne zmení, ak do úvahy vezmeme aj obvod rovinného grafu. Podarilo sa nám dokázať, že každý 2-súvislý rovinný graf obvodu aspoň 5 obsahuje hranu váhy najviac ak 7. [1] J.A. Bondy, U.S.R. Murty, Graph Theory, Springer, 2008

Kľúčové slová:
rovinný graf; váha; ľahká hrana; obvod; Kotzigova veta


Abstract:
In this contribution we investigate 2-connected plane graphs without loops and multiple edges. We use a standard graph theory terminology according to the book [1]. Let the weight of an edge be the sum of the degrees of its endvertices. An edge is light if its weight is a finite number. Further, edge e=uv is of the type (x,y), if the degree of vertex u is at most x and the degree of vertex v is at most y. In 1955 Kotzig proved that every 3-connected plane graph contains an edge with weight at most 13, what was later extended to the existence of an edge of the type (3,10), (4,7) or (5,6) in such graphs. The bounds 10,7 and 6 in this types are the best possible. Komplete bipartite graph with one partite set on 2 vertices and the second partite set arbitrary large contains no light edge. This example shows that the requirement on the 3-connectedness of graph cannot be omitted when trying to extend Kotzig's theorem to 2-connected plane graphs. The situation changes significantly if we involve the girth of plane graph into the game. We have proved that every 2-connected plane graph with girth at least 5 contains an edge with weight at most 7. [1] J.A. Bondy, U.S.R. Murty, Graph Theory, Springer, 2008

Keywords:
plane graph; weight; light edge; girth; Kotzig's theorem

Späť