Loading...
Please wait, while we are loading the content...
Similar Documents
Explicit unique-neighbor expanders (extended abstract).
| Content Provider | CiteSeerX |
|---|---|
| Author | Alon, Noga |
| Abstract | We present a simple, explicit construction of an infinite family F of bounded-degree ’unique-neighbor’ expanders Γ; i.e., there are strictly positive constants α and ɛ, such that all Γ = (X, E(Γ)) ∈ F satisfy the following property. For each subset S of X with no more than α X vertices, there are at least ɛ S vertices in X \ S that are adjacent in Γ to exactly one vertex in S. The construction of F is simple to specify, and each Γ ∈ 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. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Several Application Infinite Family Explicit Family Open Problem Positive Constant Explicit Construction Explicit Infinite Family Similar Property Explicit Unique-neighbor Expanders Non Equal Color Class Following Property Bounded-degree Unique-neighbor Expanders Bipartite Graph 3-regular Unique-neighbor Expanders Various Researcher |
| Content Type | Text |
