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,