Count Ljubljana is an undirected bipartite graph with 112 vertices and 168 edges [1] .
| Count Ljubljana | |
|---|---|
 Count Ljubljana as a Count Hiwood | |
| Top | 112 |
| Riber | 168 |
| Radius | 7 |
| Diameter | eight |
| Girth | ten |
| Automorphisms | 168 |
| Chromatic number | 2 |
| Chromatic Index | 3 |
| The properties | Cubic Hamilton Semi-symmetrical |
A graph is a cubic graph with a diameter of 8, radius 7, chromatic number 2 and chromatic index 3. Its girth is 10 and it has exactly 168 cycles of length 10. There are also 168 cycles of length 12 [2] .
Build
Count Ljubljana Hamiltonians and can be built from the LCF code : [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 .
The Ljubljana graph is the Levy graph of the Ljubljana configuration, a configuration without quadrangles with 56 lines and 56 points [2] . In this configuration, each line contains exactly 3 points, each point belongs to exactly 3 lines and any two lines intersect at most at one point.
Algebraic properties
The automorphism group of the Ljubljana graph is a group of order 168. It acts transitively on edges, but not on vertices - there are symmetries that translate any edge to any other edge, but there is no symmetry that translates any vertex to any other vertex. Therefore, the Ljubljana graph is a semisymmetric graph , the third cubic semisymmetric graph after the Gray graph with 54 vertices and the Ivanov – Iofinova graph with 110 vertices [3] .
The characteristic polynomial of the graph Ljubljana is
History
Count Ljubljana was first published in 1993 by Brower, Degter and Thomassen [4] as a self-complementary subgraph of Count Degger [5] .
In 1972, Brower already spoke of a 112-vertex edge-transitive, but not vertex-transitive, cubic graph found by Foster , but not published [6] . Conder, Malnich, Marusic and Potochnik rediscovered this 112-vertex count in 2002 and named it Count Ljubljana by the name of the capital of Slovenia [2] . They proved that the graph was the only 112-vertex edge-transitive, but not vertex-transitive, cubic graph, and therefore this is the same graph that Foster found.
Gallery
Count Ljubljana is Hamiltonian and dicotyledonous.
The chromatic index of the Ljubljana graph is 3.
An alternative drawing of Count Ljubljana.
Count Ljubljana is the Levy Count of this configuration.
Notes
- ↑ Weisstein, Eric W. Ljubljana Graph on the Wolfram MathWorld website.
- ↑ 1 2 3 Conder, Malnič, Marušič, Pisanski, Potočnik, 2002 .
- ↑ Conder, Malnič, Marušič, Potočnik, 2006 , p. 255-294.
- ↑ Brouwer, Dejter, Thomassen, 1993 , p. 25-29.
- ↑ Klin, Lauri, Ziv-Av, 2012 , p. 1175–1191.
- ↑ Bouwer, 1972 , p. 32-40.
Literature
- Marston Conder, Aleksander Malnič, Dragan Marušič, Primož Potočnik. A census of semisymmetric cubic graphs on up to 768 vertices // 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. Links between two semisymmetric graphs on 112 vertices through the lens of association schemes // Jour. Symbolic Comput .. - 2012 .-- T. 7 , no. 10 .
- Bouwer IZ On Edge But Not Vertex Transitive Regular Graphs // J. Combin. Th. Ser. B. - 1972. - Vol. 12 .
- Conder M., Malnič A., Marušič D., Pisanski T., Potočnik P. The Ljubljana Graph // IMFM Preprints. - Ljubljana: Institute of Mathematics, Physics and Mechanics, 2002 .-- V. 40 , no. 845 .