Cores of imprimitive symmetric graphs of order a product of two distinct primes

preprint2016arXivOpen access

Abstract

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 GG-symmetric if GG 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 GG, then ΓΓ is an imprimitive GG-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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.