Kotzigsova věta - Kotzigs theorem - Wikipedia

The triakis icosahedron, mnohostěn, ve kterém má každá hrana koncové body s celkovým stupněm alespoň 13

v teorie grafů a polyedrická kombinatorika oblasti matematiky, Kotzigova věta je prohlášení, že každý polyedrický graf má hranu, jejíž dva koncové body mají celkem stupeň maximálně 13. Extrémním případem je triakis icosahedron, kde žádná hrana nemá menší celkový stupeň. Výsledek je pojmenován po Anton Kotzig, který jej publikoval v roce 1955 v dvojí tvoří každý konvexní mnohostěn má dvě přilehlé plochy s celkem maximálně 13 stranami.[1] To bylo jmenováno a popularizováno na západě v 70. letech 20. století Branko Grünbaum.[2][3]

Obecněji řečeno, každý rovinný graf minimálního stupně alespoň tří má buď hranu celkového stupně nejvýše 12, nebo alespoň 60 hran, které (jako hrany v triakis icosahedron) spojují vrcholy stupňů 3 a 10.[4]Pokud jsou všechny trojúhelníkové plochy mnohostěnu vrcholově disjunktní, existuje hrana s menším celkovým stupněm, maximálně osmi.[5]Zobecnění věty jsou také známé pro vkládání grafů na povrchy s vyšší rod.[6]

Vetu nelze zobecnit na všechny rovinné grafy jako kompletní bipartitní grafy a mají hrany s neomezeným celkovým stupněm. U rovinných grafů s vrcholy stupňů menšími než tři však byly prokázány varianty věty, které ukazují, že buď existuje hrana omezeného celkového stupně, nebo nějaký jiný speciální druh podgrafu.[7]

Reference

  1. ^ Kotzig, Anton (1955), „Příspěvek k teorii Eulerianovy mnohostěny“, Matematicko-Fyzikálny Časopis, 5: 101–113, PAN  0074837
  2. ^ Grünbaum, Branko (1975), „Polytopal graphs“, Studie v teorii grafů, část II, MAA studia z matematiky, 12201, 224, PAN  0406868
  3. ^ Grünbaum, Branko (1976), „Nové pohledy na některé staré otázky kombinatorické geometrie“, Colloquio Internazionale sulle Teorie Combinatorie (Řím, 1973), Tomo I., Atti dei Convegni Lincei, 17, str. 451–468, PAN  0470861
  4. ^ Borodin, O. V. (1990), „Zevšeobecnění Kotzigovy věty a předepsané zbarvení hran planárních grafů“, Matematicheskie Zametki, 48 (6): 22–28, 160, doi:10.1007 / BF01240258, PAN  1102617
  5. ^ Borodin, Oleg V. (1992), „Rozšíření Kotzigovy věty o minimální hmotnosti hran v 3-polytopech“, Mathematica Slovaca, 42 (4): 385–389, PAN  1195032
  6. ^ Zaks, Joseph (1983), „Rozšíření Kotzigovy věty“, Israel Journal of Mathematics, 45 (4): 281–296, doi:10.1007 / BF02804013, hdl:10338.dmlcz / 127504, PAN  0720304
  7. ^ Cole, Richard; Kowalik, Łukasz; Škrekovski, Riste (2007), „Zobecnění Kotzigovy věty a její aplikace“, SIAM Journal on Discrete Mathematics, 21 (1): 93–106, CiteSeerX  10.1.1.227.3878, doi:10.1137/050646196, PAN  2299697