Long geodesics in subgraphs of the cube

Imre Leader; Eoin Long

doi:10.1016/j.disc.2014.02.013

Long geodesics in subgraphs of the cube

Imre Leader, Eoin Long

Mathematics

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

4 Citations (Scopus)

97 Downloads (Pure)

Abstract

We show that any subgraph of the hypercube Q_n of average degree d contains a geodesic of length d, where by geodesic we mean a shortest path in Q_n. This result, which is best possible, strengthens a theorem of Feder and Subi. It is also related to the ‘antipodal colourings’ conjecture of Norine.

Original language	English
Pages (from-to)	29-33
Number of pages	5
Journal	Discrete Mathematics
Volume	326
Early online date	18 Mar 2014
DOIs	https://doi.org/10.1016/j.disc.2014.02.013
Publication status	Published - 6 Jul 2014

Keywords

Geodesic
hypercube
antipodal colouring

Access to Document

10.1016/j.disc.2014.02.013Licence: Other (please provide link to licence statement

LeaderI2014LongFinal published version, 366 KBLicence: Other (please provide link to licence statement

https://doi.org/10.1016/j.disc.2014.02.013Licence: Other (please provide link to licence statement

Cite this

@article{7bcfbe85e0dd4cfbb4512268ead250fd,

title = "Long geodesics in subgraphs of the cube",

abstract = "We show that any subgraph of the hypercube Qn of average degree d contains a geodesic of length d, where by geodesic we mean a shortest path in Qn. This result, which is best possible, strengthens a theorem of Feder and Subi. It is also related to the {\textquoteleft}antipodal colourings{\textquoteright} conjecture of Norine.",

keywords = "Geodesic, hypercube, antipodal colouring",

author = "Imre Leader and Eoin Long",

year = "2014",

month = jul,

day = "6",

doi = "10.1016/j.disc.2014.02.013",

language = "English",

volume = "326",

pages = "29--33",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

}

TY - JOUR

T1 - Long geodesics in subgraphs of the cube

AU - Leader, Imre

AU - Long, Eoin

PY - 2014/7/6

Y1 - 2014/7/6

N2 - We show that any subgraph of the hypercube Qn of average degree d contains a geodesic of length d, where by geodesic we mean a shortest path in Qn. This result, which is best possible, strengthens a theorem of Feder and Subi. It is also related to the ‘antipodal colourings’ conjecture of Norine.

AB - We show that any subgraph of the hypercube Qn of average degree d contains a geodesic of length d, where by geodesic we mean a shortest path in Qn. This result, which is best possible, strengthens a theorem of Feder and Subi. It is also related to the ‘antipodal colourings’ conjecture of Norine.

KW - Geodesic

KW - hypercube

KW - antipodal colouring

U2 - 10.1016/j.disc.2014.02.013

DO - 10.1016/j.disc.2014.02.013

M3 - Article

SN - 0012-365X

VL - 326

SP - 29

EP - 33

JO - Discrete Mathematics

JF - Discrete Mathematics

ER -

Long geodesics in subgraphs of the cube

Abstract

Keywords

Access to Document

Fingerprint

Cite this