The maximum degree and diameter-bounded subgraph in the mesh

DOI10.1016/J.DAM.2012.03.035MaRDI QIDQ444444zbMATH OpenOpenAlexFDO

Authors Mirka Miller, Hebert Pérez-Rosés, Joe Ryan

Publication date 14 August 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.4069

zbMATH Keywords

degreeDelannoy numbersdiameter problemmeshnetwork designparallel architectures

Mathematics Subject Classification ID

Vertex degrees (05C07) Distance in graphs (05C12) Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Network design and communication in computer systems (68M10)

Abstract: The problem of finding the largest connected subgraph of a given undirected host graph, subject to constraints on the maximum degree $Delta$ and the diameter $D$, was introduced in cite{maxddbs}, 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,Delta=4$ and $k=2,Delta=3$, we give constructions that result in sharper lower bounds.

Recommendations

• The maximum degree \& diameter-bounded subgraph and its applications
• MaxDDBS problem on butterfly networks
• Optimal graphs in the enhanced mesh networks
• Degree diameter problem on triangular networks
• Degree diameter problem on silicate network

Cites work

• Generalized Schröder numbers and the rotation principle
• scientific article; zbMATH DE number 3731331 (Why is no real title available?)
• scientific article; zbMATH DE number 139790 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 729910 (Why is no real title available?)
• scientific article; zbMATH DE number 1919533 (Why is no real title available?)
• scientific article; zbMATH DE number 872231 (Why is no real title available?)
• Lipschitz class, narrow class, and counting lattice points
• Moore graphs and beyond: a survey of the degree/diameter problem
• The Degree-Diameter Problem for Several Varieties of Cayley Graphs I: The Abelian Case
• The maximum degree \& diameter-bounded subgraph and its applications
• The NP-completeness column: An ongoing guide
• Variation of the number of lattice points in large balls

Cited in

(9)

• Greedy routing in circulant networks
• New Moore-like bounds and some optimal families of abelian Cayley mixed graphs
• The maximum degree \& diameter-bounded subgraph and its applications
• The degree/diameter problem for mixed abelian Cayley graphs
• Searching for large multi-loop networks
• MaxDDBS problem on butterfly networks
• Degree diameter problem on honeycomb networks
• A Moore-like bound for mixed abelian Cayley graphs
• Optimal graphs in the enhanced mesh networks

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: The maximum degree and diameter-bounded subgraph in the mesh

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