We study the existence of expander graphs with a focus on odd and unique expanders. The main goal is to describe configurations of arguments for which there is no infinite family of expanders. The most imporant result is that for every graph there is a nonempty subset of at most half of its vertices, such that every other vertex is connected at least twice to the subset or not connected to the subset at all. It follows that certain classes of unique expanders cannot exist. On the other hand we present some configurations for which there are families of expanders. Powered by TCPDF (www.tcpdf.org)
| Identifer | oai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:347525 |
| Date | January 2016 |
| Creators | Hlásek, Filip |
| Contributors | Koucký, Michal, Šámal, Robert |
| Source Sets | Czech ETDs |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/masterThesis |
| Rights | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.0021 seconds