Symmetric graphs and interconnection networks

摘要

An interconnection network is usually modelled by an undirected graph in which vertices represent processors or memory modules, and edges represent communication links. It is known that the symmetric properties of a graph (such as the vertex regularity, vertex transitivity, edge transitivity, arc transitivity) are the better parameters to measure the stability and synchronizability of an interconnection network. In this paper, we study a subclass of pentavalent symmetric graphs of cube-free order, that is, the case of order36p, wherepis a prime. A complete classification is given of such graphs. As a byproduct, the classification result includes a non-quasiprimitive graph admitting a quasiprimitive 2-arc-transitive group action. To our knowledge, this is the first known example in pentavalent 2-arc-transitive graphs.