Cage (teorie grafů) - Cage (graph theory)

The Tutte (3,8) -klec.

V matematický oblast teorie grafů, a klec je běžný graf to má tak málo vrcholy jak je to možné pro jeho obvod.

Formálněr,G) -graph je definován jako graf, ve kterém má každý vrchol přesně r sousedé, a ve kterých nejkratší cyklus má délku přesně G. Je známo, že (r,G) -graf existuje pro libovolnou kombinaci r ≥ 2 a G ≥ 3. An (r,G) -cage je (r,G) -graf s nejmenším možným počtem vrcholů, ze všech (r,G) -grafy.

Pokud Mooreův graf existuje s mírou r a obvod G, musí to být klec. Kromě toho se hranice velikostí Mooreových grafů zobecňují na klece: jakákoli klec s lichým obvodem G musí mít alespoň

vrcholy a klec s rovnoměrným obvodem G musí mít alespoň

vrcholy. Jakékoli (r,G) -graf s přesně tolika vrcholy je podle definice Mooreův graf, a proto automaticky klec.

Pro danou kombinaci může existovat více klecí r a G. Například existují tři neizomorfní (3,10) klece, každá se 70 vrcholy: Balaban 10-klec, Harriesův graf a Harries – Wongův graf. Existuje však pouze jedna (3,11) klec: Klec Balaban 11 (se 112 vrcholy).

Známé klece

Graf prvního stupně nemá žádný cyklus a připojený graf druhého stupně má obvod rovný jeho počtu vrcholů, takže klece jsou zajímavé pouze pro r ≥ 3. (r, 3) -cage je a kompletní graf K.r+1 na r+1 vrcholy a (r, 4) -cage je a kompletní bipartitní graf K.r,r na 2r vrcholy.

Mezi další pozoruhodné klece patří Mooreovy grafy:

Počet vrcholů ve známém (r,G) klece, pro hodnoty r > 2 a G > 2, kromě projektivních rovin a zobecněných polygonů, jsou:

G
r
3456789101112
346101424305870112126
45819266780728
561030421702730
671240623127812
78145090

Asymptotika

Pro velké hodnoty G, Mooreova vazba znamená, že číslo n vrcholů musí růst nejméně jednotlivě exponenciálně jako funkce G. Ekvivalentně G může být maximálně úměrná logaritmus z n. Přesněji,

Předpokládá se, že tato vazba je těsná nebo těsně těsná (Bollobás & Szemerédi 2002 ). Nejznámější dolní meze G jsou také logaritmické, ale s menším konstantním faktorem (z čehož vyplývá, že n roste jednotlivě exponenciálně, ale rychleji než Moore). Konkrétně konstrukce Ramanujan grafy definován Lubotzky, Phillips & Sarnak (1988) uspokojit vázané

Tato vazba byla mírně vylepšena o Lazebnik, Ustimenko & Woldar (1995).

Je nepravděpodobné, že by tyto grafy byly samy klecí, ale jejich existence dává horní hranici počtu vrcholů potřebných v kleci.

Reference

  • Biggs, Normani (1993), Algebraická teorie grafů (2. vyd.), Cambridge Mathematical Library, str. 180–190, ISBN  0-521-45897-8.
  • Bollobás, Béla; Szemerédi, Endre (2002), „Obvod řídkých grafů“, Journal of Graph Theory, 39 (3): 194–200, doi:10,1002 / jgt.10023, PAN  1883596.
  • Exoo, G; Jajcay, R (2008), „Dynamický průzkum klece“ Dynamické průzkumy, Electronic Journal of Combinatorics, DS16, archivovány z originál dne 01.01.2015, vyvoláno 2012-03-25.
  • Erdős, Paul; Rényi, Alfréd; Sós, Vera T. (1966), „K problému teorie grafů“ (PDF), Studia Sci. Matematika. Hungar., 1: 215–235, archivovány od originál (PDF) dne 09.03.2016, vyvoláno 2010-02-23.
  • Hartsfield, Nora; Ringel, Gerhard (1990), Perly v teorii grafů: komplexní úvod, Academic Press, str.77–81, ISBN  0-12-328552-6.
  • Holton, D. A .; Sheehan, J. (1993), Petersenův graf, Cambridge University Press, str. 183–213, ISBN  0-521-43594-3.
  • Lazebnik, F .; Ustimenko, V. A .; Woldar, A. J. (1995), „Nová řada hustých grafů vysokého obvodu“, Bulletin of the American Mathematical Society Nová řada, 32 (1): 73–79, arXiv:matematika / 9501231, doi:10.1090 / S0273-0979-1995-00569-0, PAN  1284775.
  • Lubotzky, A.; Phillips, R .; Sarnak, P. (1988), „Ramanujan graphs“, Combinatorica, 8 (3): 261–277, doi:10.1007 / BF02126799, PAN  0963118.
  • Tutte, W. T. (1947), "Rodina kubických grafů", Proc. Cambridge Philos. Soc., 43 (4): 459–474, Bibcode:1947PCPS ... 43..459T, doi:10.1017 / S0305004100023720.

externí odkazy