
doi: 10.1007/bf01788527
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)\).
induced subgraph, Cayley graph, Graphs and abstract algebra (groups, rings, fields, etc.)
induced subgraph, Cayley graph, Graphs and abstract algebra (groups, rings, fields, etc.)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 4 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
