Möbius Graph - Kantor
| Möbius-Cantor graf | |
|---|---|
| Opkaldt efter | August Ferdinand Möbius og Z. Kantor |
| Toppe | 16 |
| ribben | 24 |
| Radius | fire |
| Diameter | fire |
| Omkreds | 6 |
| Automorfismer | 96 |
| Kromatisk tal | 2 |
| Kromatisk indeks | 3 |
| Slægt | en |
| Ejendomme |
symmetrisk Hamiltonian bipartite kubisk enhed afstand Cayley graf perfekt simpelt orienterbar |
Möbius-Cantor grafen er en symmetrisk todelt kubisk graf med 16 hjørner og 24 kanter, opkaldt efter August Ferdinand Möbius og Seligman Cantor (1857–1903). Den kan defineres som en generaliseret Petersen-graf , det vil sige, at den er dannet af hjørnerne af en ottekant forbundet med en ottekantet stjerne, hvor hvert punkt er forbundet med det tredje punkt i en række.
Möbius-Cantor konfiguration
Möbius rejste i 1828 [1] spørgsmålet om eksistensen af et par polygoner med sider i hver, med den egenskab, at hjørnerne af den ene polygon ligger på linjer, der går gennem siderne af den anden, og omvendt. Hvis et sådant par eksisterer, skal hjørnerne og siderne af disse polygoner danne en projektiv konfiguration . For der er ingen løsning på det euklidiske plan , men i 1882 fandt Kantor [2] et par polygoner af denne type i en generalisering af problemet, hvor punkterne og kanterne tilhører det komplekse projektive plan , altså i Cantors løsning , koordinaterne for polygonens hjørner er komplekse tal . Cantors løsning for et par indbyrdes indskrevne firkanter i det komplekse projektive plan kaldes Möbius-Cantor-konfigurationen . Möbius-Kantor-grafen tager sit navn fra Möbius-Cantor-konfigurationen, da det er Levi-grafen for denne konfiguration. Grafen har et toppunkt for hvert konfigurationspunkt og et punkt for hver tripel, og kanter forbinder to toppunkter, hvis det ene toppunkt svarer til et punkt og det andet til en tripel der indeholder det punkt.
Forholdet til hyperkuben
Möbius-Cantor grafen er en undergraf til den firedimensionelle hyperkubegraf og dannes ved at fjerne otte kanter fra hyperkuben [3] . Da hyperkuben er en enhedsafstandsgraf , kan Möbius-Cantor-grafen også tegnes i planet med alle sider af enhedslængde, selvom en sådan repræsentation ville resultere i krydsende kanter.
Topologi
Möbius-Cantor-grafen kan ikke indlejres i et plan uden skæringspunkter, dens krydsningstal er 4, og det er den mindste kubiske graf med et sådant antal krydsninger [4] . Derudover giver grafen et eksempel på en graf, hvor alle undergrafer har antallet af skæringspunkter to eller flere forskellige fra antallet af skæringspunkter på selve grafen [5] . Den er dog ringformet - der er dens indlejring i torusen , hvor alle dens ansigter er sekskanter [6] . Den dobbelte graf for denne indlejring er hyperoktaedergrafen .
Der er en endnu mere symmetrisk indlejring af Möbius-Cantor grafen i den dobbelte torus , som er et regulært kort og har seks ottekantede flader, hvor alle 96 grafsymmetrier kan realiseres som indlejringssymmetrier [7] . Indlejringssymmetrigruppen med 96 elementer har Cayley- grafen , som kan indlejres i en dobbelt torus . I 1984 blev det vist, at dette er den eneste gruppe af slægt to [8] .
Skulptur af DeWitt Godfrey og Duane Martinez i form af en dobbelt torus med en indlejret Möbius-Kantor-graf blev udstillet på Sloveniens tekniske museum ved den 6. slovenske internationale konference om grafteori i 2007. I 2013 blev en roterende version af skulpturen udstillet på Colgate University .
Möbius-Cantor grafen tillader en indlejring i den tredobbelte torus (torus af den tredje slags), hvilket giver et regulært kort med fire 12-gonale flader; [6] .
I 2004, som en del af undersøgelsen af mulige kemiske kulstofstrukturer, blev familien af alle indlejringer af Möbius-Cantor grafen i todimensionelle manifolds undersøgt , som et resultat blev det vist, at der er 759 ikke-ækvivalente indlejringer [9] .
Algebraiske egenskaber
Automorfigruppen i Möbius-Cantor grafen er en gruppe af orden 96 [10] . Den virker transitivt på hjørner og på kanter, så Möbius-Cantor-grafen er symmetrisk . Den har automorfismer, der kortlægger ethvert toppunkt til et hvilket som helst andet og enhver kant til enhver anden. Ifølge Fosters liste er Möbius-Cantor grafen den eneste 16-vertex symmetriske graf og den mindste kubiske symmetriske graf, der ikke er afstandstransitiv [11] . Möbius-Cantor-grafen er også en graf over Cayley .
En generaliseret Petersen-graf er vertex-transitiv hvis og kun hvis og , eller når , og kanttransitiv kun i følgende syv tilfælde: [12] . Således er Möbius-Cantor-grafen en af disse syv kanttransitive generaliserede Petersen-grafer. Dens symmetriske indlejring i den dobbelte torus er et af de syv regulære kubiske kort, hvor det samlede antal hjørner er det dobbelte af antallet af flade knudepunkter [13] . Blandt de syv symmetriske generaliserede Petersen-grafer er den kubiske graf , Petersen -grafen , dodecahedron- grafen , Desargues-grafen og Nauru-grafen .
Det karakteristiske polynomium af Möbius-Cantor grafen er lig med:
Noter
- ↑ Möbius, 1828 .
- ↑ Kantor, 1882 .
- ↑ Coxeter, 1950 .
- ↑ OEIS -sekvens A110507 _
- ↑ Dan McQuillan, R. Bruce Richter. På krydsningsnumrene af visse generaliserede Petersen-grafer // Diskret matematik. - 1992. - T. 104 , no. 3 . — S. 311–320 . - doi : 10.1016/0012-365X(92)90453-M .
- ↑ 1 2 Marushich, Pisansky, 2000 .
- ↑ Threlfall, 1932 .
- ↑ Tucker, 1984 .
- ↑ Leinen, Kuellmans, 2004 .
- ↑ Royle, G. F016A data (downlink)
- ↑ Conder, M. , Dobcsányi, P. "Trivalente symmetriske grafer op til 768 hjørner." J. Combin. Matematik. Forene. Comput. 40, 41-63, 2002
- ↑ Frucht, Graver, Watkins 1971 .
- ↑ McMullen, 1992 .
Links
- HSM Coxeter. Selvdobbelte konfigurationer og regelmæssige grafer // Bulletin of the American Mathematical Society . - 1950. - T. 56 , no. 5 . — S. 413–455 . - doi : 10.1090/S0002-9904-1950-09407-5 .
- R. Frucht, J.E. Graver, M.E. Watkins. Grupperne af de generaliserede Petersen-grafer // Proceedings of the Cambridge Philosophical Society . - 1971. - T. 70 , no. 02 . — S. 211–218 . - doi : 10.1017/S0305004100049811 .
- S. Kantor. Über die Configurationen (3, 3) mit den Indices 8, 9 und ihren Zusammenhang mit den Curven dritter Ordnung // Sitzungsberichte der Mathematisch-Naturwissenschaftlichen Classe der Kaiserlichen Akademie der Wissenschaften, Wien. - 1882. - T. 84 , Nr. 1 . — S. 915–932 . .
- E. Lijnen, A. Ceulemans. Orienterede 2-celle-indlejringer af en graf og deres symmetriklassifikation: Generering af algoritmer og casestudie af Möbius-Kantor-grafen // J. Chem. inf. Comput. Sci .. - 2004. - T. 44 , no. 5 . - S. 1552-1564 . doi : 10.1021 / ci049865c . — PMID 15446812 .
- Dragan Marušic, Tomaž Pisanski. Den bemærkelsesværdige generaliserede Petersen-graf G (8,3) // Math. Slovaca. - 2000. - T. 50 . — S. 117–121 .
- Peter McMullen. De regulære polyedre af typen { p , 3} med 2 p hjørner // Geometriae Dedicata . - 1992. - T. 43 , no. 3 . — S. 285–289 . - doi : 10.1007/BF00151518 .
- AF Mobius. Kann von zwei dreiseitigen Pyramiden ene jede in Bezug auf die andere um- und eingeschrieben zugleich heissen? // J. Reine Angew. Matematik. . - 1828. - T. 3 . — S. 273–278 . . I Gesammelte Werke (1886), bind 1, side 439-446.
- Thomas W. Tucker. Der er kun én gruppe af slægt to // Journal of Combinatorial Theory, Series B. - 1984. - V. 36 , no. 3 . — S. 269–275 . - doi : 10.1016/0095-8956(84)90032-7 .
- W. Threlfall. Gruppebilleder // Abhandlungen der Mathematisch-Physischen Klasse der Sächsischen Akademie der Wissenschaften. - 1932. - T. 41 , Nr. 6 . — S. 1–59 . .
- Afsløring af skulpturen.
Eksterne links
- Weisstein, Eric W. Möbius-Kantor Graph (engelsk) på Wolfram MathWorld -webstedet .
- Weisstein, Eric W. Möbius-Kantor Configuration (engelsk) på Wolfram MathWorld -webstedet .