loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02)
Explicit Unique-Neighbor Expanders
Vancouver, BC, Canada
November 16-November 19
ISBN: 0-7695-1822-2
Noga Alon, Institute for Advanced Study and Tel Aviv University
Michael Capalbo, Institute for Advanced Study
We present a simple, explicit construction of an infinite family F of bounded-degree ?unique-neighbor? expanders \Gamma; i.e., there are strictly positive constants \alpha and, such that all \Gamma = (X,E(\Gamma)) \varepsilon F satisfy the following property. For each subset S of X with no more than \alpha|X| vertices, there are at least \varepsilon|S| vertices in X \S that are adjacent in \Gamma to exactly one verte in S. The construction of F is simple to specify, and each \Gamma \varepsilon F is 6-regular. We then extend the technique and present easy to describe explicit infinite families of 4-regular and 3-regular unique-neighbor expanders, as well as explicit families of bipartite graphs with non equal color classes and similar properties.This has several applications and settles an open problem considered by various researchers.
Citation:
Noga Alon, Michael Capalbo, "Explicit Unique-Neighbor Expanders," focs, pp.73, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002
Usage of this product signifies your acceptance of the Terms of Use.