zbMATH — the first resource for mathematics

Cycles of all lengths in arc-3-cyclic semicomplete digraphs. (English) Zbl 0880.05056
A digraph of order \(n\) is said to be arc-\(k\)-cyclic if every arc lies in a directed cycle of length \(k\). It is said to be arc-pancyclic if it is arc-\(k\)-cyclic for each \(k\in\{3,4,\ldots,n\}\). A digraph \(D\) is said to be a semicomplete digraph if for every pair of distinct vertices \(u\) and \(v\) in \(D\), at least one of \((u,v)\) or \((v,u)\) is an arc of \(D\). The authors study arc-\(k\)-cyclicity and arc-pancyclicity of semicomplete digraphs.

05C38 Paths and cycles
05C20 Directed graphs (digraphs), tournaments
Full Text: DOI
[1] Alspach, B., Cycles of each length in regular tournaments, Canad. math. bull., 10, 283-286, (1967) · Zbl 0148.43602
[2] Alspach, B.; Reid, K.B.; Roselle, D.P., Bypasses in asymmetric digraphs, J. combin. theory ser. B, 17, 11-18, (1974) · Zbl 0268.05109
[3] Bang-Jensen, J., Locally semicomplete digraphs: a generalization of tournaments, J. graph theory, 14, 371-390, (1990) · Zbl 0703.05026
[4] Bang-Jensen, J., On the structure of locally semicompete digraphs, Discrete math., 100, 243-265, (1992) · Zbl 0759.05040
[5] J. Bang-Jensen, Digraphs with the path merging property, preprint. · Zbl 0832.05047
[6] Bang-Jensen, J.; Manoussakis, Y.; Thomassen, C., A polynomial algorithm for Hamiltonian-connectedness in semicomplete digraphs, J. algorithm, 13, 114-127, (1992) · Zbl 0749.68057
[7] Chv√°tal, V.; Kotzig, A., On 3-cycles in regular tournaments, ()
[8] Douglas, R.J., Tournaments that admit exactly one Hamiltonian circuit, (), 716-730, (3) · Zbl 0207.23004
[9] Gallai, T., On directed paths and circuits, (), 115-118 · Zbl 0159.54403
[10] Jakobsen, O.S., Cycles and paths in tournaments, ()
[11] Moon, J.W., Topics on tournaments, (1969), Holt, Reinhard and Winston New York · Zbl 0184.27704
[12] Reid, K.B., On sets of arcs containing no cycles in tournaments, Canad. math. bull., 12, 261-264, (1969) · Zbl 0181.51901
[13] Reid, K.B., 1-cycles in n-tournaments having no k-cycles, (), 473-482
[14] Reid, K.B.; Beineke, L.W., Tournaments, (), 169-204 · Zbl 0434.05037
[15] Thomassen, C., Hamiltonian-connected tournaments, J. combin. theory ser. B, 28, 142-163, (1980) · Zbl 0435.05026
[16] Tian, F.; Wu, Z.S.; Zhang, C.Q., Cycles of each length in tournaments, J. combin. theory ser. B, 33, 245-255, (1982) · Zbl 0495.05028
[17] Shao, P.; Zhang, C.Q., A note about the arc-pancyclic property, Kexue tongbao, 18, 1100-1103, (1982)
[18] Wu, Z.S.; Zhang, K.M.; Zhou, Y., A necessary and sufficient condition for arc-pancyclicity of tournaments, Sci. sinica, 8, 915-919, (1981)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.