Miscellaneous
From G-designs
Relevant articles: [1], [2], [3], [4], [5], [6].
Miscellaneous
There are a few other graphs and families of graphs for which the
spectrum problem has been considered but which are not covered in other
sections. This page summarises the known results for the spectrum
problem for the Petersen graph, the Heawood graph, dragons and .
The Petersen graph and the Heawood graph are shown in Figure 1.
The spectrum problem for the graph obtained from a complete graph on vertices by removing the edges of a complete subgraph on vertices, denoted by has also been considered.
Spectrum Results
Theorem 1 [2]
Let denote the Petersen graph. There exists a -design of order if and only if and .
Theorem 2 [3]
Let denote the Heawood graph. There exists an -design of order if and only if and .
Theorem 3 [6]
For each , a -design of order exists if . Moreover, this condition is also necessary when is a power of .
Theorem 4 [1]
There exists a -design of order for all when is even, and for all when is odd, except that there is no -design of order when is even.
References
- ↑ 1.0 1.1 Adams, P., Billington, E. J., and Hoffman, D. G. On the spectrum for K_m+2\sbs K_m designs, J. Combin. Des. 5, 49–60 (1997).
- ↑ 2.0 2.1 Adams, P. and Bryant, D. E. The spectrum problem for the Petersen graph, J. Graph Theory, 22, 175–180 (1996).
- ↑ 3.0 3.1 Adams, P. and Bryant, D. E. The spectrum problem for the Heawood graph, Bull. Inst. Combin. Appl. 19, 17–22 (1997).
- ↑ Adams, P., Bryant, D., and Buchanan, M. A survey on the existence of G-designs, J. Combin. Des. 16, 373–410 (2008).
- ↑ Hanson, D. A quick proof that K_10\not= P+P+P, Discrete Math. 101, 107–108 (1992).
- ↑ 6.0 6.1 Huang, C. and Schönheim, J. Decomposition of K_n into dragons, Canad. Math. Bull. 23, 275–279 (1980).