Dejterov graf

Dejterov graf
ImeItalo José Dejter
Točke112
Povezave336
Polmer7
Premer7
Notranji obseg4
Avtomorfizem2688
Kromatično število2
Kromatični indeks4
Rod 
Značilnosti6-regularen
simetričen
Označba 

Dejterov graf je v teoriji grafov neusmerjeni 6-regularni graf s 112 točkami in 336 povezavami. Imenuje se po argentinsko-ameriškem matematiku Italu Joséju Dejteru.

Njegov notranji obseg je 6.[1][2][3][4][5][6][7] Dejterov graf se skonstruira z brisanjem kopije Hammingove kode dolžine 7 iz dvojiške 7-kocke.

Dejterov graf in po razširitvi vsak graf skonstruiran z brisanjem Hammingove kode dolžine 2r-1 iz (2r-1)-kocke je simetrični graf, zato je tudi točkovno in povezavno-prehoden, ni pa polprehoden. V Dejterovem grafu je še posebej možna 3-faktorizacija v dve kopiji Ljubljanskega grafa, ki je tretji najmanjši točkovno, ne pa tudi povezavno-prehoden graf s stopnjo regularnosti 3, imenovan tudi polsimetrični kubični graf, oziroma kubični polsimetrični graf.

Dokazano je, da se lahko Dejterov graf dejansko 2-pobarva, tako da sta oba podgrafa kopiji Ljubljanskega grafa. Ti dve kopiji vsebujeta točno 112 točk Dejterovega grafa in vsaka 168 povezav, njun notranji obseg pa je enak 10, medtem ko je notranji obseg Dejterovega grafa enak 6, 7-kocke pa enak 4. Verjetno je Dejterov graf najmanjši simetrični graf, ki vsebuje po točkah povezani sebikomplementarni polsimetrični kubični podgraf.

Obe kopiji podgrafov Ljubljanskega grafa Dejterovega grafa se lahko predstavita kot prekrivna grafa Heawoodovega grafa, kot njegovi 8-prekritji. V vsaki od obeh predstavitev Ljubljanskega grafa se izmenično barvajo inverzne slike zaporednih točk Heawoodovega grafa glede na njegovo dvodelnost. Vsaka takšna inverzna slika se tvori iz 8-ih sosed vzdolž določene koordinatne smeri 7-kocke polovice Hammingove kode z določeno utežjo, 0 ali 1. Z izmenjevanjem teh uteži s permutacijo (0, 1) se lahko prehaja iz sosednosti Ljubljanskega grafa v eni barvi v sosednost druge barvne kopije Ljubljanskega grafa in obratno.

Sklici

  1. ↑ Klin; Lauri; Ziv-Av (2012).
  2. ↑ Borges; Dejter (1996).
  3. ↑ Dejter (1994).
  4. ↑ Dejter (1997).
  5. ↑ Dejter; Guan (1989).
  6. ↑ Dejter; Pujol (1995).
  7. ↑ Dejter; Weichsel (1993).

Viri

  • Borges, J.; Dejter, Italo José (1996). »On perfect dominating sets in hypercubes and their complements«. J. Combin. Math. Combin. Comput. Zv. 20. str. 161–173.
  • Dejter, Italo José (1994). »On symmetric subgraphs of the 7-cube: an overview«. Discrete Math. Zv. 124. str. 55–66.
  • Dejter, Italo José (1997). »Symmetry of factors of the 7-cube Hamming shell«. J. Combin. Des. Zv. 5. str. 301–309.
  • Dejter, Italo José; Guan, P. (1989). »Square-blocking edge subsets in hypercubes and vertex avoidance«. Graph theory, combinatorics, algorithms, and applications. San Francisco, CA. str. 162–174., SIAM, Philadelphia, PA, 1991
  • Dejter, Italo José; Pujol, J. (1995). »Perfect domination and symmetry in hypercubes«. Proceedings of the Twenty-sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing. Boca Raton, FL., Congr. Numer. 111 (1995), 18–32
  • Dejter, Italo José; Weichsel, P. M. (1993). »Twisted perfect dominating subgraphs of hypercubes«. Proceedings of the Twenty-fourth Southeastern International Conference on Combinatorics, Graph Theory, and Computing. Boca Raton, FL., Congr. Numer. 94 (1993), 67–78
  • Klin, Mikhail H.; Lauri, Josef; Ziv-Av, Matan (2012). »Links between two semisymmetric graphs on 112 vertices through the lens of association schemes« (PDF). Jour. Symbolic Comput. Zv. 47, št. 10. str. 1175–1191. doi:10.1016/j.jsc.2011.12.040.
Stub icon

Ta matematični članek je škrbina. Pomagajte Wikipediji in ga razširite.