Paper Info
Title
Representativity of Cayley maps
Abstract
The motivating question of this paper is to ask when, given a group A and generating set X for A, one can find a Cayley map CM(A,X,@r) with representativity at least two (also called a strong embedding of the graph; note that in such an embedding, each face is bounded by a cycle of the graph). We first investigate some general consequences of a Cayley map's having representativity one, which means that there exist faces that are self-adjacent (and consequently these faces are not bounded by proper cycles of the graph). We find that there exist Cayley graphs of Abelian groups all of whose Cayley maps have representativity one. This indicates that if these graphs have strong embeddings (orientable or non-orientable), then these embeddings cannot be obtained by applying the symmetry of Cayley graphs in the most natural way. This also indicates that the Cycle Double Cover of these graphs, if it exists, cannot be constructed by applying the symmetry of these graphs in the most natural way. In addition, we investigate specific consequences in the case |X|=2 or 3; we provide a few classes of examples of A and X which may be forced to have representativity at least two; and we provide a combinatorial formalism for calculating the representativity of a Cayley map without appealing to the ''lifted'' embedding.
Year
DOI
Venue
2014
10.1016/j.ejc.2013.12.006
Eur. J. Comb.
Keywords
Field
DocType
group a,strong embedding,cayley graph,abelian group,strong embeddings,general consequence,combinatorial formalism,cayley map,specific consequence,proper cycle
Discrete mathematics,Combinatorics,Embedding,Vertex-transitive graph,Cayley table,Cayley's theorem,Cayley transform,Cayley graph,Cycle double cover,Mathematics,Bounded function
Journal
Volume
ISSN
Citations 
39,
0195-6698
0
PageRank 
References 
Authors
0.34
2
3
Name
Order
Citations
PageRank
D. Christopher Stephens1193.93
Thomas W. Tucker2191130.07
Xiaoya Zha310420.82