On 2-detour subgraphs of the hypercube

József Balogh; Alexandr Kostochka

doi:10.1007/s00373-008-0790-z

On 2-detour subgraphs of the hypercube

József Balogh, Alexandr Kostochka

Mathematics

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

Abstract

A spanning subgraph H of a graph G is a 2-detour subgraph of G if for each x, y ∈ V(G), d_H(x. y) ≤ d_G(x, y) + 2. We prove a conjecture of Erdos, Hamburger, Pippert, and Weakley by showing that for some positive constant c and every n, each 2-detour subgraph of the n-dimensional hypercube Q_n has at least c log2 n · 2ⁿ edges.

Original language	English (US)
Pages (from-to)	265-272
Number of pages	8
Journal	Graphs and Combinatorics
Volume	24
Issue number	4
DOIs	https://doi.org/10.1007/s00373-008-0790-z
State	Published - Sep 2008

Keywords

Additive spanner
Detour subgraph
Extremal subgraph
Graph
Hypercube

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Online availability

10.1007/s00373-008-0790-z

Library availability

Discover UIUC Full Text

Cite this

@article{0b4352282d17466f97191c9976101202,

title = "On 2-detour subgraphs of the hypercube",

abstract = "A spanning subgraph H of a graph G is a 2-detour subgraph of G if for each x, y ∈ V(G), dH(x. y) ≤ dG(x, y) + 2. We prove a conjecture of Erdos, Hamburger, Pippert, and Weakley by showing that for some positive constant c and every n, each 2-detour subgraph of the n-dimensional hypercube Qn has at least c log2 n · 2n edges.",

keywords = "Additive spanner, Detour subgraph, Extremal subgraph, Graph, Hypercube",

author = "J{\'o}zsef Balogh and Alexandr Kostochka",

note = "Funding Information: Alexandr Kostochka: Research supported in part by NSF grants DMS-0400498 and DMS-0650784, and grant 06-01-00694 of the Russian Foundation for Basic Research. Funding Information: J{\'o}zsef Balogh: Research supported in part by NSF grants DMS-0302804, DMS-0603769 and DMS-0600303, UIUC Campus Reseach Board #06139 and #07048, and OTKA 049398. ",

year = "2008",

month = sep,

doi = "10.1007/s00373-008-0790-z",

language = "English (US)",

volume = "24",

pages = "265--272",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "4",

}

TY - JOUR

T1 - On 2-detour subgraphs of the hypercube

AU - Balogh, József

AU - Kostochka, Alexandr

N1 - Funding Information: Alexandr Kostochka: Research supported in part by NSF grants DMS-0400498 and DMS-0650784, and grant 06-01-00694 of the Russian Foundation for Basic Research. Funding Information: József Balogh: Research supported in part by NSF grants DMS-0302804, DMS-0603769 and DMS-0600303, UIUC Campus Reseach Board #06139 and #07048, and OTKA 049398.

PY - 2008/9

Y1 - 2008/9

N2 - A spanning subgraph H of a graph G is a 2-detour subgraph of G if for each x, y ∈ V(G), dH(x. y) ≤ dG(x, y) + 2. We prove a conjecture of Erdos, Hamburger, Pippert, and Weakley by showing that for some positive constant c and every n, each 2-detour subgraph of the n-dimensional hypercube Qn has at least c log2 n · 2n edges.

AB - A spanning subgraph H of a graph G is a 2-detour subgraph of G if for each x, y ∈ V(G), dH(x. y) ≤ dG(x, y) + 2. We prove a conjecture of Erdos, Hamburger, Pippert, and Weakley by showing that for some positive constant c and every n, each 2-detour subgraph of the n-dimensional hypercube Qn has at least c log2 n · 2n edges.

KW - Additive spanner

KW - Detour subgraph

KW - Extremal subgraph

KW - Graph

KW - Hypercube

UR - http://www.scopus.com/inward/record.url?scp=51849120288&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=51849120288&partnerID=8YFLogxK

U2 - 10.1007/s00373-008-0790-z

DO - 10.1007/s00373-008-0790-z

M3 - Article

AN - SCOPUS:51849120288

SN - 0911-0119

VL - 24

SP - 265

EP - 272

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 4

ER -

On 2-detour subgraphs of the hypercube

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this