Extremal subgraphs of the d-dimensional grid graph

MaRDI QIDQ6239914zbMATH OpenFDO

Authors Geir Agnarsson, Kshitij Lauria

Publication date 26 February 2013

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Extremal problems in graph theory (05C35)

Abstract: For each natural number $n$ we determine, both asymptotically and exactly, the maximum number of edges an induced subgraph of order $n$ of the $d$-dimension a grid graph ${ints}^d$ can have. The asymptotic bound is obtained by using a theorem Bollob'{a}s and Thomason, and the exact bound is obtained by induction. This generalizes some earlier results for the case $d=2$ on one hand, and for $nleq{2}^d$ on the other.

This page was built for publication: Extremal subgraphs of the $d$-dimensional grid graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6239914)