The maximum degree and diameter-bounded subgraph in the mesh

DOI10.1016/J.DAM.2012.03.035zbMATH Open1245.05023arXiv1203.4069OpenAlexW1997904473MaRDI QIDQ444444FDOQ444444

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)

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.

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

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

zbMATH Keywords

network designdegreeDelannoy numbersparallel architecturesmeshdiameter problem

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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 NP-completeness column: An ongoing guide
• The maximum degree \& diameter-bounded subgraph and its applications
• Lipschitz class, narrow class, and counting lattice points
• Variation of the number of lattice points in large balls
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Generalized Schröder numbers and the rotation principle

Cited In (7)

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

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)