Sharper Lower Bounds in the Maximum Degree and Diameter Bounded Subgraph Problem in the Mesh

arXiv1211.7128MaRDI QIDQ6237615FDOQ6237615

Publication date: 29 November 2012

Abstract: The Maximum Degree and Diameter Bounded Subgraph Problem (MaxDDBS) asks: given a host graph G, a bound on maximum degree Delta, and a diameter D, what is the largest subgraph of the host graph with degree bounded by Delta and diameter bounded by D? In this paper, we investigate this problem when the host graph is the k-dimensional mesh. We provide lower bounds for the size of the largest subgraph of the mesh satisfying MaxDDBS for all k and Delta > 3 that agree with the known upper bounds up to the first two terms, and show that for Delta = 3, the lower bounds are at least the same order of growth as the upper bounds.

This page was built for publication: Sharper Lower Bounds in the Maximum Degree and Diameter Bounded Subgraph Problem in the Mesh

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