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
Saad I. El-Zanati
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.
- 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.
- P. Adams, D. Bryant, M. Buchanan, A survey on the existence of \(G\)-designs, J. Combin. Des. 16 (2008), 373-410.
- J.-C. Bermond, J. Schönheim, \(G\)-decomposition of \(K_n\), where \(G\) has four vertices or less, Discrete Math. 19 (1977), 113-120.
- 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.
- 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.
- 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.
- 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.
- 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.
- C.J. Colbourn, J.H. Dinitz (eds), Handbook of Combinatorial Designs, 2nd ed., Chapman & Hall/CRC Press, Boca Raton, FL, 2007.
- 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.
- 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.
- 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.
- A. Hartman, E. Mendelsohn, The last of the triple systems, Ars Combin. 22 (1986), 25-41.
- R.C. Read, R.J. Wilson, An Atlas of Graphs, Oxford University Press, Oxford, 1998.
- 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
- Saad I. El-Zanati
- 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.
- Received: 2016-01-05.
- Revised: 2017-06-06.
- Accepted: 2017-06-14.
- Published online: 2017-11-13.
