Två-graf

I matematik är en tvågraf en uppsättning (oordnade) trippel vald från en finit vertexuppsättning X , så att varje (oordnad) fyrdubbling från X innehåller ett jämnt antal trippel av tvågrafen. En vanlig två-graf har egenskapen att varje par hörn ligger i samma antal trippel av två-grafen. Två-grafer har studerats på grund av deras koppling till ekvikantiga linjer och, för vanliga två-grafer, starkt regelbundna grafer , och även ändliga grupper eftersom många vanliga två-grafer har intressanta automorfismgrupper .

En två-graf är inte en graf och bör inte förväxlas med andra objekt som kallas 2-grafer i grafteorin , till exempel 2-regelbundna grafer .

Exempel

På uppsättningen av hörn {1,...,6} är följande samling av oordnade trippel en tvågraf:

123 124 135 146 156 236 245 256 345 346

Denna två-graf är en vanlig två-graf eftersom varje par av distinkta hörn visas tillsammans i exakt två tripplar.

Givet en enkel graf G = ( V , E ), bildar mängden trippel av vertexmängden V vars inducerade subgraf har ett udda antal kanter en tvågraf på mängden V . Varje tvågraf kan representeras på detta sätt. Detta exempel hänvisas till som standardkonstruktionen av en tvågraf från en enkel graf.

Som ett mer komplext exempel, låt T vara ett träd med kantuppsättning E . Mängden av alla trippel av E som inte ingår i en väg av T bildar en tvågraf på mängden E .

Växling och grafer

Växla {X,Y} i en graf

En två-graf är ekvivalent med en växlingsklass av grafer och även med en (signerad) växlingsklass av signerade kompletta grafer .

Att byta en uppsättning av hörn i en (enkel) graf innebär att vända närliggande till varje par av hörn, en i uppsättningen och den andra inte i uppsättningen: sålunda ändras kantuppsättningen så att ett angränsande par blir icke-intilliggande och ett icke-angränsande par blir intilliggande. Kanterna vars ändpunkter båda är i uppsättningen, eller båda inte i uppsättningen, ändras inte. Grafer är växlingslikvärdiga om den ena kan erhållas från den andra genom att växla. En ekvivalensklass av grafer under växling kallas en växlingsklass . Switching introducerades av van Lint & Seidel (1966) och utvecklades av Seidel; det har kallats grafväxling eller Seidelväxling , delvis för att skilja det från växling av signerade grafer .

I standardkonstruktionen av en tvågraf från en enkel graf som ges ovan, kommer två grafer att ge samma tvågraf om och endast om de är ekvivalenta under omkoppling, det vill säga de är i samma omkopplingsklass.

Låt Γ vara en tvågraf på mängden X . För alla element x i X , definiera en graf Γ _x med vertexuppsättning X med hörn y och z intill om och endast om { x , y , z } är i Γ. I denna graf x att vara en isolerad vertex. Denna konstruktion är vändbar; givet en enkel graf G , anslut ett nytt element x till uppsättningen av hörn av G , behåll samma kantuppsättning, och tillämpa standardkonstruktionen ovan.

Till en graf G motsvarar en förtecknad komplett graf Σ på samma vertexuppsättning, vars kanter är signerade negativa om i G och positiva om inte i G . Omvänt G subgrafen av Σ som består av alla hörn och alla negativa kanter. Två-grafen för G kan också definieras som uppsättningen av trippel av hörn som stöder en negativ triangel (en triangel med ett udda antal negativa kanter) i Σ. Två signerade kompletta grafer ger samma två-graf om och endast om de är likvärdiga under byte.

Växling av G och Σ är relaterade: byte av samma hörn i båda ger en graf H och dess motsvarande förtecknade fullständiga graf.

Adjacency matris

Närliggande matris för en två-graf är närliggande matris för motsvarande signerade fullständiga graf; alltså är den symmetrisk , är noll på diagonalen och har ingångar ±1 utanför diagonalen. Om G är den graf som motsvarar den förtecknade fullständiga grafen Σ, kallas denna matris (0, −1, 1)-angränsningsmatrisen eller Seidel-angränsningsmatrisen för G . Seidel-matrisen har noll poster på huvuddiagonalen, -1 poster för angränsande hörn och +1 poster för icke-angränsande hörn.

Om graferna G och H är i samma omkopplingsklass, sammanfaller multiuppsättningen av egenvärden för två Seidel-angränsande matriser för G och H eftersom matriserna är lika.

En tvågraf på en mängd V är regelbunden om och endast om dess närliggande matris har bara två distinkta egenvärden ρ ₁ > 0 > ρ ₂ säg, där ρ ₁ ρ ₂ = 1 - | V |.

Likkantiga linjer

Varje tvågraf är ekvivalent med en uppsättning linjer i något dimensionellt euklidiskt utrymme där varje par möts i samma vinkel. Uppsättningen linjer konstruerade från en två graf på n hörn erhålls enligt följande. Låt -ρ vara det minsta egenvärdet för Seidels närliggande matris , A , i tvågrafen, och anta att den har multiplicitet n - d . Då är matrisen ρ I + A positiv semidefinitiv av rang d och kan således representeras som Gram-matrisen för de inre produkterna av n vektorer i euklidiskt d -rum. Eftersom dessa vektorer har samma norm (nämligen ${\sqrt {\rho }}$ ) och ömsesidiga inre produkter ±1, möts alla par av de n linjerna som spänner över av dem i samma vinkel φ där cos φ = 1/ρ. Omvänt kan varje uppsättning icke-ortogonala ekvikantiga linjer i ett euklidiskt utrymme ge upphov till en två-graf (se ekvikantiga linjer för konstruktionen).

Med notationen enligt ovan uppfyller den maximala kardinaliteten n n ≤ d (ρ ² - 1)/(ρ ² - d ) och gränsen uppnås om och endast om två-grafen är regelbunden.

Anteckningar

Brouwer, AE , Cohen, AM och Neumaier, A. (1989), Distance-Regular Graphs. Springer-Verlag, Berlin. Avsnitt 1.5, 3.8, 7.6C.

Cameron, PJ; van Lint, JH (1991), Designs, Graphs, Codes and their Links , London Mathematical Society Student Texts 22, Cambridge University Press, ISBN 978-0-521-42385-4

Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (2nd ed.), Boca Raton: Chapman & Hall/ CRC, s. 875–882, ISBN 1-58488-506-8

Chris Godsil och Gordon Royle (2001) , Algebraisk grafteori. Graduate Texts in Mathematics, Vol. 207. Springer-Verlag, New York. Kapitel 11.

Seidel, JJ (1976), A survey of two-graphs. I: Colloquio Internazionale sulle Teorie Combinatorie (Proceedings, Rom, 1973), Vol. I, s. 481–511. Atti dei Convegni Lincei, nr 17. Accademia Nazionale dei Lincei, Rom.

Taylor, DE (1977), Regular 2-graphs. Proceedings of the London Mathematical Society (3), vol. 35, s. 257–274.

van Lint, JH; Seidel, JJ (1966), "Equilateral point sets in elliptic geometry", Indagationes Mathematicae , Proc. Koninkl. Ned. Akad. Wetenschap. Ser. A 69, 28 : 335–348