Embedding graphs in Cayley graphs

DOI10.1007/BF01788527MaRDI QIDQ1820168zbMATH OpenOpenAlexFDO

Authors Wilfried Imrich, Chris Godsil

Publication date 1987

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01788527

zbMATH Keywords

Cayley graphinduced subgraph

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Review text

Over ten years ago Babai showed that for any graph Y and for any sufficiently large group G, there is a Cayley graph X of G such that Y is an induced subgraph of X. The bounds given by him for \(| G|\) have been recently reduced by Babai and Sós to approximately \(9.5| Y|^ 3\). Using different methods the present paper reduces the bound to roughly \(3.7| Y|^ 3\). Better bounds are given for odd order groups and Abelian groups. It is noted that while there exist examples which show \(| G|\) must be \(O(n^ 2)\), no such examples exist which require \(| G|\) to be \(O(n^ 3)\).

Recommendations

• scientific article; zbMATH DE number 475367
• Cylindric embeddings of Cayley graphs.
• Large Cayley graphs on an abelian group
• Sidon sets in groups and induced subgraphs of Cayley graphs
• Characterising planar Cayley graphs and Cayley complexes in terms of group presentations

Cites work

• Sidon sets in groups and induced subgraphs of Cayley graphs

Cited in

(9)

• Sidon sets in groups and induced subgraphs of Cayley graphs
• Cylindric embeddings of Cayley graphs.
• Generalized Brownian loops
• Imbeddings of metacyclic cayley graphs
• scientific article; zbMATH DE number 475367 (Why is no real title available?)
• Relative Cayley graphs of finite groups
• Uniform emulations of Cartesian-product and Cayley graphs
• Coloring minimal Cayley graphs
• What is and is not inside a Cayley graph?

This page was built for publication: Embedding graphs in Cayley graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1820168)