Even graphs

From G-designs

Jump to: navigation, search

Relevant articles: [1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11].

Contents

[hide]

Even graphs


A graph is even if each vertex has even degree.

A 2-regular graph is a union of vertex disjoint cycles.

We denote by C_{m_1}\cup C_{m_2}\cup\cdots\cup C_{m_t} the 2-regular graph consisting of t vertex disjoint cycles of lengths m_1,m_2,\ldots,m_t.

An even graph which is connected is called a closed trail, and a closed trail with m edges is a called a closed m-trail.


Figure 1: Some even graphs
Some even graphs




Spectrum Results


Table 1 summarises the known results on the spectrum problem for even graphs with up to ten edges. An explanation of the sources of these results is given in [1].

Table 1

Table 1: The spectrum for even graphs with up to 10 edges.
m Spectrum for each even graph with m edges Exceptions (E_1 and E_3 as in Figure 1)
3 n \equiv 1 {\rm \ or \ } 3 \,({\rm mod \ }6) \emptyset
4 n \equiv 1 \,({\rm mod \ }8) \emptyset
5 n \equiv 1 {\rm \ or \ } 5 \,({\rm mod \ }10) \emptyset
6 n \equiv 1 {\rm \ or \ } 9 \,({\rm mod \ }12) {\rm There \ is \ no \ }(C_3 \cup C_3){\rm-design \ of \ order \ }9.
7 n \equiv 1 {\rm \ or \ } 7 \,({\rm mod \ }14) \emptyset
8 n \equiv 1 \,({\rm mod \ }16) \emptyset
9 n \equiv 1 {\rm \ or \ } 9 \,({\rm mod \ }18) {\rm There \ is \ no \ }G{\rm-design \ of \ order \ }9{\rm \ for \ }G\in\{C_4 \cup C_5, E_1, E_3\}.
10 n \equiv 1 {\rm \ or \ } 5 \,({\rm mod \ }20){\rm \ and \ }n\neq 5 {\rm There \ is \ a \ }K_5{\rm-design \ of \ order \ }5.


Theorem 1 [7]

Let G be a 2-regular bipartite graph. There exists a G-design of order n for all n \equiv 1 \,({\rm mod \ }2|E(G)|).


Theorem 2 [4]

Let G be a 2-regular graph with at most three components. There exists a G-design of order 2|E(G)| + 1.


Theorem 3

Let G be the union of t vertex disjoint 3-cycles.

  • There exists a G-design of order 6t+1 [8].
  • If n \equiv 1 {\rm \ or \ } 3 \,({\rm mod \ }6) and n > 9t there exists a G-design of order n [9].


Theorem 4 [9]

Let D_l be the union of l edge-disjoint 3-cycles each sharing a common vertex. If n(n-1) \equiv 0 \,({\rm mod \ }6l) and n>6l then there exists a D_l-design of order n.




Notes


  • It is well-known (though at present there is no published proof, see [5]) that there is no (C_3\cup C_3\cup C_5)-design of order 11.
  • Results on the famous Oberwolfach problem provide further G-designs of orders n for many instances where G is a 2-regular graph with n vertices, see the section on unions of graphs.
  • When 3\leq m\leq 5 the only closed m-trails are cycles (see the section on cycles).
  • When m=6 we have only the 6-cycle and the graph G_{15} (see Figure 1 in the section on Graphs with five vertices).
  • A Dutch l-windmill, denoted D_l, is the graph containing a vertex, x say, such that D_l is the union of l edge-disjoint 3-cycles, all of which contain the vertex x.
  • There are four even graphs with 10 or fewer vertices which are neither 2-regular nor closed trails, namely the graphs E_3, E_4, E_5 and E_6 shown in Figure 1.


References


  1. 1.0 1.1 Adams, P., Bryant, D., and Buchanan, M. A survey on the existence of G-designs, J. Combin. Des. 16, 373–410 (2008).
  2. Adams, P., Bryant, D., and Gavlas, H. Decompositions of the complete graph into small 2-regular graphs, J. Combin. Math. Combin. Comput. 43, 135–146 (2002).
  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 Aguado, A., El-Zanati, S. I., Hake, H., Stob, J., and Yayla, H. On ρ-labeling the union of three cycles, Australas. J. Combin. 37, 155–170 (2007).
  5. 5.0 5.1 Alspach, B. The Oberwolfach problem, CRC Press Series on Discrete Mathematics and its Applications, The CRC handbook of combinatorial designs, ed. 1, CRC Press, 394–395 (1996).
  6. 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).
  7. 7.0 7.1 Blinco, A. and El-Zanati, S. I. A note on the cyclic decomposition of complete graphs into bipartite graphs, Bull. Inst. Combin. Appl. 40, 77–82 (2004).
  8. 8.0 8.1 Dinitz, J. H. and Rodney, P. Disjoint difference families with block size 3, Util. Math. 52, 153–160 (1997).
  9. 9.0 9.1 9.2 Horák, P. and Rosa, A. Decomposing Steiner triple systems into small configurations, Ars Combin. 26, 91–105 (1988).
  10. Köhler, E. Über das Oberwolfacher Problem, Lehrbücher Monograph. Geb. Exakten Wissensch., Math. Reihe, Beiträge zur geometrischen Algebra (Proc. Sympos., Duisburg, 1976), Birkhäuser, Basel, 189–201 (1977).
  11. 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).