Cores of Imprimitive Symmetric Graphs of Order a Product of Two Distinct Primes

摘要

A retract of a graph is an induced subgraph of such that there exists a homomorphism from to whose restriction to is the identity map. A graph is a core if it has no nontrivial retracts. In general, the minimal retracts of a graph are cores and are unique up to isomorphism; they are called the core of the graph. A graph is G-symmetric if G is a subgroup of the automorphism group of that is transitive on the vertex set and also transitive on the set of ordered pairs of adjacent vertices. If in addition the vertex set of admits a nontrivial partition that is preserved by G, then is an imprimitive G-symmetric graph. In this paper cores of imprimitive symmetric graphs of order a product of two distinct primes are studied. In many cases the core of is determined completely. In other cases it is proved that either is a core or its core is isomorphic to one of two graphs, and conditions on when each of these possibilities occurs is given.