Holes, Antiholes and Maximal Cliques in a Railway Model for a Single Track
Please always quote using this URN: urn:nbn:de:0297-zib-7939
- We present a graph theoretical model for scheduling trains on a single unidirectional track between two stations. The set of departures of all possible train types at all possible (discrete) points of time is turned into an undirected graph $\Gneu$ by joining two nodes if the corresponding departures are in conflict. This graph $\Gneu$ has no odd antiholes and no $k$-holes for any integer $k\geq 5$. In particular, any finite, node induced subgraph of $\Gneu$ is perfect. For any integer $r\geq 2$ we construct minimal headways for $r$ train types so that the resulting graph $\Gneu$ has $2r$-antiholes and $4$-holes at the same time. Hence, $\Gneu$ is neither a chordal graph nor the complement of a chordal graph, in general. At the end we analyse the maximal cliques in $G$.
Download full text files
Additional Services
| Author: | Sascha Lukac |
|---|---|
| Document Type: | ZIB-Report |
| Tag: | anti holes; cliques; holes; perfect graphs; railway |
| MSC-Classification: | 05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C17 Perfect graphs |
| Date of first Publication: | 2004/05/28 |
| Series (Serial Number): | ZIB-Report (04-18) |
| ZIB-Reportnumber: | 04-18 |
