Longest cycles in almost regular 3-partite tournaments
详细信息 查看全文
- 作者：Lutz Volkmann
- 关键词：Multipartite tournaments ; Almost regular multipartite tournaments ; 3-Partite tournaments ; Longest cycle
- 刊名：Discrete Mathematics
- 出版年：2006
- 出版时间：28 November 2006
- 年：2006
- 卷：306
- 期：22
- 页码：2931-2942
- 全文大小：229 K
文摘
If black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-D&_mathId=mml1&_user=10&_cdi=5632&_rdoc=12&_handle=V-WA-A-W-WU-MsSWYVW-UUW-U-AAZCBUUZWY-AAZWYYAVWY-VBWYVZYC-WU-U&_acct=C000050221&_version=1&_userid=10&md5=9e0d5ca78347bd95b7fa61949c18b885"" title=""Click to view the MathML source"">D is a digraph, then we denote by black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-D&_mathId=mml2&_user=10&_cdi=5632&_rdoc=12&_handle=V-WA-A-W-WU-MsSWYVW-UUW-U-AAZCBUUZWY-AAZWYYAVWY-VBWYVZYC-WU-U&_acct=C000050221&_version=1&_userid=10&md5=885bd893e8ecd2fb43095ee934fd7905"" title=""Click to view the MathML source"">V(D) its vertex set. A multipartite or black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-D&_mathId=mml3&_user=10&_cdi=5632&_rdoc=12&_handle=V-WA-A-W-WU-MsSWYVW-UUW-U-AAZCBUUZWY-AAZWYYAVWY-VBWYVZYC-WU-U&_acct=C000050221&_version=1&_userid=10&md5=0f346ddd82ab337773b7ff9eb6055049"" title=""Click to view the MathML source"">c-partite tournament is an orientation of a complete black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-D&_mathId=mml4&_user=10&_cdi=5632&_rdoc=12&_handle=V-WA-A-W-WU-MsSWYVW-UUW-U-AAZCBUUZWY-AAZWYYAVWY-VBWYVZYC-WU-U&_acct=C000050221&_version=1&_userid=10&md5=8a1b0ba11af1f33176f6968c64ddb05e"" title=""Click to view the MathML source"">c-partite graph. The global irregularity of a digraph black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-D&_mathId=mml5&_user=10&_cdi=5632&_rdoc=12&_handle=V-WA-A-W-WU-MsSWYVW-UUW-U-AAZCBUUZWY-AAZWYYAVWY-VBWYVZYC-WU-U&_acct=C000050221&_version=1&_userid=10&md5=c240fb104c036faf1437cbe7e2b8806a"" title=""Click to view the MathML source"">D is defined by
If black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-D&_mathId=mml7&_user=10&_cdi=5632&_rdoc=12&_handle=V-WA-A-W-WU-MsSWYVW-UUW-U-AAZCBUUZWY-AAZWYYAVWY-VBWYVZYC-WU-U&_acct=C000050221&_version=1&_userid=10&md5=0b2708c140f5596e1f9dff8c99d9257d"" title=""Click to view the MathML source"">ig(D)=0, then black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-D&_mathId=mml8&_user=10&_cdi=5632&_rdoc=12&_handle=V-WA-A-W-WU-MsSWYVW-UUW-U-AAZCBUUZWY-AAZWYYAVWY-VBWYVZYC-WU-U&_acct=C000050221&_version=1&_userid=10&md5=de012e942253f193e9776b00cef9f641"" title=""Click to view the MathML source"">D is regular, and if black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-D&_mathId=mml9&_user=10&_cdi=5632&_rdoc=12&_handle=V-WA-A-W-WU-MsSWYVW-UUW-U-AAZCBUUZWY-AAZWYYAVWY-VBWYVZYC-WU-U&_acct=C000050221&_version=1&_userid=10&md5=f1f17146ef0d6317272c3a48176fd8ac"" title=""Click to view the MathML source"">ig(D)1, then black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-D&_mathId=mml10&_user=10&_cdi=5632&_rdoc=12&_handle=V-WA-A-W-WU-MsSWYVW-UUW-U-AAZCBUUZWY-AAZWYYAVWY-VBWYVZYC-WU-U&_acct=C000050221&_version=1&_userid=10&md5=6efb24a8fe42ce5f13d9f25a6e7b7ca7"" title=""Click to view the MathML source"">D is called almost regular. In 1997, Yeo has shown that each regular multipartite tournament is Hamiltonian. This remains valid for almost all almost regular black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-D&_mathId=mml11&_user=10&_cdi=5632&_rdoc=12&_handle=V-WA-A-W-WU-MsSWYVW-UUW-U-AAZCBUUZWY-AAZWYYAVWY-VBWYVZYC-WU-U&_acct=C000050221&_version=1&_userid=10&md5=e4548d82c1891208ffd010641d728ee1"" title=""Click to view the MathML source"">c-partite tournaments with black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-D&_mathId=mml12&_user=10&_cdi=5632&_rdoc=12&_handle=V-WA-A-W-WU-MsSWYVW-UUW-U-AAZCBUUZWY-AAZWYYAVWY-VBWYVZYC-WU-U&_acct=C000050221&_version=1&_userid=10&md5=87e5f0281cd37e2e8e610b73b108b795"" title=""Click to view the MathML source"">c≥4. However, there exist infinite families of almost regular 3-partite tournaments without any Hamiltonian cycle. In this paper we will prove that every vertex of an almost regular 3-partite tournament black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-D&_mathId=mml13&_user=10&_cdi=5632&_rdoc=12&_handle=V-WA-A-W-WU-MsSWYVW-UUW-U-AAZCBUUZWY-AAZWYYAVWY-VBWYVZYC-WU-U&_acct=C000050221&_version=1&_userid=10&md5=9f5447d6757dbccb934567cf00a07bd2"" title=""Click to view the MathML source"">D is contained in a directed cycle of length at least black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-4KFMMFW-D&_mathId=mml14&_user=10&_cdi=5632&_rdoc=12&_handle=V-WA-A-W-WU-MsSWYVW-UUW-U-AAZCBUUZWY-AAZWYYAVWY-VBWYVZYC-WU-U&_acct=C000050221&_version=1&_userid=10&md5=21628bfe9b17d1316d6a2238b888f68e"" title=""Click to view the MathML source"">|V(D)|-2. Examples will show that this result is best possible.