# Graphs with five vertices

### From G-designs

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

## Contents[hide] |

# Graphs with five vertices

There are 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:-

-designs of orders , , and were constructed in _{[12]}.

-designs of orders , and were constructed in _{[18]}.

The last remaining open cases for -designs, -designs, and -designs have now all been settled, _{[13]}.

**Table 1**

Graph | Spectrum | Possible exceptions |

## Notes

- Note that is a path, is a caterpillar, is a star, is a cycle and is a complete graph.

- In
_{[2]}it is claimed that the spectrum problem for -designs where in the case where 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 , , and 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 and . Thus, the results in_{[11]}settle the case only for and , and the case remains open for and . 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 , except that the existence of a -design of order is left unresolved for . Heinrich's survey_{[9]}omits the case from the list of unresolved cases. In 2004, Li and Chang_{[14]}constructed -designs of order for , and based on the list in_{[9]}claimed to have finished the problem. A -design of order 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 -designs of order for all is implied by the existence of -designs of order for various values of , but the actual proven result requires -designs of order . This (unproven) result is incorporated in_{[9]}and then used in_{[5]}to (incorrectly) establish the existence of -designs of order for all .

- The existence of a -design of order for all 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 is in_{[8]}.

## References

- ↑
^{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.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). - ↑ Blinco, A.
*Decompositions of complete graphs into theta graphs with fewer than ten edges*, Util. Math.**64**, 197–212 (2003). - ↑ 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.0}^{5.1}Chang, Y.*The spectra for two classes of graph designs*, Ars Combin.**65**, 237–243 (2002). - ↑ 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). - ↑ 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.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.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). - ↑ Huang, C.
*Balanced graph designs on small graphs*, Utilitas Math.**10**, 77–108 (1976). - ↑
^{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.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.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.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.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.0}^{16.1}Rodger, C. A.*Graph decompositions*, Matematiche (Catania),**45**, 119–139 (1991) (1990). - ↑
^{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.0}^{18.1}H. Wei, H. S. and Ge, G.*Traffic grooming in unidirectional WDM rings with grooming ratio 9*, Preprint,