Premium
Self‐Complementary Vertex‐Transitive Graphs Need Not be Cayley Graphs
Author(s) -
Li Cai Heng,
Praeger Cheryl E.
Publication year - 2001
Publication title -
bulletin of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 2.396
H-Index - 48
eISSN - 1469-2120
pISSN - 0024-6093
DOI - 10.1112/s0024609301008505
Subject(s) - mathematics , cayley graph , combinatorics , vertex (graph theory) , transitive relation , graph product , indifference graph , wreath product , chordal graph , vertex transitive graph , modular decomposition , discrete mathematics , permutation graph , 1 planar graph , pathwidth , graph , product (mathematics) , line graph , voltage graph , geometry
A construction is given of an infinite family of finite self‐complementary, vertex‐transitive graphs which are not Cayley graphs. To the authors' knowledge, these are the first known examples of such graphs. The nature of the construction was suggested by a general study of the structure of self‐complementary, vertex‐transitive graphs. It involves the product action of a wreath product of permutation groups. 2000 Mathematics Subject Classification 05C25.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom