No label defined (Q4352276)

As with most of the articles in the collection, this article is mainly an expository paper based upon its author's series of five invited lectures given at the NATO Advanced Study Institute held in Montréal in July, 1996. Its intent is to instruct the mathematician who has some background in graph theory and group theory about the research frontiers inhabited by the author in recent years. Graduate students and other researchers should find this work to be a very readable, cohesive, and informative article. Following a brief introduction, the first chapter introduces essential graph theoretical notions such as various graph products and metric properties, e.g., distance regularity and strong regularity. Chapter 2 does the same for permutation group notions, especially as they may be applied to graphs, e.g., orbitals and orbital digraphs and an assortment of ``useful'' families of vertex-transitive graphs and digraphs. By far the longest chapter, Chapter 3 includes results from a series of papers (published between 1988 and 1996) by both D. Marušič alone and jointly with the author. The proof is presented of a major and rather complex theorem, namely the classification of all vertex-transitive graphs of order \(pq\) where \(p\) and \(q\) are distinct primes. Chapter 4 poses two problems which remain unresolved in the general case. The first, posed by \textit{D. Marušič} [Discrete Math. 36, 69-81 (1981; Zbl 0459.05041)] asks whether every vertex-transitive graph (digraph) admits a fixed-point-free automorphism whose orbits are all of equal length. The answer is affirmative for 3-valent graphs and for digraphs of order \(2p^2\), where \(p\) is prime. The second question asks, is every Cayley graph hamiltonian? Various sufficient conditions are presented for an affirmative answer. Chapters 5 and 6 present the author's joint work with Walter Pacco, not yet in print. The categorical product \(B(\Gamma):=\Gamma\times K_2\) is called the canonical double cover of \(\Gamma\). Given a graph \(\tilde\Gamma\), the number of non-isomorphic graphs \(\Gamma\) is determined such that \(\tilde\Gamma=B(\Gamma)\). The material of Chapter 6 is based on the following related notion. For a set \(V\), let \({\mathcal G}\leq\text{Sym}(V)\times\text{Sym}(V)\). Fix \((a,b)\in V\times V\). The digraph with vertex set \(V\) and arc set \({\mathcal G}(a,b):=\{(g(a),h(b)):(g,h)\in{\mathcal G}\}\) is a two-fold orbital digraph, which generalizes the notion of orbital digraphs presented earlier. For the entire collection see [Zbl 0868.00039].