The 10-cages and derived configurations. (English) Zbl 1030.05083
Summary: Symmetry properties of the three 10-cages on 70 vertices are investigated. Being bipartite, these graphs are Levi graphs of triangle- and quadrangle-free \((35_3)\) configurations. For each of these graphs a Hamilton cycle is given via the associated LCF notation. Furthermore, the automorphism groups of respective orders 80, 120, and 24 are computed. A special emphasis is given to the A. T. Balaban 10-cage, the first known example of a 10-cage [Rev. Roum. Math. Pure Appl. 18, 1033-1043 (1973; Zbl 0263.05112)], and the corresponding Balaban configuration. It is shown that the latter is linear, that is, it can be realized as a geometric configuration of points and lines in the Euclidean plane. Finally, based on the Balaban configuration, an infinite series of linear triangle-free and quadrangle-free (\((7n)_3\)) configurations is produced for each odd integer \(n \geqslant 5\).
MSC:
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 51A20 | Configuration theorems in linear incidence geometry |
| 05C45 | Eulerian and Hamiltonian graphs |
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
Citations:
Zbl 0263.05112Software:
GENREGOnline Encyclopedia of Integer Sequences:
Number of self-polar configurations of type (n_3).Number of cyclic configurations of type (n_3).
Number of geometrical configurations of type (n_3).
Number of self-dual combinatorial configurations of type (n_3).
References:
| [1] | Balaban, A. T., Trivalent graphs of girth nine and eleven and relations among cages, Rev. Roumaine Math. Pure Appl., 18, 1033-1043 (1973) · Zbl 0263.05112 |
| [2] | A.T. Balaban, Reaction Graphs, in: D. Bonchev, O. Mekenyan (Eds.), Graph Theoretical Approaches to Chemical Reactivity (Understanding Chemical Reactivity), Vol. 9, Kluwer Academic Publishers, Dordrecht, 1994.; A.T. Balaban, Reaction Graphs, in: D. Bonchev, O. Mekenyan (Eds.), Graph Theoretical Approaches to Chemical Reactivity (Understanding Chemical Reactivity), Vol. 9, Kluwer Academic Publishers, Dordrecht, 1994. |
| [3] | Betten, A.; Brinkmann, G.; Pisanski, T., Counting symmetric configurations \(v_3\), Discrete Appl. Math., 99, 331-338 (2000) · Zbl 0940.05020 |
| [4] | M. Boben, T. Pisanski, Coordinatizations of the configurations arising from the 10-Cages,; M. Boben, T. Pisanski, Coordinatizations of the configurations arising from the 10-Cages, · Zbl 1023.51009 |
| [5] | Boben, M.; Pisanski, T., Polycyclic configurations, European J. Combin., 24, 431-457 (2003) · Zbl 1023.51009 |
| [6] | Bokowski, J.; Sturmfels, B., Computational Synthetic Geometry, Lecture Notes in Mathematics, Vol. 1355 (1989), Springer: Springer Heidelberg · Zbl 0683.05015 |
| [7] | D. Bonchev, O. Mekenyan, Graph Theoretical Approaches to Chemical Reactivity (Understanding Chemical Reactivity), Vol. 9, Kluwer Academic Publishers, Dordrecht, 1994.; D. Bonchev, O. Mekenyan, Graph Theoretical Approaches to Chemical Reactivity (Understanding Chemical Reactivity), Vol. 9, Kluwer Academic Publishers, Dordrecht, 1994. |
| [8] | Brinkmann, G.; McKay, B. D.; Saager, C., The smallest cubic graph of girth 9, Combin. Probab. Comput., 5, 1-13 (1995) |
| [9] | P.J. Cameron (Ed.), Problems from the Fifteenth British Combinatorial Conference; Discrete Math. 167/168 (1997) 605-615.; P.J. Cameron (Ed.), Problems from the Fifteenth British Combinatorial Conference; Discrete Math. 167/168 (1997) 605-615. · Zbl 0870.05075 |
| [10] | Cameron, P. J.; Giudici, M.; Jones, G. A.; Kantor, W. M.; Klin, M. H.; Marušič, D.; Nowitz, L. A., Transitive permutation groups without regular subgroups, J. London Math. Soc., 66, 2, 325-333 (2002) · Zbl 1015.20001 |
| [11] | Coxeter, H. S.M., Self-dual configurations and regular graphs, Bull. Amer. Math. Soc., 56, 413-455 (1950) · Zbl 0040.22803 |
| [12] | Frucht, R., A canonical representation of trivalent Hamiltonian graphs, J. Graph Theory, 1, 45-60 (1977) · Zbl 0358.05029 |
| [13] | Giudici, M., Quasiprimitive groups with no fixed, point free elements of prime order, J. London Math. Soc., 67, 2, 73-84 (2003) · Zbl 1050.20002 |
| [14] | Gross, J. L.; Tucker, T. W., Topological Graph Theory (1987), Wiley Interscience: Wiley Interscience New York · Zbl 0621.05013 |
| [15] | Grünbaum, B., Astral \((n_k)\) configurations, Geombinatorics, 3, 32-37 (1993) · Zbl 0845.51010 |
| [16] | B. Grünbaum, Special Topics in Geometry—Configurations, Math. 553B, University of Washington, Seattle, Spring, 1999.; B. Grünbaum, Special Topics in Geometry—Configurations, Math. 553B, University of Washington, Seattle, Spring, 1999. |
| [17] | Grünbaum, B., Astral \((n_4)\) configurations, Geombinatorics, 9, 127-134 (2000) · Zbl 0981.51014 |
| [18] | Klein, D. J.; Graovac, A.; Trinajstić, N.; Mihalić, Z., Excitation spectra for degenerate rearrangements, J. Mol. Struct., 341, 157-164 (1995) |
| [19] | Marušič, D., On vertex symmetric digraphs, Discrete Math., 36, 69-81 (1981) · Zbl 0459.05041 |
| [20] | Marušič, D., Vertex symmetric graphs and digraphs of order \(p^k\), Ann. Discrete Math., 27, 115-128 (1985) · Zbl 0571.05024 |
| [21] | Marušič, D.; Pisanski, T., Weakly flag-transitive configurations and half-arc-transitive graphs, European J. Combin., 20, 559-570 (1999) · Zbl 0945.05033 |
| [22] | Marušič, D.; Scapellato, R., Permutation groups, vertex-transitive graphs and semiregular automorphisms, European J. Combin., 19, 707-712 (1998) · Zbl 0912.05038 |
| [23] | B.D. McKay, W. Myrvold, J. Nadon, Fast backtracking principles applied to find new cages, Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, January 1998, pp. 188-191.; B.D. McKay, W. Myrvold, J. Nadon, Fast backtracking principles applied to find new cages, Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, January 1998, pp. 188-191. · Zbl 0930.68106 |
| [24] | Meringer, M., Fast generation of regular graphs and construction of cages, J. Graph Theory, 30, 137-146 (1999) · Zbl 0918.05062 |
| [25] | T. Pisanski, M. Randić, Bridges between Geometry and Graph Theory, in: C.A. Gorini (Ed.), Geometry at Work, MAA Notes, Vol. 53, Mathematical Association of America, Washington, DC, 2000, pp. 174-194.; T. Pisanski, M. Randić, Bridges between Geometry and Graph Theory, in: C.A. Gorini (Ed.), Geometry at Work, MAA Notes, Vol. 53, Mathematical Association of America, Washington, DC, 2000, pp. 174-194. |
| [26] | G. Royle,; G. Royle, |
| [27] | Schroth, A., How to draw a hexagon, Discrete Math., 199, 167-171 (1999) · Zbl 0939.51006 |
| [28] | White, A. T., Graphs of Groups on Surfaces, North-Holland Mathematics Studies, Vol. 188 (2001), North-Holland: North-Holland Amsterdam · Zbl 0378.05028 |
| [29] | Wong, P. K., Cages—a survey, J. Graph Theory, 6, 1-22 (1982) · Zbl 0488.05044 |
| [30] | Wong, P. K., On the smallest graphs of girth 10 and valency 3, Discrete Math., 43, 119-124 (1983) · Zbl 0507.05039 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
