Theta graphs

From G-designs

Jump to: navigation, search

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

Theta graphs


The theta graph \Theta(a,b,c) is the graph consisting of three internally disjoint paths with common endpoints and lengths a, b and c with a\leq b\leq c.


Spectrum Results


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

Table 1

Table 1: The spectrum for theta graphs with up to 9 edges.
m Spectrum for theta graphs with m edges Exceptions
5 n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }5) {\rm There \ is \ no \ }\Theta(1,2,2){\rm -design \ of \ order \ }5.
6 n \equiv 0,1,4 {\rm \ or \ } 9 \,({\rm mod \ }245)

{\rm and \ }n\neq 4

{\rm There \ is \ no \ }\Theta(2,2,2){\rm -design \ of \ order \ }9.

{\rm There \ is \ no \ }\Theta(2,2,2){\rm -design \ of \ order \ }12.

7 n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }7) {\rm There \ is \ no \ }\Theta(1,3,3){\rm -design \ of \ order \ }7.

{\rm There \ is \ no \ }\Theta(2,2,3){\rm -design \ of \ order \ }7.

8 n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }16) \emptyset
9 n \equiv 0 {\rm \ or \ } 1 \,({\rm mod \ }9) {\rm There \ is \ no \ }\Theta(1,4,4){\rm -design \ of \ order \ }9.

{\rm There \ is \ no \ }\Theta(2,2,5){\rm -design \ of \ order \ }9.

{\rm There \ is \ no \ }\Theta(3,3,3){\rm -design \ of \ order \ }9.


Theorem 1 [4]

There exists a \Theta(1,k,k)-design of order n in each of the following cases.

  • k is odd and n \equiv 0 \,({\rm mod \ }2k+1) except when (k,n)=(3,7).
  • k\in\{5,9\} and n \equiv 1 \,({\rm mod \ }2k+1).
  • k \equiv 3 \,({\rm mod \ }4) and n \equiv 1 \,({\rm mod \ }2k+1).
  • k \equiv 1 \,({\rm mod \ }4), k \geq 13 and n \equiv 1 \,({\rm mod \ }4k+2).


Theorem 2 [6], [7], [8]

Let a \geq 1, let b,c \geq 2 and let a \leq b \leq c. There exists a \Theta(a,b,c)-design of order 2(a+b+c) + 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. ↑ 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. ↑ Bermond, J. -C. and Schönheim, J. $G-decomposition of K_n, where G has four vertices or less, Discrete Math. 19, 113–120 (1977).
  4. ↑ 4.0 4.1 Blinco, A. On diagonal cycle systems, Australas. J. Combin. 24, 221–230 (2001).
  5. ↑ Blinco, A. Decompositions of complete graphs into theta graphs with fewer than ten edges, Util. Math. 64, 197–212 (2003).
  6. ↑ 6.0 6.1 Delorme, C., Maheo, M., Thuillier, H., Koh, K. M., and Teo, H. K. Cycles with a chord are graceful, J. Graph Theory, 4, 409–415 (1980).
  7. ↑ 7.0 7.1 Koh, K. M. and Yap, K. Y. Graceful numberings of cycles with a P_3-chord, Bull. Inst. Math. Acad. Sinica, 13, 41–48 (1985).
  8. ↑ 8.0 8.1 Punnim, N. and Pabhapote, N. On graceful graphs: cycles with a P_k-chord, k\geq 4, Ars Combin. 23, 225–228 (1987).