Change search
ReferencesLink to record
Permanent link

Direct link
Bipartite multigraphs with expander-like properties
KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.
2007 (English)In: Discrete Applied Mathematics, ISSN 0166-218X, Vol. 155, no 13, 1667-1677 p.Article in journal (Refereed) Published
Abstract [en]

This note considers the following 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)(vertical bar U vertical bar)?" Graphs with the above property seem to behave well also with respect to other, more complicated, expander-like properties. We provide results for d in (5,6,7,81 and give a description of a fairly general methodology for devising computer-assisted proofs for a wide class of mathematical claims using interval arithmetic.

Place, publisher, year, edition, pages
2007. Vol. 155, no 13, 1667-1677 p.
Keyword [en]
expander graphs, probabilistic method, interval arithmetic
National Category
Computer Science
URN: urn:nbn:se:kth:diva-37006DOI: 10.1016/j.dam.2007.03.001ISI: 000249236300002ScopusID: 2-s2.0-34547480916OAI: diva2:431814
Available from: 2011-07-26 Created: 2011-07-25 Last updated: 2011-07-26Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Engebretsen, Lars
By organisation
Numerical Analysis and Computer Science, NADA
In the same journal
Discrete Applied Mathematics
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 19 hits
ReferencesLink to record
Permanent link

Direct link