Graphs with six 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].

Contents

[hide]

Graphs with six vertices


This page summarises the known results on the spectrum problem for graphs with six vertices. The majority of these results are concerned with graphs on six vertices with at most nine edges. However, there are a few other results on graphs on six vertices with more than nine edges.

The first results considered are for all graphs on six vertices with at most eight edges, excluding those with isolated vertices (see Table 1). Next the known results for graphs on six vertices with nine edges, excluding those with isolated vertices, are discussed (see Table 2). Finally the known results for graphs with six vertices and more than nine edges, excluding those with isolated vertices, are described.

There are 70 non-isomorphic graphs on six vertices with at most eight edges, excluding those with isolated vertices, and these are shown in the Figure 1.

Figure 1: Graphs with 6 vertices and up to 8 edges
Graphs with 6 vertices and up to 8 edges

my home page

There are twenty one non-isomorphic graphs with six vertices and nine edges, excluding those with isolated vertices. The spectrum problem has been completely solved for ten of these which are shown in Figure 2.

Figure 2: Ten graphs with 6 vertices and 9 edges.

H^9_1

H^9_2

H^9_3

H^9_4

H^9_5

H^9_6

H^9_7

H^9_8

H^9_9

H^9_{10}




Spectrum Results


Table 1 summarises the known results on the spectrum problem for graphs with 6 vertices and up to 8 edges. An explanation of the sources of most of these results is given in [2], and the remainder are new results as discussed below.

The results from [12] left possible exceptions for the graph H^7_{16} (which are listed as such in [2]). These exceptions have since been dealt with in [14] and they are included in Table 1.

Table 1

Table 1: The spectrum for graphs with 6 vertices and up to 8 edges.
(i,j) Spectrum for H^j_i Possible

exceptions

(1,3) n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }3)

{\rm \ and \ }n\not\in\{3,4\}

\emptyset
(1,4),(2,4),(3,4) n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }8) \emptyset
(1,5),(2,5),(4,5),(8,5),(9,5) n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }5)

{\rm \ and \ }n\neq 5

\emptyset
(3,5),(5,5),(6,5),(7,5) n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }5)

{\rm \ and \ }n\not\in\{5,6\}

\emptyset
(1,6),(2,6),(3,6),(4,6),(5,6),(6,6),(7,6),(9,6),(10,6),(11,6),

(12,6),(13,6),(14,6)

n \equiv 0,1,4 {\rm \ or \ } 9 \,({\rm mod \ }24)

{\rm \ and \ }n\neq 4

\emptyset
(8,6) n \equiv 1 {\rm \ or \ } 9 \,({\rm mod \ }12)

{\rm \ and \ }n\neq 9

\emptyset
(15,6) n \equiv 1 {\rm \ or \ } 9 \,({\rm mod \ }12) \emptyset
(1,7),(2,7),(3,7),(4,7),(5,7),(9,7),(10,7),(13,7),(17,7) n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }7) \emptyset
(6,7),(7,7),(12,7),(15,7),(18,7) n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }7)

{\rm \ and \ }n\neq 7

\emptyset
(8,7) n \equiv 1 {\rm \ or \ } 7 \,({\rm mod \ }14) \emptyset
(11,7),(14,7) n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }7)

{\rm \ and \ }n\neq 8

\emptyset
(16,7),(19,7),(20,7) n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }7)

{\rm \ and \ }n\neq 7,8

\emptyset
(1,8),(2,8),(3,8),(4,8),(5,8),(6,8),(7,8),(8,8),(9,8),(10,8),

(11,8),(16,8),(17,8),(18,8),(19,8),(20,8),(21,8),(22,8)

n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }16) \emptyset
(12,8),(13,8) n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }16) n=32
(14,8),(15,8) n \equiv 1 \,({\rm mod \ }16) \emptyset

There are twenty one non-isomorphic graphs with six vertices and nine edges, excluding those with isolated vertices. The spectrum problem has been solved for the ten of these shown in Figure 2, and the results are summarised in Table 2.

In [10], the spectrum problem is completely solved for H_1^9, H_2^9, \ldots, H_9^9 and the spectrum problem for H^9_{10} is solved in [1]. The spectrum problems for H^9_1 and H^9_2 were solved prior to [10]. The spectrum problem for the graph H^9_1 was first solved by Mullin et al [11] (see the page on even graphs), and the spectrum problem for H^9_2 (the complete bipartite graph K_{3,3}) was first solved by Guy and Beineke [5] (see the page on complete bipartite graphs).

Table 2

Table 2: The spectrum for some graphs with 6 vertices and 9 edges.
(i,j) Spectrum for H^j_i
(1,9) n\equiv 1 {\rm \ or \ } 9 \,({\rm mod \ }18)
(2,9) n\equiv 1 \,({\rm mod \ }9){\rm \ and \ }n\neq 10
(3,9) n\equiv 1 \,({\rm mod \ }9)
(4,9),(5,9),(6,9),(8,9),(9,9),(10,9) n\equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }9){\rm \ and \ }n\neq 9
(7,9) n\equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }9)

The known results for graphs with six vertices and more than nine edges, excluding those with isolated vertices, are described below.

The spectrum for the unique closed 10-trail on six vertices is dealt with in the section on even graphs.

The known results on the spectrum problem for K_6 are covered in the section on complete graphs.

In [7] it is shown by computer search that there is no (K_6-e)-design of order 29 (K_6-e is the graph obtained by removing an edge from K_6). This is the only known example of a non-complete graph, G say, such that there is no G-design of order 2|E(G)|+1.



Notes


  • The spectrum problem for H^7_{19} and H^7_{20} is settled in [4]. However, as [4] is not easily accessible the construction is included in [2].
  • Some of the graphs in this section belong to special families and have thus been covered in other sections of this site. For example, some are trees, even graphs, matchings or theta graphs.
  • In [10] the authors incorrectly state that there are twenty non-isomorphic graphs with six vertices and nine edges, excluding those with isolated vertices. There are in fact twenty one (see [6] and [13]).


References


  1. ↑ 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. ↑ 2.0 2.1 2.2 2.3 Adams, P., Bryant, D., and Buchanan, M. A survey on the existence of G-designs, J. Combin. Des. 16, 373–410 (2008).
  3. ↑ Adams, P., Bryant, D. E., and Khodkar, A. The spectrum problem for closed m-trails, m\leq 10, J. Combin. Math. Combin. Comput. 34, 223–240 (2000).
  4. ↑ 4.0 4.1 4.2 Cui, Y. G. Decompositions and packings of λK_v into K_2,s with a pendant edge, PhD Thesis (2002).
  5. ↑ 5.0 5.1 Guy, R. K. and Beineke, L. W. The coarseness of the complete graph, Canad. J. Math. 20, 888–894 (1968).
  6. ↑ 6.0 6.1 Harary, F. Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, (1969).
  7. ↑ 7.0 7.1 Hartke, S. G., Östergård, P. R. J., Bryant, D., and El-Zanati, S. I. The nonexistence of a (K_6-e)-decomposition of the complete graph K_29, J. Combin. Des. 18, 94–104 (2010).
  8. ↑ Huang, C. and Rosa, A. Decomposition of complete graphs into trees, Ars Combin. 5, 23–63 (1978).
  9. ↑ Kang, Q., Yuan, L., and Liu, S. Graph designs for all graphs with six vertices and eight edges, Acta Math. Appl. Sin. Engl. Ser. 21, 469–484 (2005).
  10. ↑ 10.0 10.1 10.2 10.3 Kang, Q., Zhao, H., and Ma, C. Graph designs for nine graphs with six vertices and nine edges, Ars Combin. 88, 379–395 (2008).
  11. ↑ 11.0 11.1 Mullin, R. C., Poplove, A. L., and Zhu, L. Decomposition of Steiner triple systems into triangles, Proceedings of the first Carbondale combinatorics conference (Carbondale, Ill., 1986), 149–174 (1987).
  12. ↑ 12.0 12.1 Tian, Z., Du, Y., and Kang, Q. Decomposing complete graphs into isomorphic subgraphs with six vertices and seven edges, Ars Combin. 81, 257–279 (2006).
  13. ↑ 13.0 13.1 Read, R. C. and Wilson, R. J. An atlas of graphs, Oxford Science Publications, New York:The Clarendon Press Oxford University Press, (1998).
  14. ↑ 14.0 14.1 Wang, L. The spectrum for a class of graph designs, Preprint, (2009).
  15. ↑ Yin, J. X. and Gong, B. S. Existence of G-designs with \vert V(G)\vert =6, Lecture Notes in Pure and Appl. Math. Combinatorial designs and applications (Huangshan, 1988), Dekker, New York, 201–218 (1990).