Silně pravidelný graf - Strongly regular graph

v teorie grafů, a silně pravidelný graf je definována následovně. Nechat G = (PROTI, E) být a běžný graf s proti vrcholy a stupně k. G se říká, že je velmi pravidelné pokud existují také celá čísla λ a μ takové, že:
- Každé dva sousední vrcholy mají λ společné sousedy.
- Každé dva nesousedící vrcholy mají μ společných sousedů.
O grafu tohoto druhu se někdy říká, že je to srg (proti, k, λ, μ). Silně pravidelné grafy představil Raj Chandra Bose v roce 1963.[1]
Někteří autoři vylučují grafy, které splňují definici triviálně, konkrétně grafy, které jsou disjunktním spojením jednoho nebo více stejně velkých kompletní grafy,[2][3] a jejich doplňuje, kompletní vícedílné grafy se stejně velkými nezávislými sadami.
The doplněk srg (proti, k, λ, μ) je také silně pravidelný. Je to srg (proti, v-k−1, proti−2−2k+ μ, proti−2k+ λ).
Silně pravidelný graf je a vzdálenost-pravidelný graf s průměrem 2, kdykoli μ není nenulová lokálně lineární graf kdykoli λ je jedna.
Vlastnosti
Vztah mezi parametry
Čtyři parametry v srg (proti, k, λ, μ) nejsou nezávislé a musí dodržovat následující vztah:
Výše uvedený vztah lze snadno odvodit pomocí argumentu počítání takto:
- Představte si, že vrcholy grafu leží ve třech úrovních. Vyberte libovolný vrchol jako kořen v úrovni 0. Pak jeho k sousedé leží na úrovni 1 a všechny ostatní vrcholy leží na úrovni 2.
- Vrcholy na úrovni 1 jsou přímo spojeny s kořenem, proto musí mít λ další sousedy společné s kořenem, a tito společní sousedé musí být také na úrovni 1. Protože každý vrchol má stupeň k, existují zbývající hrany pro každý uzel úrovně 1 pro připojení k uzlům na úrovni 2. Proto existují hrany mezi úrovní 1 a úrovní 2.
- Vrcholy na úrovni 2 nejsou přímo spojeny s kořenem, proto musí mít μ společných sousedů s kořenem a tito běžní sousedé musí být všichni na úrovni 1. Existují vrcholy v úrovni 2 a každý je připojen k μ uzlům v úrovni 1. Proto je počet hran mezi úrovní 1 a úrovní 2 .
- Rovnice dvou výrazů pro hrany mezi úrovní 1 a úrovní 2 následuje vztah.
Matice sousedství
Nechat Já označit matice identity a nechte J označit matice jedniček, obě matice objednávky proti. The matice sousedství A silně pravidelného grafu splňuje dvě rovnice. Za prvé:
což je triviální přepracování požadavku na pravidelnost. To ukazuje k je vlastní hodnota matice sousedství s vlastním vektorem všech. Druhá je kvadratická rovnice,
což vyjadřuje silnou pravidelnost. The ij-tý prvek na levé straně udává počet dvoustupňových cest od i na j. První člen RHS udává počet vlastních cest od i na i, jmenovitě k hrany ven a zpět dovnitř. Druhý člen udává počet dvoustupňových cest, když i a j jsou přímo připojeni. Třetí člen dává odpovídající hodnotu, když i a j nejsou připojeni. Jelikož tyto tři případy jsou vzájemně se vylučující a kolektivně vyčerpávající následuje jednoduchá aditivní rovnost.
Naopak graf, jehož matice sousedství splňuje obě výše uvedené podmínky a který není úplným nebo nulovým grafem, je silně pravidelný graf.[4]
Vlastní čísla
Matice sousedství grafu má přesně tři vlastní čísla:
- k, jehož multiplicita je 1 (jak je vidět výše)
- jehož multiplicita je
- jehož multiplicita je
Protože multiplicita musí být celá čísla, jejich výrazy poskytují další omezení hodnot proti, k, μ, a λ, související s tzv Podmínky Kerin.
Silně pravidelné grafy, pro které jsou nazývány konferenční grafy kvůli jejich spojení se symetrickými konferenční matice. Jejich parametry se snižují na
Silně pravidelné grafy, pro které mít celočíselná vlastní čísla s nestejnou multiplicitou.
Naopak připojený regulární graf s pouze třemi vlastními hodnotami je silně pravidelný.[5]
Příklady
- The cyklus o délce 5 je srg (5, 2, 0, 1).
- The Petersenův graf je srg (10, 3, 0, 1).
- The Clebschův graf je srg (16, 5, 0, 2).
- The Shrikhandův graf je srg (16, 6, 2, 2), což není a vzdálenost-tranzitivní graf.
- The n × n náměstí věžní graf, tj. spojnicový graf vyváženého úplného bipartitního grafu K.n, n, je srg (n2, 2n − 2, n - 2, 2). Parametry pro n= 4 se shodují s grafy Shrikhandeho grafu, ale oba grafy nejsou izomorfní.
- The hranový graf úplného grafu K.n je srg ().
- The Chang grafy jsou srg (28, 12, 6, 4), stejné jako spojnicový graf K.8, ale tyto čtyři grafy nejsou izomorfní.
- The hranový graf a zobecněný čtyřúhelník GQ (2, 4) je srg (27, 10, 1, 5). Ve skutečnosti každý zobecněný čtyřúhelník řádu (s, t) dává silně pravidelný graf tímto způsobem: k tomu, srg ((s + 1) (st + 1), s (t + 1), s-1, t +1).
- The Schläfliho graf je srg (27, 16, 10, 8).[6]
- The Hoffman – Singletonův graf je srg (50, 7, 0, 1).
- The Sims-Gewirtzův graf je (56, 10, 0, 2).
- The Graf M22 aka Mesnerův graf je srg (77, 16, 0, 4).
- The Graf Brouwer – Haemers je srg (81, 20, 1, 6).
- The Graf Higman – Sims je srg (100, 22, 0, 6).
- The Místní McLaughlinův graf je srg (162, 56, 10, 24).
- The Cameronův graf je srg (231, 30, 9, 3).
- The Graf Berlekamp – van Lint – Seidel je srg (243, 22, 1, 2).
- The McLaughlinův graf je srg (275, 112, 30, 56).
- The Paleyův graf řádu q je srg (q, (q − 1)/2, (q − 5)/4, (q - 1) / 4). Nejmenší Paleyův graf s q= 5, je 5-cyklus (výše).
- samo-doplňkové oblouk-tranzitivní grafy jsou silně pravidelné.
Volá se silně pravidelný graf primitivní pokud jsou propojeny graf i jeho doplněk. Všechny výše uvedené grafy jsou primitivní, protože jinak μ = 0 nebo λ = k.
Conwayův problém s 99 grafy požaduje stavbu srg (99, 14, 1, 2). Není známo, zda existuje graf s těmito parametry, a John Horton Conway nabídl cenu 1 000 $ za řešení tohoto problému.[7]
Grafy bez trojúhelníků, Mooreovy grafy a geodetické grafy
Silně pravidelné grafy s λ = 0 jsou trojúhelník volný. Kromě kompletních grafů na méně než 3 vrcholech a všech kompletních bipartitních grafech je známo pouze sedm výše uvedených (pětiúhelník, Petersen, Clebsch, Hoffman-Singleton, Gewirtz, Mesner-M22 a Higman-Sims). Silně pravidelné grafy s λ = 0 a μ = 1 jsou Mooreovy grafy s obvodem 5. Opět tři výše uvedené grafy (pětiúhelník, Petersen a Hoffman-Singleton) s parametry (5, 2, 0, 1), (10, 3, 0, 1) a (50, 7, 0, 1), jsou jediné známé. Jedinou další možnou sadou parametrů poskytujících Mooreův graf je (3250, 57, 0, 1); není známo, zda takový graf existuje, a pokud ano, zda je či není jedinečný.[8]
Obecněji, každý silně pravidelný graf s je geodetický graf, graf, ve kterém každé dva vrcholy mají jedinečný nevážená nejkratší cesta.[9] Jediné známé silně pravidelné grafy s jsou Mooreovy grafy. Není možné, aby takový graf měl , ale ještě nebyly vyloučeny další kombinace parametrů jako (400, 21, 2, 1). Přes probíhající výzkum vlastností, se kterými je silně pravidelný graf měl by,[10][11] není známo, zda vůbec existují, nebo dokonce zda je jejich počet konečný.[9]
Viz také
Poznámky
- ^ https://projecteuclid.org/euclid.pjm/1103035734, R. C. Bose, Silně pravidelné grafy, částečné geometrie a částečně vyvážené vzory, PacificJ. Math 13 (1963) 389–419. (str. 122)
- ^ Brouwer, Andries E; Haemers, Willem H. Spektra grafů. p. 101 Archivováno 16. 03. 2012 na Wayback Machine
- ^ Godsil, Chris; Royle, Gordone. Algebraická teorie grafů. Springer-Verlag New York, 2001, str. 218.
- ^ Cameron, P.J .; van Lint, J.H. (1991), Vzory, grafy, kódy a jejich odkazy, London Mathematical Society Student Texts 22, Cambridge University Press, s. 1.37, ISBN 978-0-521-42385-4
- ^ Godsil, Chris; Royle, Gordone. Algebraická teorie grafů. Springer-Verlag, New York, 2001, Lemma 10.2.1.
- ^ Weisstein, Eric W., "Schläfliho graf", MathWorld
- ^ Conway, John H., Pět problémů s $ 1 000 (aktualizace 2017) (PDF), Online encyklopedie celočíselných sekvencí, vyvoláno 2019-02-12
- ^ Dalfó, C. (2019), „An survey on the missing Moore graph“, Lineární algebra a její aplikace, 569: 1–14, doi:10.1016 / j.laa.2018.12.035, PAN 3901732
- ^ A b Blokhuis, A.; Brouwer, A. E. (1988), „Geodetické grafy o průměru dva“, Geometriae Dedicata, 25 (1–3): 527–533, doi:10.1007 / BF00191941, PAN 0925851
- ^ Deutsch, J .; Fisher, P. H. (2001), „Na silně pravidelných grafech s ", European Journal of Combinatorics, 22 (3): 303–306, doi:10.1006 / eujc.2000.0472, PAN 1822718
- ^ Belousov, I.N .; Makhnev, A. A. (2006), „Na velmi pravidelných grafech s a jejich automorfismy “, Doklady Akademii Nauk, 410 (2): 151–155, PAN 2455371
Reference
- A.E.Brouwer, A.M. Cohen a A. Neumaier (1989), Vzdálené pravidelné grafy. Berlín, New York: Springer-Verlag. ISBN 3-540-50619-5, ISBN 0-387-50619-5
- Chris Godsil a Gordon Royle (2004), Algebraická teorie grafů. New York: Springer-Verlag. ISBN 0-387-95241-1