Circuits of Each Length in Tournaments

被引:0
作者
Yue-Li Wang
Jun-Lin Guo
Cheng-Huang Hung
Hung-Chang Chan
机构
[1] National Taiwan University of Science and Technology,Department of Information Management
[2] Yuanpei University,Department of Computer Science and Information Engineering
来源
Graphs and Combinatorics | 2014年 / 30卷
关键词
Tournaments; Regular tournaments; Almost regular tournaments; Multipartite tournaments; Pancyclic; Pancircuitous;
D O I
暂无
中图分类号
学科分类号
摘要
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 v1, a1, v2, a2, v3, . . . , vn-1, an-1, vn in which vertex vn = v1, arc ai = vivi+1 for i = 1, 2, . . . , n−1, and ai≠aj\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${a_i \neq a_j}$$\end{document} if i≠j\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${i \neq j}$$\end{document}. In this paper, we shall show that every tournament Tn in a subclass of tournaments has a circuit of each length k for 3⩽k⩽θ(Tn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${3 \leqslant k \leqslant \theta(T_n)}$$\end{document}, where θ(Tn)=n(n-1)2-3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\theta(T_n) = \frac{n(n-1)}{2}-3}$$\end{document} if n is odd and θ(Tn)=n(n-1)2-n2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\theta(T_n) = \frac{n(n-1)}{2}-\frac{n}{2}}$$\end{document} otherwise. Note that a graph having θ(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.
引用
收藏
页码:1271 / 1282
页数:11
相关论文
共 10 条
  • [1] Alspach B.(1967)Cycles of each length in regular tournaments Can. Math. Bull. 10 283-286
  • [2] Bondy J.A.(1971)Pancyclic Graphs I J. Comb. Theory Ser. B 11 80-84
  • [3] Bondy J.A.(1976)Disconnected orientation and a conjecture of Las Vergnas J. London Math. Soc. 14 277-282
  • [4] Hall P.(1935)On representation of subsets J. London Math. Soc. 10 26-30
  • [5] Harary F.(1966)The theory of round robin tournaments Am. Math. Mon. 73 231-246
  • [6] Moser L.(1916)Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre Mathematische Annalen 77 453-465
  • [7] Kőnig D.(1966)On subtournaments of a tournament Can. Math. Bull. 9 297-301
  • [8] Moon J.W.(2002)Cycles in multipartite tournaments: results and problems Discrete Math. 245 19-53
  • [9] Volkmann L.(1999)Diregular J. Graph Theory 32 137-152
  • [10] Yeo A.(undefined)-partite tournaments are vertex-pancyclic when undefined undefined undefined-undefined