Mathematics – Combinatorics
Scientific paper
2004-12-06
Mathematics
Combinatorics
13 pages, 1 Postscript figure generated with MetaPost
Scientific paper
A graph with vertex set V and edge set E is called a (d,c)-expander if the maximum degree of a vertex is d and, for every subset W of V that has cardinality at most |V|/2, the number of edges between vertices in W and vertices outside of W is at least c|V|. This note considers a related combinatorial question: "For which integers d and functions f_d does there exist, for every large enough v, a bipartite d-regular multigraph on 2v nodes with node sets V and W having the following property: For every U that is a subset of either V or W, the cardinality of the set of neighbours of U is at least f_d(|U|)?" Graphs with the above property seem to behave well also with respect to other, more complicated, expansion-type properties. We provide results for d in {5,6,7,8} and give a description of a fairly general methodology for devising computer-assisted proofs for a wide class of mathematical claims using so called interval arithmetic.
No associations
LandOfFree
Bipartite Multigraphs with Expander-Like Properties does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Bipartite Multigraphs with Expander-Like Properties, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bipartite Multigraphs with Expander-Like Properties will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-41119