Homogeneous embeddings of cycles in graphs

Wayne Goddard; Michael A. Henning; Hiren Maharaj

doi:10.1007/s003730050050

Homogeneous embeddings of cycles in graphs

Wayne Goddard, Michael A. Henning, Hiren Maharaj

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

3 Citations (Scopus)

Abstract

If G and H are vertex-transitive graphs, then the framing number fr(G, H) of G and H is defined as the minimum order of a graph every vertex of which belongs to an induced G and an induced H. This paper investigates fr(C_m, C_n) for m < n. We show first that fr(C_m, C_n) ≥ n + 2 and determine when equality occurs. Thereafter we establish general lower and upper bounds which show that fr(C_m, C_n) is approximately the minimum of n - m + 2√n and n + n/m.

Original language	English
Pages (from-to)	159-173
Number of pages	15
Journal	Graphs and Combinatorics
Volume	15
Issue number	2
DOIs	https://doi.org/10.1007/s003730050050
Publication status	Published - 1999
Externally published	Yes

Keywords

Cycle
Framing number
Graph
Homogeneous embedding

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/s003730050050

Cite this

@article{e2cc4be3b5a24651b760c103da757037,

title = "Homogeneous embeddings of cycles in graphs",

abstract = "If G and H are vertex-transitive graphs, then the framing number fr(G, H) of G and H is defined as the minimum order of a graph every vertex of which belongs to an induced G and an induced H. This paper investigates fr(Cm, Cn) for m < n. We show first that fr(Cm, Cn) ≥ n + 2 and determine when equality occurs. Thereafter we establish general lower and upper bounds which show that fr(Cm, Cn) is approximately the minimum of n - m + 2√n and n + n/m.",

keywords = "Cycle, Framing number, Graph, Homogeneous embedding",

author = "Wayne Goddard and Henning, \{Michael A.\} and Hiren Maharaj",

year = "1999",

doi = "10.1007/s003730050050",

language = "English",

volume = "15",

pages = "159--173",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "2",

}

TY - JOUR

T1 - Homogeneous embeddings of cycles in graphs

AU - Goddard, Wayne

AU - Henning, Michael A.

AU - Maharaj, Hiren

PY - 1999

Y1 - 1999

N2 - If G and H are vertex-transitive graphs, then the framing number fr(G, H) of G and H is defined as the minimum order of a graph every vertex of which belongs to an induced G and an induced H. This paper investigates fr(Cm, Cn) for m < n. We show first that fr(Cm, Cn) ≥ n + 2 and determine when equality occurs. Thereafter we establish general lower and upper bounds which show that fr(Cm, Cn) is approximately the minimum of n - m + 2√n and n + n/m.

AB - If G and H are vertex-transitive graphs, then the framing number fr(G, H) of G and H is defined as the minimum order of a graph every vertex of which belongs to an induced G and an induced H. This paper investigates fr(Cm, Cn) for m < n. We show first that fr(Cm, Cn) ≥ n + 2 and determine when equality occurs. Thereafter we establish general lower and upper bounds which show that fr(Cm, Cn) is approximately the minimum of n - m + 2√n and n + n/m.

KW - Cycle

KW - Framing number

KW - Graph

KW - Homogeneous embedding

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

U2 - 10.1007/s003730050050

DO - 10.1007/s003730050050

M3 - Article

AN - SCOPUS:0346722952

SN - 0911-0119

VL - 15

SP - 159

EP - 173

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 2

ER -

Homogeneous embeddings of cycles in graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this