Dejter grófja

A Dejter-gráf egy 6-reguláris gráf, 112 csúcsgal, 336 éllel és 4 [1] [2] [3] [4] [5] [6] [7] kerülettel . A Dejter-gráfot úgy kapjuk meg, hogy eltávolítjuk a 7-es hosszúságú Hamming-kód másolatát a bináris 7-es kockából .

Leírás

A Dejter-gráf és bármely gráf, amelyet egy 2 r -1 hosszúságú Hamming-kód eltávolításával kapunk egy (2 r -1) -kockából , szimmetrikus gráf (és ezért csúcstranzitív és éltranzitív , de nem féltranzitív ). Konkrétan a Dejter-gráf lehetővé teszi a ljubljanai gráf 3-as felbontását , amely a harmadik legkisebb éltranzitív gráf, de nem egy reguláris 3-as fokú csúcstranzitív gráf. Az ilyen gráfokat félszimmetrikus köbös gráfoknak nevezzük .

Valójában bebizonyosodott, hogy a Dejter-gráf kétszínű is lehet, mondjuk a {piros, kék} halmaz segítségével, mint a jobb oldali felső ábrán, így mindkét, azonos színű élekből álló gráf másolata a ljubljanai grafikon . Ez a két másolat a Dejter gráfnak pontosan 112 csúcsát és egyenként 168 élét tartalmazza, mindkét példány kerülete 10, míg a Dejter gráf 6, a 7-kocka pedig 4. Úgy tűnik, a Dejter gráf a legkisebb szimmetrikus gráf , amelynek van egy összefüggő önkomplementer csúcsfeszesítő félszimmetrikus köbös részgráfja.

A Dejter-gráf csúcsait összekötő vörös és kék ljubljanai részgráfok egyaránt ábrázolhatók a Heawood- gráf fedőgráfjaiként, vagyis a Heawood -gráf 8-borításaként . Ezt a ljubljanai gráf mindkét ábrázolásánál (piros felül, kék alul, mindkettő jobb oldalon) úgy kaphatjuk meg, hogy felváltva színezzük a Heawood-gráf egymást követő csúcsait , mondjuk feketére és fehérre (jobban látható, ha duplán kattintunk a képen a nagyításhoz), mert a Heawood-gráf kétrészes . Minden ilyen képet 8 szomszéd alkot a 7-es kocka fix koordinátája mentén, a Hamming-kód felének fix súlya 0 vagy 1. Ezeknek a súlyoknak a cseréjével, a (0 1) permutálásával el lehet lépni a meghatározott szomszédságtól. a piros Ljubljana gráf a Ljubljana kék gráf által meghatározott szomszédsághoz és fordítva.

A Dejter-gráf hetedik része az alábbi külön ábrán látható, és a Heawood-gráf két eredményül kapott másolatából nyerhető .

Jegyzetek

1. ↑ Klin, Lauri, Ziv-Av, 2012 , p. 1175–1191.
2. ↑ Borges, Dejter, 1996 , p. 161-173.
3. ↑ Dejter, 1994 , p. 55–66.
4. ↑ Dejter, 1997 , p. 301–309.
5. ↑ Dejter, Guan, 1989 , p. 162–174.
6. ↑ Dejter, Pujol, 1995 , p. 18-32.
7. ↑ Dejter, Weichsel, 1993 , p. 67–78.

Irodalom

• Klin M., Lauri J., Ziv-Av M. Kapcsolatok két félszimmetrikus gráf között 112 csúcson az asszociációs sémák lencséjén keresztül // Jour. Symbolic Comput.. - 2012. - V. 47 , sz. 10 .
• Borges J., Dejter IJ A tökéletes uralkodó halmazokról hiperkockákban és azok komplementereiben // J. Combin. Math. Kombájn. Comput.. - 1996. - Kiadás. 20 .
• Dejter IJ A 7-kocka szimmetrikus részgráfjairól: áttekintés // Discrete Math.. - 1994. - Vol. 124 .
• Dejter IJ A 7 kockából álló Hamming-héj faktorainak szimmetriája // J. Combin. Des.. - 1997. - Issue. 5 .
• Dejter IJ, Guan P. Négyzetblokkoló él részhalmazok hiperkockákban és csúcs elkerülésében // Gráfelmélet, kombinatorika, algoritmusok és alkalmazások, SIAM. – San Francisco, CA, 1989.
• Dejter IJ, Pujol J. Perfect dominanation and symmetry in hypercubes // Proceedings of the Twenty-sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing. - Boca Raton, Florida, 1995. - T. 111. - (Congr. Numer.).
• Dejter IJ, Weichsel PM Twisted perfect dominating subgraphs of hypercubes // Proceedings of the Twenty-4th Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, Florida, 1993).. - 1993.