×

Circuits of each length in tournaments. (English) Zbl 1298.05150

Summary: A tournament is a directed graph whose underlying graph is a complete graph. A circuit is an alternating sequence of vertices and arcs of the form \(v_1,a_1,v_2,a_2,v_3,\dots,v_{n-1},a_{n-1},v_n\) in which vertex \(v_n=v_1\), \(\mathrm{arc } a_i=v_iv_{i+1}\) for \(i=1,2,\dots,n-1\), and \(a_i\neq a_j\) if \(i\neq j\). In this paper, we shall show that every tournament \(T_n\) in a subclass of tournaments has a circuit of each length \(k\) for \(3\leqslant k\leqslant\theta(T_n)\), where \(\theta(T_n)=\frac{n(n-1)}{2}-3\) if \(n\) is odd and \(\theta(T_n)=\frac{n(n-1)}{2}-\frac{n}{2}\) otherwise. Note that a graph having \(\theta(G)>n\) can be used as a host graph on embedding cycles with lengths larger than \(n\) to it if congestions are allowed only on vertices.

MSC:

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

References:

[1] Alspach B.: Cycles of each length in regular tournaments. Can. Math. Bull. 10, 283-286 (1967) · Zbl 0148.43602 · doi:10.4153/CMB-1967-028-6
[2] Bondy J.A.: Pancyclic Graphs I. J. Comb. Theory Ser. B 11, 80-84 (1971) · Zbl 0183.52301 · doi:10.1016/0095-8956(71)90016-5
[3] Bondy J.A.: Disconnected orientation and a conjecture of Las Vergnas. J. London Math. Soc. 14, 277-282 (1976) · Zbl 0344.05124 · doi:10.1112/jlms/s2-14.2.277
[4] Hall P.: On representation of subsets. J. London Math. Soc. 10, 26-30 (1935) · Zbl 0010.34503
[5] Harary F., Moser L.: The theory of round robin tournaments. Am. Math. Mon. 73, 231-246 (1966) · Zbl 0142.41602 · doi:10.2307/2315334
[6] Harary, F.: Graph Theory. Addison-Wesley, Reading (1969) · Zbl 0182.57702
[7] Kőnig D.: Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Mathematische Annalen 77, 453-465 (1916) · JFM 46.0146.03 · doi:10.1007/BF01456961
[8] Moon J.W.: On subtournaments of a tournament. Can. Math. Bull. 9, 297-301 (1966) · Zbl 0141.41204 · doi:10.4153/CMB-1966-038-7
[9] Volkmann L.: Cycles in multipartite tournaments: results and problems. Discrete Math. 245, 19-53 (2002) · Zbl 0996.05063 · doi:10.1016/S0012-365X(01)00419-8
[10] Yeo A.: Diregular c-partite tournaments are vertex-pancyclic when \[{c \geqslant 5}\] c⩾5. J. Graph Theory 32, 137-152 (1999) · Zbl 0931.05037 · doi:10.1002/(SICI)1097-0118(199910)32:2<137::AID-JGT4>3.0.CO;2-I
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.