Opuscula Math. 38, no. 1 (2018), 15-30
https://doi.org/10.7494/OpMath.2018.38.1.15

Opuscula Mathematica

The spectrum problem for digraphs of order 4 and size 5

Ryan C. Bunge
Steven DeShong
Alexander Fischer
Dan P. Roberts
Lawrence Teng

Abstract. The paw graph consists of a triangle with a pendant edge attached to one of the three vertices. We obtain a multigraph by adding exactly one repeated edge to the paw. Now, let $$D$$ be a directed graph obtained by orientating the edges of that multigraph. For 12 of the 18 possibilities for $$D$$, we establish necessary and sufficient conditions on $$n$$ for the existence of a $$(K^{*}_{n},D)$$-design. Partial results are given for the remaining 6 possibilities for $$D$$.

Keywords: spectrum problem, digraph decompositions.

Mathematics Subject Classification: 05C20, 05C51.

Full text (pdf)

1. R.J.R. Abel, F.E. Bennett, M. Greig, PBD-Closure, [in:] Handbook of Combinatorial Designs, C.J. Colbourn, J.H. Dinitz (eds), 2nd ed., Chapman & Hall/CRC Press, Boca Raton, FL, 2007, 246-254.
2. P. Adams, D. Bryant, M. Buchanan, A survey on the existence of $$G$$-designs, J. Combin. Des. 16 (2008), 373-410.
3. J.-C. Bermond, J. Schönheim, $$G$$-decomposition of $$K_n$$, where $$G$$ has four vertices or less, Discrete Math. 19 (1977), 113-120.
4. J.-C. Bermond, C. Huang, A. Rosa, D. Sotteau, Decomposition of complete graphs into isomorphic subgraphs with five vertices, Ars Combin. 10 (1980), 211-254.
5. D. Bryant, S. El-Zanati, Graph Decompositions, [in:] Handbook of Combinatorial Designs, C.J. Colbourn, J.H. Dinitz (eds), 2nd ed., Chapman & Hall/CRC Press, Boca Raton, FL, 2007, 477-486.
6. R.C. Bunge, C.J. Cowan, L.J. Cross, S.I. El-Zanati, A.E. Hart, D. Roberts, A.M. Youngblood, Decompositions of complete digraphs into small tripartite digraphs, J. Combin. Math. Combin. Comput. 102 (2017), 239-251.
7. R.C. Bunge, S.I. El-Zanati, L. Febles Miranda, J. Guadarrama, D. Roberts, E. Song, A. Zale, On the $$\lambda$$-fold spectra of tripartite multigraphs of order 4 and size 5, Ars Combin., to appear.
8. R.C. Bunge, S.I. El-Zanati, H.J. Fry, K.S. Krauss, D.P. Roberts, C.A. Sullivan, A.A. Unsicker, N.E. Witt, On the spectra of bipartite directed subgraphs of $$K^*_4$$, J. Combin. Math. Combin. Comput. 98 (2016), 375-390.
9. C.J. Colbourn, J.H. Dinitz (eds), Handbook of Combinatorial Designs, 2nd ed., Chapman & Hall/CRC Press, Boca Raton, FL, 2007.
10. G. Ge, Group divisible designs, [in:] Handbook of Combinatorial Designs, C.J. Colbourn, J.H. Dinitz (eds), 2nd ed., Chapman & Hall/CRC Press, Boca Raton, FL, 2007, 255-260.
11. G. Ge, S. Hu, E. Kolotoğlu, H. Wei, A complete solution to spectrum problem for five-vertex graphs with application to traffic grooming in optical networks, J. Combin. Des. 23 (2015), 233-273.
12. M. Greig, R. Mullin, PBDs: Recursive Constructions, [in:] Handbook of Combinatorial Designs, C.J. Colbourn, J.H. Dinitz (eds), 2nd ed., Chapman & Hall/CRC Press, Boca Raton, FL, 2007, 236-246.
13. A. Hartman, E. Mendelsohn, The last of the triple systems, Ars Combin. 22 (1986), 25-41.
14. R.C. Read, R.J. Wilson, An Atlas of Graphs, Oxford University Press, Oxford, 1998.
15. R.M. Wilson, Decompositions of complete graphs into subgraphs isomorphic to a given graph, Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975), Congressus Numerantium, No. XV, Utilitas Math., Winnipeg, Man., 1976, 647-659.
• Ryan C. Bunge
• Illinois State University, Normal, IL 61790-4520, USA
• Steven DeShong
• Virginia Polytechnic Institute and State University, Blacksburg, VA 24061, USA
• Illinois State University, Normal, IL 61790-4520, USA
• Alexander Fischer
• Jacobs High School, Algonquin, IL 60102, USA
• Dan P. Roberts
• Illinois Wesleyan University, Bloomington, IL 61701, USA
• Lawrence Teng
• University of Michigan, Ann Arbor, MI 48109, USA
• Communicated by Mariusz Meszka.
• Revised: 2017-06-06.
• Accepted: 2017-06-14.
• Published online: 2017-11-13.