Vol. LXXIX, 2 (2010)
p. 175 - 180

Characterization of simple orbit graphs

A. Bretto, A. Faisant, C. Jaulin and J. Tomanová

Received: March 9, 2009;   Revised: February 2, 2010;   Accepted: May 5, 2010

Abstract.   Let G be a (finite) group and let S be a non-empty subset of G. The vertex set of the orbit graph O(G,S) is the collection, over all s Î S, of orbits of left translations induced by s. If u and v are distinct vertices (each representing an orbit of some s and t from S), then for any gÎ G appearing in both orbits there is an edge colored g in O(G,S) joining u and v. Orbit graphs are an important special case of "G-graphs" introduced by Bretto and Faisant in Math. Slovaca 55 (2005). In this paper we characterize simple orbit graphs and apply the result to show that certain class of simple orbit graphs is closed under the construction of incidence graphs.

Keywords:  orbit graph, G-graph, automorphism group  

AMS Subject classification: Primary:  05C25  

PDF                               Compressed Postscript                                 Version to read

Acta Mathematica Universitatis Comenianae
ISSN 0862-9544   (Printed edition)

Faculty of Mathematics, Physics and Informatics
Comenius University
842 48 Bratislava, Slovak Republic  

Telephone: + 421-2-60295111 Fax: + 421-2-65425882  
e-Mail:    Internet: