Graphs with five vertices

From G-designs

Jump to: navigation, search

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 23 non-isomorphic graphs with five vertices, excluding those with isolated vertices, and these are shown in Figure 1.

Figure 1: Graphs with 5 vertices
Graphs with 5 vertices



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

Table 1: The spectrum for graphs with 5 vertices.
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


  • 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,