Theta graphs

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

 $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).