Embedding graphs in Cayley graphs

Chris D. Godsil; Wilfried Imrich

doi:10.1007/BF01788527

Embedding graphs in Cayley graphs

Chris D. Godsil
, Wilfried Imrich

Chair of Applied Mathematics (170)

Simon Fraser University

Research output: Contribution to journal › Article › Research › peer-review

2 Citations (Scopus)

Abstract

If Y is a finite graph then it is known that every sufficiently large group G has a Cayley graph containing an induced subgraph isomorphic to Y. This raises the question as to what is "sufficiently large". Babai and Sós have used a probabilistic argument to show that |G| > 9.5 |Y|3 suffices. Using a form of greedy algorithm we strengthen this to {Mathematical expression}. Some related results on finite and infinite groups are included.

Original language	English
Pages (from-to)	39-43
Number of pages	5
Journal	Graphs and combinatorics
Volume	3.1987
Issue number	1
DOIs	https://doi.org/10.1007/BF01788527
Publication status	Published - Dec 1987

Access to Document

10.1007/BF01788527

Cite this

@article{0da05c5c19794e7d959bf28d25e3a987,

title = "Embedding graphs in Cayley graphs",

abstract = "If Y is a finite graph then it is known that every sufficiently large group G has a Cayley graph containing an induced subgraph isomorphic to Y. This raises the question as to what is {"}sufficiently large{"}. Babai and S{\'o}s have used a probabilistic argument to show that |G| > 9.5 |Y|3 suffices. Using a form of greedy algorithm we strengthen this to \{Mathematical expression\}. Some related results on finite and infinite groups are included.",

author = "Godsil, \{Chris D.\} and Wilfried Imrich",

year = "1987",

month = dec,

doi = "10.1007/BF01788527",

language = "English",

volume = "3.1987",

pages = "39--43",

journal = "Graphs and combinatorics ",

issn = "0911-0119",

publisher = "Springer Japan",

number = "1",

}

TY - JOUR

T1 - Embedding graphs in Cayley graphs

AU - Godsil, Chris D.

AU - Imrich, Wilfried

PY - 1987/12

Y1 - 1987/12

N2 - If Y is a finite graph then it is known that every sufficiently large group G has a Cayley graph containing an induced subgraph isomorphic to Y. This raises the question as to what is "sufficiently large". Babai and Sós have used a probabilistic argument to show that |G| > 9.5 |Y|3 suffices. Using a form of greedy algorithm we strengthen this to {Mathematical expression}. Some related results on finite and infinite groups are included.

AB - If Y is a finite graph then it is known that every sufficiently large group G has a Cayley graph containing an induced subgraph isomorphic to Y. This raises the question as to what is "sufficiently large". Babai and Sós have used a probabilistic argument to show that |G| > 9.5 |Y|3 suffices. Using a form of greedy algorithm we strengthen this to {Mathematical expression}. Some related results on finite and infinite groups are included.

UR - https://www.scopus.com/pages/publications/0011563739

U2 - 10.1007/BF01788527

DO - 10.1007/BF01788527

M3 - Article

AN - SCOPUS:0011563739

SN - 0911-0119

VL - 3.1987

SP - 39

EP - 43

JO - Graphs and combinatorics

JF - Graphs and combinatorics

IS - 1

ER -

Embedding graphs in Cayley graphs

Abstract

Access to Document

Other files and links

Cite this