Ljubljanski graf
Ljubljanski graf[2]:32 je v teoriji grafov neusmerjeni dvodelni graf s 112 točkami in 168 povezavami.
Ljubljanski graf | |
---|---|
Ime | Ljubljana |
Točke | 112 |
Povezave | 168 |
Polmer | 7 |
Premer | 8 |
Notranji obseg | 10 |
Avtomorfizem | 168 |
Kromatično število | 2 |
Kromatični indeks | 3 |
Značilnosti | kubičen regularen dvodelen polsimetričen Hamiltonov |
Označba | [1] |
Je kubični graf s premerom 8, polmerom 7, kromatičnim številom 2 in kromatičnim indeksom 3. Njegov notranji obseg je 10, v njem pa je točno ciklov dolžine 10. Graf ima tudi 168 ciklov dolžine 12.[1]
Konstrukcija
urediLjubljanski graf je Hamiltonov graf in se ga lahko skonstruira iz zapisa 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.
Ljubljanski graf je Levijev graf s konfugracijo Ljubljanskega grafa, konfiguracijo brez pravih kotov s 56 daljicami in 56 točkami.[1] V takšni konfiguraciji vsaka daljica vsebuje točno 3 točke, vsaka točka pripada točno 3 daljicam in poljubni par daljic se seka v samo eni točki.
Algebrske značilnosti
urediGrupa avtomorfizmov Ljubljanskega grafa je grupa reda 168. Ljubljanski graf je točkovnoprehoden, ne pa tudi povezavno. Graf ima avtomorfizme za vsak par točk, ne pa za povezave. Zaradi tega je Ljubljanski graf polsimetrični graf, tretji najmanjši kubični polsimetrični graf za Grayjevim grafom s 54 točkami in grafom Jofinove in Ivanova s 110 točkami.[3]
Karakteristični polinom Ljubljanskega grafa je:
Zgodovina
urediČlanek o Ljubljanskem grafu so prvič objavili Brouwer, Dejter in Thomassen leta 1993[4] kot sebikomplementarni podgraf Dejterovega grafa.[5]
Leta 1972 je Bouwer že govoril o kubičnem grafu s 112 točkami, točkovno-prehodnem, ne pa tudi povezavno, ki ga je odkril Foster, vendar ni objavil članka o njem.[6] Conder, Malnič, Marušič, Pisanski in Potočnik so ga odkrili neodvisno leta 2002 in ga po Conderjevem predlogu imenovali po Ljubljani.[1] Dokazali so, da gre za edini graf s takšno značilnostjo prehodnosti, ki ga je odkril že Foster.
Upodobitve
uredi-
Kromatično število Ljubljanskega grafa je 2.
-
Kromatični indeks Ljubljanskega grafa je 3.
-
Alternativna upodobitev Ljubljanskega grafa.
-
Ljubljanski graf je Levijev graf s to konfiguracijo.
-
Ljubljanski graf z vloženim Heawoodovim grafom.
Glej tudi
urediSklici
urediViri
uredi- Alizadeh, Yaser; Klavžar, Sandi (2012), The Wiener dimension of a graph
- Bouwer, Izak Zurk (1972), »On Edge But Not Vertex Transitive Regular Graphs«, J. Combin. Th. Ser. B, 12: 32–40, doi:10.1016/0095-8956(72)90030-5
- Brouwer, Andries Evert; Dejter, Italo Jose; Thomassen, Carsten (1993), »Highly Symmetric Subgraphs of Hypercubes« (PDF), J. Algebr. Comb., 2: 25–29, doi:10.1023/A:1022472513494, arhivirano iz prvotnega spletišča (PDF) dne 30. junija 2016, pridobljeno 20. junija 2016
- Conder, Marston; Dobson, Edward; Ito, Tatsuro (2013), Phd summer school in discrite mathematics (PDF), Koper: University of Primorska Press, COBISS 271775744, ISBN 978-961-6832-62-5
- Conder, Marston; Malnič, Aleksander; Marušič, Dragan; Pisanski, Tomaž; Potočnik, Primož (2002), »The Ljubljana Graph« (PDF), Preprint series / University of Ljubljana, Institute of Mathematics, Physics and Mechanics, Department of Mathematics, 40 (845): 1–15, COBISS 12107353, ISSN 1318-4865, arhivirano iz prvotnega spletišča (PDF) dne 27. avgusta 2016, pridobljeno 20. junija 2016
- Conder, Marston; Malnič, Aleksander; Marušič, Dragan; Pisanski, Tomaž; Potočnik, Primož (2005), »The edge-transitive but not vertex-transitive cubic graph on 112 vertices«, J. Graph Theory, 50 (1): 25–42, COBISS 13740377, doi:10.1002/jgt.20089
- Conder, Marston; Malnič, Aleksander; Marušič, Dragan; Potočnik, Primož (2006), »A census of semisymmetric cubic graphs on up to 768 vertices«, J. Algebr. Comb., 23 (3): 255–294, COBISS 13973081, doi:10.1007/s10801-006-7397-3
- 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., 47 (10): 1175–1191, doi:10.1016/j.jsc.2011.12.040
- Kuzman, Boštjan (2011), Oris razvoja teorije grafov v Sloveniji (PDF), DMFA[mrtva povezava]
- Lukšič, Primož; Pisanski, Tomaž (2006), Distance-residual graphs (PDF), arXiv:math/0609810