# Graphs with five vertices

Relevant articles: [1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18].

[hide]

# Graphs with five vertices

There are $23$ non-isomorphic graphs with five vertices, excluding those with isolated vertices, and these are shown in Figure 1.

## Spectrum Results

Table 1 summarises the known results on the spectrum problem for graphs with five vertices. An explanation of the sources of these results is given in [1].

In addition to the results described in [1], the following results have been obtained:-

$G_{22}$-designs of orders $27$, $135$, $162$ and $216$ were constructed in [12].

$G_{22}$-designs of orders $36$, $144$ and $234$ were constructed in [18].

The last remaining open cases for $G_{20}$-designs, $G_{21}$-designs, and $G_{22}$-designs have now all been settled, [13].

Table 1

 Graph Spectrum Possible exceptions $G_1$ $n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }3){\rm \ and \ }n\not\in\{3,4\}$ $\emptyset$ $G_2$ $n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }8)$ $\emptyset$ $G_3$ $n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }8)$ $\emptyset$ $G_4$ $n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }8)$ $\emptyset$ $G_5$ $n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }8)$ $\emptyset$ $G_6$ $n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }5)$ $\emptyset$ $G_7$ $n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }5){\rm \ and \ }n\neq 5$ $\emptyset$ $G_8$ $n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }5){\rm \ and \ }n\neq 5$ $\emptyset$ $G_9$ $n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }5){\rm \ and \ }n\not\in\{5,6\}$ $\emptyset$ $G_{10}$ $n \equiv 1 {\rm \ or \ } 5 \,({\rm mod \ }10)$ $\emptyset$ $G_{11}$ $n \equiv 0,1,4 {\rm \ or \ } 9 \,({\rm mod \ }12){\rm \ and \ }n\neq 4$ $\emptyset$ $G_{12}$ $n \equiv 0,1,4 {\rm \ or \ } 9 \,({\rm mod \ }12){\rm \ and \ }n\neq 4$ $\emptyset$ $G_{13}$ $n \equiv 0,1,4 {\rm \ or \ } 9 \,({\rm mod \ }12){\rm \ and \ }n\neq 4$ $\emptyset$ $G_{14}$ $n \equiv 0,1,4 {\rm \ or \ } 9 \,({\rm mod \ }12){\rm \ and \ }n\not\in\{4,9,12\}$ $\emptyset$ $G_{15}$ $n \equiv 1 {\rm \ or \ } 9 \,({\rm mod \ }12)$ $\emptyset$ $G_{16}$ $n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }7){\rm \ and \ }n\not\in\{7,8\}$ $\emptyset$ $G_{17}$ $n \equiv 1 {\rm \ or \ } 7 \,({\rm mod \ }14)$ $\emptyset$ $G_{18}$ $n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }7){\rm \ and \ }n\not\in\{8,14\}$ $\emptyset$ $G_{19}$ $n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }7){\rm \ and \ }n\neq 8$ $\emptyset$ $G_{20}$ $n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }16)$ $\emptyset$ $G_{21}$ $n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }16){\rm \ and \ }n\neq 16$ $\emptyset$ $G_{22}$ $n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }9){\rm \ and \ }n\not\in\{9,10,18\}$ $\emptyset$ $G_{23}$ $n \equiv 1 {\rm \ or \ } 5 \,({\rm mod \ }20)$ $\emptyset$

## Notes

• Note that $G_3\cong P_5$ is a path, $G_4$ is a caterpillar, $G_5\cong K_{1,4}$ is a star, $G_{10}\cong C_5$ is a cycle and $G_{23}\cong K_5$ is a complete graph.
• In [2] it is claimed that the spectrum problem for $G_i$-designs where $i\in\{6,7,8,9\}$ in the case where $n\equiv 0\,({\rm mod \ }10)$ is settled in [17]; however, it seems likely that this is a typographical error. A likely intended reference is [11], as it is stated in [2] that $G_6$, $G_7$, $G_8$ and $G_9$ are dragons and these graphs are the topic of [11] (see Theorem 3 in the section on Miscellaneous graphs). However, the definition of dragons excludes the graphs $G_6$ and $G_7$. Thus, the results in [11] settle the case $n\equiv 0\,({\rm mod \ }10)$ only for $G_8$ and $G_9$, and the case $n\equiv 0\,({\rm mod \ }10)$ remains open for $G_6$ and $G_7$. Although Bermond et al [2] describe a method which may be used to settle this case, the details are not all included in their paper; however, the necessary designs are constructed in [1].
• Bermond et al [2] completely settle the spectrum problem for $G_{18}$, except that the existence of a $G_{18}$-design of order $n$ is left unresolved for $n\in\{36,42,56,92,98,120\}$. Heinrich's survey [9] omits the case $n=42$ from the list of unresolved cases. In 2004, Li and Chang [14] constructed $G_{18}$-designs of order $n$ for $n \in \{36,56,92,98,120\}$, and based on the list in [9] claimed to have finished the problem. A $G_{18}$-design of order $42$ is constructed in [1].
• It is worth noting that [16] contains an unfortunate error in the statement of a lemma. The lemma states that the existence of $G_{20}$-designs of order $n$ for all $n\equiv 0\,({\rm mod \ }16)$ is implied by the existence of $G_{20}$-designs of order $8s+1$ for various values of $s$, but the actual proven result requires $G_{20}$-designs of order $8s$. This (unproven) result is incorporated in [9] and then used in [5] to (incorrectly) establish the existence of $G_{20}$-designs of order $n$ for all $n\equiv 0\,({\rm mod \ }16)$.
• The existence of a $G_{22}$-design of order $n$ for all $n\equiv 1\,({\rm mod \ }18)$ except for twelve unresolved cases is stated in [9]. Although this result is now known to be true, a proof is not given in any of the references cited in [9]. In [15], these twelve (previously) unresolved cases are settled, but it seems the first published complete solution of the case $n\equiv1\,({\rm mod \ }18)$ is in [8].

## References

1. 1.0 1.1 1.2 1.3 1.4 Adams, P., Bryant, D., and Buchanan, M. A survey on the existence of G-designs, J. Combin. Des. 16, 373–410 (2008).
2. 2.0 2.1 2.2 2.3 2.4 Bermond, J. -C., Huang, C., Rosa, A., and Sotteau, D. Decomposition of complete graphs into isomorphic subgraphs with five vertices, Ars Combin. 10, 211–254 (1980).
3. Blinco, A. Decompositions of complete graphs into theta graphs with fewer than ten edges, Util. Math. 64, 197–212 (2003).
4. Bryant, D. and El-Zanati, S. Graph decompositions, CRC Press Series on Discrete Mathematics and its Applications, The CRC handbook of combinatorial designs, ed. 2, CRC Press, 477–486 (2007).
5. 5.0 5.1 Chang, Y. The spectra for two classes of graph designs, Ars Combin. 65, 237–243 (2002).
6. Colbourn, C. J., Ge, G., and Ling, A. C. H. Graph designs for the eight-edge five-vertex graphs, Discrete Math. 309, 6440–6445 (2009).
7. Colbourn, C. J. and Wan, P. Minimizing drop cost for SONET/WDM networks with 1 \over 8 wavelength requirements, Networks, 37, 107–116 (2001).
8. 8.0 8.1 Ge, G. and Ling, A. C. H. On the existence of (K_5\sbs e)-designs with application to optical networks, SIAM J. Discrete Math. 21, 851–864 (2007).
9. 9.0 9.1 9.2 9.3 9.4 9.5 Heinrich, K. Graph decompositions, CRC Press Series on Discrete Mathematics and its Applications, The CRC handbook of combinatorial designs, ed. 1, CRC Press, 361–366 (1996).
10. Huang, C. Balanced graph designs on small graphs, Utilitas Math. 10, 77–108 (1976).
11. 11.0 11.1 11.2 11.3 Huang, C. and Schönheim, J. Decomposition of K_n into dragons, Canad. Math. Bull. 23, 275–279 (1980).
12. 12.0 12.1 Kolotoglu, E. The Existence and Construction of (K_5\setminus e)-Designs of Orders 27, 135, 162, and 216, J. Combin. Des. (to appear),
13. 13.0 13.1 G. Ge S. Hu, K. E. and Wei, H. A complete solution to spectrum problem for five-vertex graphs with application to traffic grooming in optical networks, J. Combin. Des. 23, 233 (2015).
14. 14.0 14.1 Li, Q. and Chang, Y. Decomposition of lambda-fold complete graphs into a certain five-vertex graph, Australas. J. Combin. 30, 175–182 (2004).
15. 15.0 15.1 Li, Q. and Chang, Y. A few more (K_v,K_5\sbs e)-designs, Bull. Inst. Combin. Appl. 45, 11–16 (2005).
16. 16.0 16.1 Rodger, C. A. Graph decompositions, Matematiche (Catania), 45, 119–139 (1991) (1990).
17. 17.0 17.1 Rosa, A. and Huang, C. Another class of balanced graph designs: balanced circuit designs, Discrete Math. 12, 269–293 (1975).
18. 18.0 18.1 H. Wei, H. S. and Ge, G. Traffic grooming in unidirectional WDM rings with grooming ratio 9, Preprint,