Contele de Ljubljana

Graficul Ljubljana este un graf bipartit nedirecționat cu 112 vârfuri și 168 de muchii [1] .

Graficul este un grafic cubic cu diametrul 8, raza 7, numărul cromatic 2 și indicele cromatic 3. Are circumferința 10 și are exact 168 de cicluri de lungime 10. Există și 168 de cicluri de lungime 12 [2] .

Clădire

Graficul Ljubljana este hamiltonian și poate fi construit dintr-un cod LCF  : [47, -23, -31, 39, 25, -21, -31, -41, 25, 15, 29, -41, -19, 15, -49, 33, 39, -35, -21, 17, -33, 49, 41, 31, -15, -29, 41, 31, -15, -25, 21, 31, -51, -25, 23, 9, -17, 51, 35, -29, 21, -51, -39, 33, -9, -51, 51, -47, -33, 19, 51, -21, 29, 21, - 31, -39] 2 .

Graficul Ljubljana este graficul Lévy al configurației Ljubljana, o configurație fără patrulaturi cu 56 de linii și 56 de puncte [2] . În această configurație, fiecare linie conține exact 3 puncte, fiecare punct aparține exact a 3 linii și oricare două linii se intersectează în cel mult un punct.

Proprietăți algebrice

Grupul de automorfism al grafului Ljubljana este un grup de ordinul 168. Acționează tranzitiv pe muchii, dar nu pe vârfuri - există simetrii care duc orice muchie la orice altă muchie, dar nu există o simetrie care să ducă orice vârf la orice alt vârf. . Prin urmare, graficul Ljubljana este un grafic semisimetric , al treilea grafic semisimetric cubic după graficul Gray cu 54 de vârfuri și graficul Ivanov-Iofinova cu 110 vârfuri [3] .

Polinomul caracteristic al graficului Ljubljana este

Istorie

Contele Ljubljana a fost publicat pentru prima dată în 1993 de Brouwer, Dejter și Thomassen [4] ca un subgraf auto-complementar al Contelui Dejter [5] .

În 1972, Brouwer vorbea deja despre un graf cubic cu 112 vârfuri tranzitiv, dar nu tranzitiv, găsit de Foster , dar nepublicat [6] . Conder, Malnic, Marušić și Potocnik au redescoperit acest grafic cu 112 vârfuri în 2002 și l-au numit Contele de Ljubljana după capitala Sloveniei [2] . Ei au demonstrat că graficul a fost singurul graf cubic cu 112 vârfuri tranzitiv, dar nu tranzitiv și, prin urmare, este același grafic pe care l-a găsit Foster.

Galerie

• Graficul Ljubljana este hamiltonian și bipartit.

• Indicele cromatic al contelui de Ljubljana este 3.

• Desen alternativ al contelui de Ljubljana.

• Contele Ljubljana este Contele Levi din această configurație.

Note

1. ↑ Weisstein, Eric W. Ljubljana Graph  pe site- ul Wolfram MathWorld .
2. ↑ 1 2 3 Conder, Malnič, Marušič, Pisanski, Potočnik, 2002 .
3. ↑ Conder, Malnič, Marušič, Potočnik, 2006 , p. 255-294.
4. ↑ Brouwer, Dejter, Thomassen, 1993 , p. 25-29.
5. ↑ Klin, Lauri, Ziv-Av, 2012 , p. 1175–1191.
6. ↑ Bouwer, 1972 , p. 32-40.

Literatură

• Marston Conder, Aleksander Malnič, Dragan Marušič, Primož Potočnik. Un recensământ de grafice cubice semisimetrice pe până la 768 de vârfuri // Journal of Algebraic Combinatorics. - 2006. - T. 23 . — S. 255–294 . - doi : 10.1007/s10801-006-7397-3 .
• Brouwer AE, Dejter IJ, Thomassen C. Highly Symmetric Subgraphs of Hypercubes // J. Algebraic Combinat.. - 1993. - Vol. 2 .
• Klin M., Lauri J., Ziv-Av M. Legături între două grafice semisimetrice pe 112 vârfuri prin prisma schemelor de asociere // Jour. Calcul simbolic.. - 2012. - V. 7 , nr. 10 .
• Bouwer IZ pe margine, dar nu pe vârfuri, grafice regulate tranzitive // ​​J. Combin. th. Ser. B. - 1972. - Emisiune. 12 .
• Conder M., Malnič A., Marušič D., Pisanski T., Potočnik P. The Ljubljana Graph  // IMFM Preprints. - Ljubljana: Institutul de Matematică, Fizică și Mecanică, 2002. - V. 40 , nr. 845 .