×

Miscellaneous digraph classes. (English) Zbl 1407.05109

Bang-Jensen, Jørgen (ed.) et al., Classes of directed graphs. Cham: Springer. Springer Monogr. Math., 517-574 (2018).
Summary: Obviously, there are countless digraph classes, so that any attempt to give a complete overview is doomed to failure. One has to restrict oneself to a selection. This chapter tries to survey some of the digraph classes that were not granted their own chapter in this book. As tournaments are arguably the best studied class of digraphs with a rich library of strong results, it is no wonder that they and their many generalizations are featured prominently throughout the book. In this regard, this chapter poses no exception. We examine arc-locally semicomplete digraphs, which generalize both semicomplete and semicomplete bipartite digraphs, as well as their generalizations \(\mathcal {H}_1\)-free digraphs and \(\mathcal {H}_2\)-free digraphs. The related classes of \(\mathcal {H}_3\)-free digraphs and \(\mathcal {H}_4\)-free digraphs are also briefly considered. Of course, there are also digraph classes (fairly) unrelated to tournaments such as kernel-perfect digraphs which are mentioned in several results throughout the book and appear in this chapter in a section mainly dedicated to perfect digraphs, game-perfect digraphs and weakly game-perfect digraphs. Furthermore, we consider some digraph classes that appear naturally in applications to other fields such as mathematical logic or computer science. Two such classes with applications in the construction of interconnection networks are de Bruijn digraphs and Kautz digraphs. Both classes can be defined using the line digraph operator. We also investigate line digraphs and iterated line digraphs in general. Minimal series-parallel digraphs, series-parallel digraphs and series-parallel partial order digraphs appear in flow diagrams and dependency charts and have an application to the problem of scheduling under constraints. We consider them briefly in a section on directed cographs, a generalization of series-parallel partial order digraphs.
For the entire collection see [Zbl 1398.05002].

MSC:

05C20 Directed graphs (digraphs), tournaments
Full Text: DOI

References:

[1] M. Aigner. On the linegraph of a directed graph. Mathematische Zeitschrift, 102(1):56-61, 1967. · Zbl 0158.20901 · doi:10.1007/BF01110285
[2] B. Alspach and T.D. Parsons. Isomorphism of circulant graphs and digraphs. Discrete Mathematics, 25(2):97-108, 1979. · Zbl 0402.05038 · doi:10.1016/0012-365X(79)90011-6
[3] S.D. Andres. Asymmetric directed graph coloring games. Discrete Math., 309(18):5799-5802, 2009. · Zbl 1177.91054 · doi:10.1016/j.disc.2008.03.022
[4] S.D. Andres. Directed defective asymmetric graph coloring games. Discrete Appl. Math., 158(4):251-260, 2010. · Zbl 1226.05114 · doi:10.1016/j.dam.2009.04.025
[5] S.D. Andres. Game-perfect digraphs. Math. Methods Oper. Res., 76(3):321-341, 2012. · Zbl 1278.91026 · doi:10.1007/s00186-012-0401-x
[6] S.D. Andres. Lightness of digraphs in surfaces and directed game chromatic number. Discrete Math., 309(11):3564-3579, 2009. · Zbl 1225.05105 · doi:10.1016/j.disc.2007.12.060
[7] S.D. Andres. On characterizing game-perfect graphs by forbidden induced subgraphs. Contributions to Discrete Mathematics, 7(1), 2012. · Zbl 1317.05045
[8] S.D. Andres. On kernels in game-perfect digraphs and a characterization of weakly game-perfect digraphs. Technical report feU-dmo043.17, Fakultät für Mathematik und Informatik, Fernuniversität Hagen, Germany, 2017.
[9] S.D. Andres and W. Hochstättler. Perfect digraphs. J. Graph Theory, 79(1):21-29, 2015. · Zbl 1312.05059 · doi:10.1002/jgt.21811
[10] A. Arroyo and H. Galeana-Sánchez. The path partition conjecture is true for some generalizations of tournaments. Discrete Math., 313(3):293-300, 2013. · Zbl 1256.05085 · doi:10.1016/j.disc.2012.10.014
[11] L. Baffi and R. Petreschi. Parallel maximal matching on minimal vertex series parallel digraphs. In Algorithms, concurrency and knowledge (Pathumthani, 1995), pages 34-47. Springer-Verlag, 1995. · doi:10.1007/3-540-60688-2_33
[12] C. Balbuena and M. Guevara. Kernels and partial line digraphs. Appl. Math. Lett., 23(10):1218-1220, 2010. · Zbl 1193.05083 · doi:10.1016/j.aml.2010.06.001
[13] J. Bang-Jensen. Arc-local tournament digraphs: a generalization of tournaments and bipartite tournaments. Technical report 2, Department of Mathematics and Computer Science, Odense University, Denmark, 1993.
[14] J. Bang-Jensen. Digraphs with the path-merging property. J. Graph Theory, 20(2):255-265, 1995. · Zbl 0832.05047 · doi:10.1002/jgt.3190200214
[15] J. Bang-Jensen. The structure of strong arc-locally semicomplete digraphs. Discrete Math., 283(1-3):1-6, 2004. · Zbl 1048.05038 · doi:10.1016/j.disc.2004.01.011
[16] J. Bang-Jensen and G. Gutin. Digraphs: Theory, Algorithms and Applications. Springer-Verlag, London, 2nd edition, 2009. · Zbl 1170.05002 · doi:10.1007/978-1-84800-998-1
[17] J. Bang-Jensen and G. Gutin. Paths and cycles in extended and decomposable digraphs. Discrete Math., 164(1-3):5-19, 1997. · Zbl 0872.05028 · doi:10.1016/S0012-365X(96)00038-6
[18] J. Bang-Jensen, F. Havet, and N. Trotignon. Finding an induced subdivision of a digraph. Theor. Comput. Sci., 443:10-24, 2012. · Zbl 1243.68190 · doi:10.1016/j.tcs.2012.03.017
[19] J. Bang-Jensen and A. Maddaloni. Arc-disjoint paths in decomposable digraphs. J. Graph Theory, 77(2):89-110, 2014. · Zbl 1302.05063 · doi:10.1002/jgt.21775
[20] J. Bang-Jensen and Y. Manoussakis. Cycles through \(k\) vertices in bipartite tournaments. Combinatorica, 14(2):243-246, 1994. · Zbl 0812.05023 · doi:10.1007/BF01215353
[21] D. Bauer, F. Boesch, C. Suffel, and R. Tindell. Connectivity extremal problems and the design of reliable probabilistic networks. Theory and Application of Graphs, pages 89-98, 1981. · Zbl 0469.05044
[22] D. Bechet, P. De Groote, and C. Retoré. A complete axiomatisation for the inclusion of series-parallel partial orders. In International Conference on Rewriting Techniques and Applications, pages 230-240. Springer, 1997. · Zbl 1379.06001 · doi:10.1007/3-540-62950-5_74
[23] L.W. Beineke and C.M. Zamfirescu. Connection digraphs and second-order line digraphs. Discrete Math., 39:237-254, 1982. · Zbl 0483.05031 · doi:10.1016/0012-365X(82)90147-9
[24] C. Berge. Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 10(114):88, 1961.
[25] C. Berge and P. Duchet. Recent problems and results about kernels in directed graphs. Discrete Math., 86(1-3):27-31, 1990. · Zbl 0721.05027 · doi:10.1016/0012-365X(90)90346-J
[26] J.-C. Bermond and P. Fraigniaud. Broadcasting and gossiping in de Bruijn networks. SIAM J. Comput., 23(1):212-225, 1994. · Zbl 0802.68094 · doi:10.1137/S0097539791197852
[27] J.-C. Bermond, N. Homobono, and C. Peyrat. Large fault-tolerant interconnection networks. Graphs Combin., 5(1):107-123, 1989. · Zbl 0672.94021 · doi:10.1007/BF01788663
[28] J.-C. Bermond, X. Munos, and A. Marchetti-Spaccamela. A Broadcasting Protocol in Line Digraphs. J. Parallel Distributed Comput., 61(8):1013-1032, 2001. · Zbl 0988.68012 · doi:10.1006/jpdc.2001.1737
[29] P. Bertolazzi, R.F. Cohen, G. Di Battista, R. Tamassia, and I.G. Tollis. How to draw a series-parallel digraph. Int. J. Comput. Geom. Appl., 4(4):385-402, 1994. · Zbl 0829.68098 · doi:10.1142/S0218195994000215
[30] H. Bidkhori and S. Kishore. A bijective proof of a theorem of Knuth. Combin. Prob. Comput., 20(1):11-25, 2011. · Zbl 1221.05174 · doi:10.1017/S0963548310000192
[31] E. Boros and V. Gurvich. Perfect graphs are kernel-solvable. Discrete Math., 159:35-55, 1996. · Zbl 0861.05053 · doi:10.1016/0012-365X(95)00096-F
[32] E. Boros and V. Gurvich. Perfect graphs, kernels, and cores of cooperative games. Discrete Math., 306(19):2336-2354, 2006. · Zbl 1103.05034 · doi:10.1016/j.disc.2005.12.031
[33] A. Bretscher, D.G. Corneil, M. Habib, and C. Paul. A simple linear time lexbfs cograph recognition algorithm. SIAM Journal on Discrete Mathematics, 22(4):1277-1296, 2008. · Zbl 1187.05070 · doi:10.1137/060664690
[34] W.G. Bridges and S. Toueg. On the impossibility of directed Moore graphs. J. Combin. Theory Ser. B, 29:339-341, 1980. · Zbl 0388.05019 · doi:10.1016/0095-8956(80)90091-X
[35] D.E. Brown, A.H. Busch, and J.R. Lundgren. Interval tournaments. J. Graph Theory, 56:72-81, 2007. · Zbl 1130.05028 · doi:10.1002/jgt.20247
[36] F. Cao, D.-Z. Du, D.F. Hsu, L. Hwang, and W. Wu. Super line-connectivity of consecutive-d digraphs. Discrete Math., 183(1):27-38, 1998. · Zbl 0895.05035 · doi:10.1016/S0012-365X(97)00079-4
[37] W.H. Chan, W.C. Shiu, P.K. Sun, and X. Zhu. The strong game colouring number of directed graphs. Discrete Math., 313(10):1070-1077, 2013. · Zbl 1261.05065 · doi:10.1016/j.disc.2013.02.001
[38] X. Cheng, X. Du, M. Min, H.Q. Ngo, L. Ruan, J. Sun, and W. Wu. Super link-connectivity of iterated line digraphs. Theor. Comput. Sci., 304(1):461-469, 2003. · Zbl 1045.68019 · doi:10.1016/S0304-3975(03)00282-2
[39] M. Chudnovsky, G. Cornuéjols, X. Liu, P.D. Seymour, and K. Vušković. Recognizing Berge graphs. Combinatorica, 25(2):143-186, 2005. · Zbl 1089.05027 · doi:10.1007/s00493-005-0012-8
[40] M. Chudnovsky, N. Robertson, P.D. Seymour, and R. Thomas. The strong perfect graph theorem. Annals Math., pages 51-229, 2006. · Zbl 1112.05042 · doi:10.4007/annals.2006.164.51
[41] V. Chvátal and C. Ebenegger. A note on line digraphs and the directed max-cut problem. Discrete Appl. Math., 29(2):165-170, 1990. · Zbl 0739.90070 · doi:10.1016/0166-218X(90)90141-X
[42] D.G. Corneil, Y. Perl, and L.K. Stewart. A linear recognition algorithm for cographs. SIAM J. Comput., 14(4):926-934, 1985. · Zbl 0575.68065 · doi:10.1137/0214065
[43] C. Crespelle and C. Paul. Fully dynamic recognition algorithm and certificate for directed cographs. Discrete Appl. Math., 154(12):1722-1741, 2006. · Zbl 1110.68096 · doi:10.1016/j.dam.2006.03.005
[44] S.J. Curran and J.A. Gallian. Hamiltonian cycles and paths in Cayley graphs and digraphs – a survey. Discrete Mathematics, 156(1-3):1-18, 1996. · Zbl 0857.05067 · doi:10.1016/0012-365X(95)00072-5
[45] S. Das, M. Francis, P. Hell, and J. Huang. Recognition and characterization of chronological interval digraphs. the electronic journal of combinatorics, 20(3):P5, 2013. · Zbl 1295.05161
[46] S. Das and M. Sen. An interval digraph in relation to its associated bipartite graph. Discrete Math., 122(1-3):113-136, 1993. · Zbl 0792.05060 · doi:10.1016/0012-365X(93)90290-A
[47] S. Dasgupta. On characterizations and structure of interval digraphs and unit probe interval graphs. PhD thesis, University of Colorado, 2012.
[48] N.G. de Bruijn. A combinatorial problem. Ned. Akad. Wet. Proc., 49:758-764, 1946. · Zbl 0060.02701
[49] D.-Z. Du, F. Cao, and D.F. Hsu. De Bruijn digraphs, and Kautz digraphs, and their generalizations. In D.-Z. Du and D.F. Hsu, editors, Combinatorial network theory, pages 65-105. Kluwer, Dordrecht, 1996. · Zbl 0845.05049 · doi:10.1007/978-1-4757-2491-2_3
[50] D.-Z. Du, D.F. Hsu, and F.K. Hwang. Hamiltonian property of \(d\)-consecutive digraphs. Math. Comput. Modeling, 17:61-63, 1993. · Zbl 0789.05040 · doi:10.1016/0895-7177(93)90253-U
[51] D.-Z. Du, D.F. Hsu, and Y.-D. Lyuu. Corrigendum to ’Line digraph iterations and connectivity analysis of de Bruijn and Kautz Graphs’. IEEE Trans. Computers, 45(7):863, 1996. · doi:10.1109/TC.1996.508325
[52] D.-Z. Du, D.F. Hsu, and Y.-D. Lyuu. On the diameter vulnerability of Kautz digraphs. Discrete Math., 151(1):81-85, 1996. · Zbl 0853.05043 · doi:10.1016/0012-365X(94)00084-V
[53] D.-Z. Du, D.F. Hsu, H.Q. Ngo, and G.W. Peck. On connectivity of consecutive-\(d\) digraphs. Discrete Math., 257(2):371-384, 2002. · Zbl 1011.05035 · doi:10.1016/S0012-365X(02)00436-3
[54] D.-Z. Du, D.F. Hsu, and G.W. Peck. Connectivity of consecutive-\(d\) digraphs. Discrete Appl. Math., 37:169-177, 1992. · Zbl 0776.05045 · doi:10.1016/0166-218X(92)90131-S
[55] D.-Z. Du, Y.-D. Lyuu, and D.F. Hsu. Line digraph iterations and connectivity analysis of de Bruijn and Kautz graphs. IEEE Trans. Computers, 42(5):612-616, 1993. · Zbl 1395.05068 · doi:10.1109/12.223681
[56] D.Z. Du, Y.-D. Lyuu, and D.F. Hsu. Line digraph iterations and the spread concept—with application to graph theory, fault tolerance, and routing. In WG 1991: Graph-theoretic concepts in computer science, volume 570 of Lect. Notes Comput. Sci., pages 169-179. Springer, 1992. · Zbl 0776.05046
[57] P. Duchet and H. Meyniel. A note on kernel-critical graphs. Discrete Math., 33(1):103-105, 1981. · Zbl 0456.05032 · doi:10.1016/0012-365X(81)90264-8
[58] D. Duffus, H. Lefmann, and V. Rödl. Shift graphs and lower bounds on Ramsey numbers \(r_k(l;r)\). Discrete Math., 137(1):177-187, 1995. · Zbl 0822.05047 · doi:10.1016/0012-365X(93)E0139-U
[59] A. Ehrenfeucht and G. Rozenberg. Primitivity is hereditary for 2-structures. Theor. Comput. Sci., 70(3):343-358, 1990. · Zbl 0701.05053 · doi:10.1016/0304-3975(90)90131-Z
[60] J. Fàbrega and M.A. Fiol. Maximally connected digraphs. J. Graph Theory, 13(6):657-668, 1989. · Zbl 0688.05029 · doi:10.1002/jgt.3190130603
[61] J. Fabrega, M.A. Fiol, J.L.A. Yebra, and I. Alegre. Connectivity and reliable routing algorithms in line digraphs. In 3rd Int. Symp. Applied Informatics, pages 45-50, 1985.
[62] T. Feder, P. Hell, J. Huang, and A. Rafiey. Adjusted interval digraphs. Elec. Notes Discrete Math., 32:83-91, 2009. · Zbl 1267.05257 · doi:10.1016/j.endm.2009.02.012
[63] M.A. Fiol, J.L.A. Yebra, and I. Alegre. Line digraph iteration and the \((d,k)\) digraph problem. IEEE Trans. Comput., C-33:400-403, 1984. · Zbl 0528.68048 · doi:10.1109/TC.1984.1676455
[64] H. Galeana-Sánchez. Kernels and perfectness in arc-local tournament digraphs. Discrete Math., 306(19-20):2473-2480, 2006. · Zbl 1102.05027 · doi:10.1016/j.disc.2005.12.036
[65] H. Galeana-Sánchez and I.A. Goldfeder. A classification of arc-locally semicomplete digraphs. Elec. Notes Discrete Math., 34:59-61, 2009. · Zbl 1272.05063 · doi:10.1016/j.endm.2009.07.010
[66] H. Galeana-Sánchez and I.A. Goldfeder. A classification of all arc-locally semicomplete digraphs. Discrete Math., 312(11):1883-1891, 2012. · Zbl 1243.05094 · doi:10.1016/j.disc.2012.02.022
[67] H. Galeana-Sánchez and I.A. Goldfeder. Hamiltonian cycles in a generalization of bipartite tournaments with a cycle factor. Discrete Math., 315:135-143, 2014. · Zbl 1279.05043 · doi:10.1016/j.disc.2013.10.019
[68] H. Galeana-Sánchez and R. Gómez. Independent sets and non-augmentable paths in generalizations of tournaments. Discrete Math., 308(12):2460-2472, 2008. · Zbl 1147.05042 · doi:10.1016/j.disc.2007.05.016
[69] H. Galeana-Sánchez and R. Gómez. \((k,l)\)-kernels,\((k,l)\)-semikernels, \(k\)-Grundy functions and duality for state splittings. Discuss. Math. Graph Theory, 27(2):359-371, 2007. · Zbl 1133.05039 · doi:10.7151/dmgt.1367
[70] H. Galeana-Sánchez and X. Li. Semikernels and \((k,l)\)-kernels in digraphs. SIAM J. Discrete Math., 11(2):340-346, 1998. · Zbl 0907.05025 · doi:10.1137/S0895480195291370
[71] H. Galeana-Sánchez, L.P. Ramírez, and H.A. Rincón-Mejía. Semikernels, quasi kernels, and Grundy functions in the line digraph. SIAM J. Discrete Math., 4(1):80-83, 1991. · Zbl 0723.05066 · doi:10.1137/0404008
[72] F. Gavril. Some NP-complete problems on graphs. In 11th Conf. on Information Sciences and Systems, pages 91-95, 1977.
[73] Z. Ge and S.L. Hakimi. Disjoint rooted spanning trees with small depths in deBruijn and Kautz graphs. SIAM J. Comput., 26(1):79-92, 1997. · Zbl 0874.05020 · doi:10.1137/S0097539793244198
[74] I.A. Goldfeder. Una clasificación de las digráficas localmente semicompletas en flechas. Undergraduate Thesis, Facultad de Ciencias, Universidad Nacional Autónoma de México, 2008.
[75] M. Grötschel, L. Lovász, and A. Schrijver. Polynomial algorithms for perfect graphs. North-Holland Mathematics Studies, 88:325-356, 1984. · Zbl 0554.05041 · doi:10.1016/S0304-0208(08)72943-8
[76] M. Guevara, C. Balbuena, and H. Galeana-Sánchez. Relation between number of kernels (and generalizations) of a digraph and its partial line digraphs. Elec. Notes Discrete Math., 54:265-269, 2016. · Zbl 1356.05060 · doi:10.1016/j.endm.2016.09.046
[77] Y. Guo and M. Surmacs. Pancyclic arcs in Hamiltonian cycles of hypertournaments. J. Korean Math. Soc, 51(6):1141-1154, 2014. · Zbl 1303.05107 · doi:10.4134/JKMS.2014.51.6.1141
[78] Y. Guo and M. Surmacs. Pancyclic out-arcs of a vertex in a hypertournament. Australas. J. Combinatorics, 61(3):227-250, 2015. · Zbl 1309.05084
[79] G. Gutin and A. Yeo. Hamiltonian paths and cycles in hypertournaments. J. Graph Theory, 25(4):277-286, 1997. · Zbl 0879.05041 · doi:10.1002/(SICI)1097-0118(199708)25:4<277::AID-JGT5>3.0.CO;2-H
[80] R. Häggkvist and Y. Manoussakis. Cycles and paths in bipartite tournaments with spanning configurations. Combinatorica, 9(1):33-38, 1989. · Zbl 0681.05036 · doi:10.1007/BF02122681
[81] Y.O. Hamidoune. On the connectivity of Cayley digraphs. European Journal of Combinatorics, 5(4):309-312, 1984. · Zbl 0561.05028 · doi:10.1016/S0195-6698(84)80034-7
[82] F. Harary and R.Z. Norman. Some properties of line digraphs. Rend. Circ. Mat. Palermo, 9(2):161-168, 1960. · Zbl 0099.18205 · doi:10.1007/BF02854581
[83] M. Harminc. Solutions and kernels of a directed graph. Mathematica Slovaca, 32(3):263-267, 1982. · Zbl 0491.05029
[84] C.C. Harner and R.C. Entringer. Arc colorings of digraphs. J. Combin.Theory Ser. B, 13(3):219-225, 1972. · Zbl 0231.05105 · doi:10.1016/0095-8956(72)90057-3
[85] T. Hasunuma and H. Nagamochi. Independent spanning trees with small depths in iterated line digraphs. Discrete Appl. Math., 110(2):189-211, 2001. · Zbl 0983.05023 · doi:10.1016/S0166-218X(00)00269-9
[86] T. Hasunuma and M. Otani. On the \((h,k)\)-domination numbers of iterated line digraphs. Discrete Appl. Math., 160(12):1859-1863, 2012. · Zbl 1246.05118 · doi:10.1016/j.dam.2012.03.024
[87] R.L. Hemminger. Line digraphs. In Graph Theory and Applications, pages 149-163. Springer, 1972. · Zbl 0247.05129 · doi:10.1007/BFb0067366
[88] R.L. Hemminger and L.W. Beineke. Line graphs and line digraphs. In L.W. Beineke and R.J. Wilson, editors, Selected Topics in Graph Theory, pages 271-305. Academic Press, London, 1978. · Zbl 0434.05056
[89] C. Hernández-Cruz and H. Galeana-Sánchez. \(k\)-kernels in \(k\)-transitive and \(k\)-quasi-transitive digraphs. Discrete Math., 312(16):2522-2530, 2012. · Zbl 1246.05067 · doi:10.1016/j.disc.2012.05.005
[90] C. Heuchenne. Sur une certaine correspondance entre graphs. Bull. Soc. R. Sci. Liége, 33:743-753, 1964. · Zbl 0134.43302
[91] A. Huck. Disproof of a conjecture about independent branchings in \(k\)-connected directed graphs. J. Graph Theory, 20(2):235-239, 1995. · Zbl 0833.05051 · doi:10.1002/jgt.3190200212
[92] M. Imase and M. Itoh. Design for directed graphs with minimum diameter. IEEE Trans. Comput., C-32:782-784, 1983. · Zbl 0515.94027 · doi:10.1109/TC.1983.1676323
[93] M. Imase and M. Itoh. Design to minimize a diameter on building block networks. IEEE Trans. Comput., C-30:439-443, 1981. · Zbl 0456.94030 · doi:10.1109/TC.1981.1675809
[94] M. Imase, I. Soneoka, and K. Okada. A fault tolerant processor interconnection network. Syst. Comput. Japan, 17:21-30, 1986. · doi:10.1002/scj.4690170803
[95] M. Imase, I. Soneoka, and K. Okada. Connectivity of regular directed graphs with small diameter. IEEE Trans. Comput., C-34:267-273, 1985. · Zbl 0554.05044 · doi:10.1109/TC.1985.1676569
[96] M. Imori, M. Matsumoto, and H. Yamada. The line digraph of a regular and pancircular digraph is also regular and pancircular. Graphs Combin., 4:235-239, 1988. · Zbl 0658.05032 · doi:10.1007/BF01864164
[97] H.A. Jung. On a class of posets and the corresponding comparability graphs. Journal of Combinatorial Theory, Series B, 24(2):125-133, 1978. · Zbl 0382.05045 · doi:10.1016/0095-8956(78)90013-8
[98] R.M. Karp. Reducibility among combinatorial problems. In Complexity of computer computations (Proc. Symp., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), pages 85-103. Plenum, 1972. · Zbl 1467.68065 · doi:10.1007/978-1-4684-2001-2_9
[99] W.H. Kautz. Bounds on directed \((d,k)\) graphs. Theory of cellular logic networks and machines. AFCRL-68-0668 Final report, pages 20-28, 1968.
[100] K.K. Kayibi, M.A. Khan, and S. Pirzada. Scores, inequalities and regular hypertournaments. J. Math. Ineq. Appl., 15(2):343-351, 2012. · Zbl 1238.05107
[101] K.K. Kayibi, M.A. Khan, and S. Pirzada. Uniform sampling of \(k\)-hypertournaments. Linear and Multilinear Algebra, 61(1):123-138, 2013. · Zbl 1259.05071 · doi:10.1080/03081087.2012.664771
[102] K.K. Kayibi, M.A. Khan, S. Pirzada, and G. Zhou. On scores, losing scores and total scores in hypertournaments. Elec. J. Graph Theory and Appl., 3(1):8-21, 2015. · Zbl 1467.05097
[103] D.E. Knuth. Oriented subtrees of an arc digraph. J. Combin. Theory, 3(4):309-314, 1967. · Zbl 0161.21001 · doi:10.1016/S0021-9800(67)80101-7
[104] Y. Koh and S. Ree. On \(k\)-hypertournament matrices. Linear algebra and its applications, 373:183-195, 2003. · Zbl 1026.05078 · doi:10.1016/S0024-3795(02)00726-7
[105] J. Krausz. Démonstration nouvelle d’une théorème de Whitney sur les réseaux. Mat. Fiz. Lapok, 50(1):75-85, 1943. · Zbl 0061.41401
[106] J.M. Laborde, C. Payan, and N.H. Xuong. Independent sets and longest directed paths in digraphs. Graphs and other combinatorial topics (Prague, 1982), 59:173-177, 1983. · Zbl 0528.05034
[107] E.L. Lawler. Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Ann. Discrete Math., 2:75-90, 1978. Algorithmic aspects of combinatorics (Conf., Vancouver Island, B.C., 1976). · Zbl 0374.68033
[108] L. Levine. Sandpile groups and spanning trees of directed line graphs. J. Combin. Theory Ser. A, 118(2):350-364, 2011. · Zbl 1292.05135 · doi:10.1016/j.jcta.2010.04.001
[109] H. Li, S. Li, Y. Guo, and M. Surmacs. On the vertex-pancyclicity of hypertournaments. Discrete Appl. Math., 161(16):2749-2752, 2013. · Zbl 1285.05079 · doi:10.1016/j.dam.2013.05.036
[110] H. Li, W. Ning, Y. Guo, and M. Lu. On pancyclic arcs in hypertournaments. Discrete Appl. Math., 215:164-170, 2016. · Zbl 1346.05136 · doi:10.1016/j.dam.2016.07.017
[111] R. Li, X. Zhang, S. Li, Q. Guo, and Y. Guo. The \(h\)-force set of a hypertournament. Discrete Appl. Math., 169:168-175, 2014. · Zbl 1288.05118 · doi:10.1016/j.dam.2013.12.020
[112] N. Lichiardopol. Independence number of iterated line digraphs. Discrete Math., 293(1):185-193, 2005. · Zbl 1062.05112 · doi:10.1016/j.disc.2004.08.030
[113] X. Liu and D.B. West. Line digraphs and coreflexive vertex sets. Discrete Math., 188(1-3):269-277, 1998. · Zbl 0957.05049 · doi:10.1016/S0012-365X(98)00022-3
[114] L. Lovász. A characterization of perfect graphs. J. Combin. Theory Ser. B, 13(2):95-98, 1972. · Zbl 0241.05107 · doi:10.1016/0095-8956(72)90045-7
[115] M. Lü and J.-M. Xu. Super connectivity of line graphs and digraphs. Acta Mathematicae Applicatae Sinica, 22(1):43-48, 2006. · Zbl 1104.05041 · doi:10.1007/s10255-005-0283-2
[116] Q. Lu, E. Shan, and M. Zhao. \((k,l)\)-kernels in line digraphs. J. Shanghai University (English Edition), 10(6):484-486, 2006. · Zbl 1110.05041 · doi:10.1007/s11741-006-0042-5
[117] R.H. Möhring. Computationally tractable classes of ordered sets. In Algorithms and order, pages 105-193. Springer, 1989. · Zbl 1261.06003 · doi:10.1007/978-94-009-2639-4_4
[118] R.H. Möhring and F.J. Radermacher. Substitution decomposition for discrete structures and connections with combinatorial optimization. North-Holland mathematics studies, 95:257-355, 1984. · Zbl 0567.90073 · doi:10.1016/S0304-0208(08)72966-9
[119] C.L. Monma and J.B. Sidney. A general algorithm for optimal job sequencing with series-parallel constraints. Math. Oper. Res., 4:215-224, 1977. · Zbl 0437.90047 · doi:10.1287/moor.4.3.215
[120] H. Müller. Recognizing interval digraphs and interval bigraphs in polynomial time. Discrete Appl. Math., 78:189-205, 1997. · Zbl 0890.68103 · doi:10.1016/S0166-218X(97)00027-9
[121] J. Nešetril and E. Sopena. On the oriented game chromatic number. Elec. J. Combin., 8(2), 2001. · Zbl 0982.05049
[122] V. Neumann-Lara. The dichromatic number of a digraph. J. Combin. Theory Ser. B., 33:265-270, 1982. · Zbl 0506.05031 · doi:10.1016/0095-8956(82)90046-6
[123] P. Ochem and A. Pinlou. Oriented vertex and arc colorings of partial 2-trees. Elec. Notes Discrete Math., 29:195-199, 2007. · Zbl 1341.05087 · doi:10.1016/j.endm.2007.07.034
[124] P. Ochem, A. Pinlou, and E. Sopena. On the oriented chromatic index of oriented graphs. J. Graph Theory, 57(4):313-332, 2008. · Zbl 1147.05032 · doi:10.1002/jgt.20286
[125] J.B. Orlin. Line-digraphs, arborescences, and theorems of Tutte and Knuth. J. Combin. Theory Ser. B, 25(2):187-198, 1978. · Zbl 0328.05113 · doi:10.1016/0095-8956(78)90038-2
[126] V. Petrovic and C. Thomassen. Edge-disjoint Hamiltonian cycles in hypertournaments. J. Graph Theory, 51(1):49-52, 2006. · Zbl 1086.05046 · doi:10.1002/jgt.20120
[127] A. Pinlou. On oriented arc-coloring of subcubic graphs. Elec. J. Combinatorics, 13(3):R69, 2006. · Zbl 1096.05023
[128] A. Pinlou and E. Sopena. Oriented vertex and arc colorings of outerplanar graphs. Inform. Process. Lett., 100(3):97-104, 2006. · Zbl 1185.05064 · doi:10.1016/j.ipl.2006.06.012
[129] S. Poljak and V. Rödl. On the arc-chromatic number of a digraph. J. Combin. Theory Ser. B, 31(2):190-198, 1981. · Zbl 0472.05024 · doi:10.1016/S0095-8956(81)80024-X
[130] E. Prisner. Bicliques in graphs. II. Recognizing \(k\)-path graphs and underlying graphs of line digraphs. In WG 1996: Graph-theoretic concepts in computer science, volume 1335 of Lect. Notes Comput. Sci., pages 273-287. Springer, 1997. · Zbl 0895.68103
[131] E. Prisner. Line graphs and generalizations—a survey. Congr. Numer., 116:193-229, 1996. Surveys in graph theory (San Francisco, 1995). · Zbl 0906.05061
[132] R.A. Rankin. A campanological problem in group theory. Math. Proc. Cambridge Philosophical Soc., 44:17-25, 1948. · Zbl 0030.10606 · doi:10.1017/S030500410002394X
[133] S.M. Reddy, J.G. Kuhl, S.H. Hosseini, and H. Lee. On digraphs with minimum diameter and maximum connectivity. In 20th Annual Allerton Conference, pages 1018-1026, 1982.
[134] S. M. Reddy, D.K. Pradhan, and J. G. Kuhl. Directed graphs with minimal diameter and maximal connectivity. Tech. Rep., School of Engineering, Oakland University, 1980.
[135] F. Rendl. Quadratic assignment problems on series-parallel digraphs. Z. Oper. Res. Ser. A-B, 30(3):A161-A173, 1986. · Zbl 0596.90063
[136] C. Retoré. Pomset logic as a calculus of directed cographs. Technical Report n3714, Unité de recherche INRIA Rennes, France, 1999.
[137] P.I. Richards. Precedence constraints and arrow diagrams. SIAM Rev., 9:548-553, 1967. · Zbl 0149.41702 · doi:10.1137/1009075
[138] B.K. Sanyal and M.K. Sen. New characterization of digraphs represented by intervals. J. Graph Theory, 22:297-303, 1996. · Zbl 0857.05040 · doi:10.1002/(SICI)1097-0118(199608)22:4<297::AID-JGT3>3.0.CO;2-G
[139] M. Sen, S. Das, A.B. Roy, and D.B. West. Interval digraphs: an analogue of interval graphs. J. Graph Theory, 13(2):189-202, 1989. · Zbl 0671.05039 · doi:10.1002/jgt.3190130206
[140] M. Sen, P. Talukdar, and S. Das. Chronological orderings of interval digraphs. Discrete Math., 306(14):1601-1609, 2006. · Zbl 1093.05027 · doi:10.1016/j.disc.2005.11.032
[141] M.K. Sen, B.K. Sanyal, and D.B. West. Representing digraphs using intervals or circular arcs. Discrete Math., 147(1-3):235-245, 1995. · Zbl 0838.05056 · doi:10.1016/0012-365X(94)00167-H
[142] E. Shan, L. Kang, and Q. \(Lu. k\)-semikernels, \(k\)-quasikernels, \(k\)-kernels in digraphs and their line digraphs. Utilitas Math., 72:267-277, 2007. · Zbl 1120.05040
[143] T. Soneoka. Super edge-connectivity of dense digraphs and graphs. Discrete Appl. Math., 37:511-523, 1992. · Zbl 0760.05050 · doi:10.1016/0166-218X(92)90155-4
[144] G. Steiner. A compact labeling scheme for series-parallel graphs. Discrete Appl. Math., 11(3):281-297, 1985. · Zbl 0596.90049 · doi:10.1016/0166-218X(85)90079-4
[145] M. Surmacs. Regular hypertournaments and arc-pancyclicity. J. Graph Theory, 84:176-190, 2017. · Zbl 1354.05062 · doi:10.1002/jgt.22019
[146] M.M. Syslo. A new solvable case of the traveling salesman problem. Math. Program., 4(1):347-348, 1973. · Zbl 0257.90025 · doi:10.1007/BF01584676
[147] W.T. Tutte. The dissection of equilateral triangles into equilateral triangles. Proc. Cambridge Philos. Soc., 44:463-482, 1948. · Zbl 0030.40903 · doi:10.1017/S030500410002449X
[148] J. Valdes. Parsing flowcharts and series-parallel graphs. Technical Report STAN-CS-78-682, Computer Science Department, Stanford University, Stanford, Ca., 1978.
[149] J. Valdes, R.E. Tarjan, and E.L. Lawler. The recognition of series parallel digraphs. SIAM J. Comput., 11(2):298-313, 1982. · Zbl 0478.68065 · doi:10.1137/0211023
[150] T. van Aardenne-Ehrenfest and N.G. de Bruijn. Circuits and trees in oriented linear graphs. Simon Stevin, 28:203-217, 1951. · Zbl 0044.38201
[151] E.A. van Doorn. Connectivity of circulant digraphs. J. Graph Theory, 10(1):9-14, 1986. · Zbl 0594.05042 · doi:10.1002/jgt.3190100103
[152] J.L. Villar. The underlying graph of a line digraph. Discrete Appl. Math., 37:525-538, 1992. · Zbl 0760.05052 · doi:10.1016/0166-218X(92)90156-5
[153] J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, Princeton, NJ, 1944. · Zbl 0063.05930
[154] C. Wang and G. Zhou. Note on the degree sequences of \(k\)-hypertournaments. Discrete Math., 308(11):2292-2296, 2008. · Zbl 1140.05044 · doi:10.1016/j.disc.2007.05.002
[155] R. Wang. A conjecture on 3-anti-quasi-transitive digraphs. Discrete Math., 322:48-52, 2014. · Zbl 1283.05118 · doi:10.1016/j.disc.2013.12.026
[156] R. Wang. Cycles in 3-anti-circulant digraphs. Australasian Journal of Combinatorics, 60(2):158-168, 2014. · Zbl 1305.05092
[157] S. Wang and R. Wang. Independent sets and non-augmentable paths in arc-locally in-semicomplete digraphs and quasi-arc-transitive digraphs. Discrete Math., 311(4):282-288, 2011. · Zbl 1222.05090 · doi:10.1016/j.disc.2010.11.009
[158] S. Wang and R. Wang. The structure of strong arc-locally in-semicomplete digraphs. Discrete Math., 309(23):6555-6562, 2009. · Zbl 1183.05032 · doi:10.1016/j.disc.2009.06.033
[159] D.B. West. Short proofs for interval digraphs. Discrete Math., 178(1-3):287-292, 1998. · Zbl 0884.05044 · doi:10.1016/S0012-365X(97)81840-7
[160] D.S. Witte. On Hamiltonian circuits in Cayley diagrams. Discrete Mathematics, 38(1):99-108, 1982. · Zbl 0474.05036 · doi:10.1016/0012-365X(82)90174-1
[161] D. Witte and J.A. Gallian. A survey: Hamiltonian cycles in Cayley graphs. Discrete Mathematics, 51(3):293-304, 1984. · Zbl 0718.05038 · doi:10.1016/0012-365X(84)90010-4
[162] W. Xiao and B. Parhami. Some mathematical properties of Cayley digraphs with applications to interconnection network design. Intern. J. Comput. Math., 82(5):521-528, 2005. · Zbl 1064.05082 · doi:10.1080/00207160512331331101
[163] C. Xu, S. Zhang, B. Ning, and B. Li. A note on the number of spanning trees of line digraphs. Discrete Math., 338(5):688-694, 2015. · Zbl 1306.05083 · doi:10.1016/j.disc.2014.12.009
[164] M.-Y. Xu. Automorphism groups and isomorphisms of Cayley digraphs. Discrete Mathematics, 182(1-3):309-319, 1998. · Zbl 0887.05025 · doi:10.1016/S0012-365X(97)00152-0
[165] D. Yang and X. Zhu. Game colouring directed graphs. Elec. J. Combinatorics, 17(R11):1, 2010. · Zbl 1215.05075
[166] J. Yang. Vertex-pancyclicity of hypertournaments. J. Graph Theory, 63(4):338-348, 2010. · Zbl 1248.05096
[167] Q.F. Yang, R.E. Burkard, E. Cela, and G.J. Woeginger. Hamiltonian cycles in circulant digraphs with two stripes. Discrete Math., 176:233-254, 1997. · Zbl 0895.05041 · doi:10.1016/S0012-365X(96)00298-1
[168] C.M.D. Zamfirescu. Transformations of digraphs viewed as intersection digraphs. In Convexity and Discrete Geometry Including Graph Theory, pages 27-35. Springer, 2016. · Zbl 1369.05095 · doi:10.1007/978-3-319-28186-5_2
[169] F. Zhang and G. Lin. On the de Bruijn-Good graphs. Acta Math. Sinica, 30(2):195-205, 1987. · Zbl 0628.05047
[170] H. Zhang, F. Zhang, and Q. Huang. On the number of spanning trees and Eulerian tours in iterated line digraphs. Discrete Appl. Math., 73(1):59-67, 1997. · Zbl 0877.05042 · doi:10.1016/S0166-218X(96)00024-8
[171] Z. Zhang, F. Liu, and J. Meng. Super-connected \(n\)-th iterated line digraphs. Oper. Res. Transactions, 9(2005):35-39, 2005.
[172] Z. Zhang and Y. Zhu. Restricted connectivity of line digraphs. J. Mathematical Study, 43:107-113, 2010. · Zbl 1224.05221
[173] G. Zhou, T. Yao, and K. Zhang. On score sequences of \(k\)-hypertournaments. European J. Combin., 21(8):993-1000, 2000. · Zbl 0966.05037 · doi:10.1006/eujc.2000.0393
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.