A Tur'an-type problem for circular arc graphs
| Autor: | Carlson, Rosalie, Flood, Stephen, O'Neill, Kevin, Su, Francis Edward |
|---|---|
| Rok vydání: | 2011 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | A circular arc graph is the intersection graph of a collection of connected arcs on the circle. We solve a Tur'an-type problem for circular arc graphs: for n arcs, if m and M are the minimum and maximum number of arcs that contain a common point, what is the maximum number of edges the circular arc graph can contain? We establish a sharp bound and produce a maximal construction. For a fixed m, this can be used to show that if the circular arc graph has enough edges, there must be a point that is covered by at least M arcs. In the case m=0, we recover results for interval graphs established by Abbott and Katchalski (1979). We suggest applications to voting situations with interval or circular political spectra. Comment: 18 pages, 8 figures, related papers at http://www.math.hmc.edu/~su/papers.html |
| Databáze: | arXiv |
| Externí odkaz: |
|