On adjacency-transitive graphs. (English) Zbl 0891.05035
A graph automorphism of a graph \( \Gamma \) mapping each vertex of \( \Gamma \) onto itself or one of its neighbors is called an adjacency automorphism. An adjacency-transitive graph is a graph that possesses a vertex-transitive automorphism group generated by its adjacency automorphisms. In the first part of the paper, the relation between vertex-transitive, Cayley and adjacency-transitive graphs is investigated: quasiabelian Cayley graphs are shown to be adjacency-transitive; non-Cayley adjacency-transitive graphs, adjacency-transitive Cayley graphs that are not quasiabelian as well as Cayley graphs with no non-trivial adjacency automorphisms are constructed. The second half of the paper contains a classification of the cubic and four-valent adjacency-transitive graphs, all of which are isomorphic to Cayley graphs of abelian groups.
Reviewer: R.Jajcay (Terre Haute)
MSC:
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
References:
| [1] | Alspach, B.; Sutcliffe, R. J., Vertex-transitive graphs of order \(2p\), Ann. N. Y. Acad. Sci., 319, 18-27 (1979) · Zbl 0481.05033 |
| [2] | Biggs, N., Algebraic Graph Theory (1994), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0797.05032 |
| [3] | Godsil, C. D., More odd graph theory, Discrete Math., 27, 205-207 (1980) · Zbl 0438.05053 |
| [4] | Marušič, D., Vertex transitive graphs and digraphs of order \(p^k\), Ann. Discrete Math., 27, 115-128 (1985) · Zbl 0571.05024 |
| [5] | Pacco, W.; Scapellato, R., Digraphs having the same canonical double covering, Discrete Math., 173, 291-296 (1997) · Zbl 0881.05052 |
| [6] | Praeger, C. E.; Xu, M.-Y., Vertex-primitive graphs of order a product of two distinct primes, J. Combin. Theory Ser. B, 59, 245-266 (1993) · Zbl 0793.05072 |
| [7] | Trofimov, V. I., Bounded automorphisms of graphs and the characterization of grids, Izv. Akad. Nauk SSSR Ser. Mat., 47, 407-420 (1983) · Zbl 0519.05037 |
| [8] | Wang, J.; Xu, M. Y., A class of hamiltonian Cayley graphs and Parsons graphs, European J. Combin., 18, 567-600 (1997) |
| [9] | Wielandt, H., Permutation Groups (1966), Academic Press: Academic Press New York |
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.
