On 2-Detour Subgraphs of the Hypercube |
| |
Authors: | József Balogh Alexandr Kostochka |
| |
Affiliation: | (1) University of Illinois at Urbana-Champaign, Urbana-Champaign, IL 61801, USA;(2) Institute of Mathematics, Novosibirsk, 630090, Russia |
| |
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 Erdős, 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 clog2 n · 2 n edges. 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. 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. |
| |
Keywords: | Graph Extremal subgraph Hypercube Detour subgraph Additive spanner |
本文献已被 SpringerLink 等数据库收录! |
|