The spectrum problem for digraphs of order 4 and size 5

• Autorzy: Bunge R. C. , DeShong S , El-Zanati S. I. , Fischer A. , Roberts D. P. , Teng L.

Identyfikatory

DOI

10.7494/OpMath.2018.38.1.15

• Języki publikacji: EN

Abstrakty

EN

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 [formula] design. Partial results are given for the remaining 6 possibilities for D.

Słowa kluczowe

EN

spectrum problem; digraph decompositions

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2018
• Tom: Vol. 38, no. 1
• Strony: 15--30
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Bunge R. C.

• Illinois State University Normal, IL 61790-4520, USA

autor

DeShong S

• Virginia Polytechnic Institute and State University Blacksburg, VA 24061, USA

autor

El-Zanati S. I.

• Illinois State University Normal, IL 61790-4520, USA

autor

Fischer A.

• Jacobs High School Algonquin, IL 60102, USA

autor

Roberts D. P.

• Illinois Wesleyan University Bloomington, IL 61701, USA

autor

Teng L.

• University of Michigan Ann Arbor, MI 48109, USA

Bibliografia

• [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 Kn, 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. Young-blood, 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 X-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. Un-sicker, N.E. Witt, On the spectra of bipartite directed subgraphs of K%, 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. Kolotoglu, H. Wei, A complete solution to spectrum problem for five-vertex graphs with application to traffic groom/ing 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.

Uwagi

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).