2012/03/19 by Mirka Miller, Hebert Pérez‐Rosés, Miller, Mirka +4
Computer Science · Mathematics · #05C35 (Primary) 05C12 #05C90 #68R10 #95C15 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems #cs.DM #math.CO #msc:05C12 #msc:05C35 #msc:05C90 #msc:68R10 #msc:95C15
paper · pdf · doi:10.48550/arxiv.1203.4069
accepted, 18 pages, 7 figures; Discrete Applied Mathematics, 2012
arxiv created 2012/03/19 · openalex publication_date 2012/03/19 · arxiv updated 2012/03/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The problem of finding the largest connected subgraph of a given undirected host graph, subject to constraints on the maximum degree Δ and the diameter D, was introduced in \citemaxddbs, as a generalization of the Degree-Diameter Problem. A case of special interest is when the host graph is a common parallel architecture. Here we discuss the case when the host graph is a k-dimensional mesh. We provide some general bounds for the order of the largest subgraph in arbitrary dimension k, and for the particular cases of k=3, Δ= 4 and k=2, Δ= 3, we give constructions that result in sharper lower bounds.