应用数学学报(英文版)
HOME | ABOUT JOURNAL | EDITORIAL BOARD | FOR AUTHORS | SUBSCRIPTIONS | ADVERTISEMENT | CONTACT US
 
Acta Mathematicae Applicatae
Sinica, Chinese Series
 
   
   
Adv Search »  
Acta Mathematicae Applicatae Sinica, English Series 2012, Vol. 28 Issue (1) :201-208    DOI: 10.1007/s10255-012-0135-9
ARTICLES Current Issue | Next Issue | Archive | Adv Search << | >>
Componentwise Complementary Cycles in Multipartite Tournaments
Zhi-hong HE1, Guo-jun LI2, Xue-qin ZHOU1
1. School of Mathematics and Information Science, Yantai University, Yantai 264005, China;
2. School of Mathematics and System Sciences, Shandong University, Jinan 250100, China
Download: PDF (1KB)   HTML (1KB)   Export: BibTeX or EndNote (RIS)      Supporting Info
Abstract The problem of complementary cycles in tournaments and bipartite tournaments was completely solved. However, the problem of complementary cycles in semicomplete n-partite digraphs with n ≥ 3 is still open. Based on the definition of componentwise complementary cycles, we get the following result. Let D be a 2-strong n-partite (n ≥ 6) tournament that is not a tournament. Let C be a 3-cycle of D and D \ V (C) be nonstrong. For the unique acyclic sequence D1,D2, … ,Dα of D\V (C), where α ≥ 2, let Dc = {Di|Di contains cycles, i = 1, 2, … , α}, Dc = {D1,D2, … ,Dα} \ Dc. If Dc ≠ Ø, then D contains a pair of componentwise complementary cycles.  
Service
Email this article
Add to my bookshelf
Add to citation manager
Email Alert
RSS
Articles by authors
Keywordscomplementary cycles   componentwise complementary cycles   multipartite tournaments     
Abstract: The problem of complementary cycles in tournaments and bipartite tournaments was completely solved. However, the problem of complementary cycles in semicomplete n-partite digraphs with n ≥ 3 is still open. Based on the definition of componentwise complementary cycles, we get the following result. Let D be a 2-strong n-partite (n ≥ 6) tournament that is not a tournament. Let C be a 3-cycle of D and D \ V (C) be nonstrong. For the unique acyclic sequence D1,D2, … ,Dα of D\V (C), where α ≥ 2, let Dc = {Di|Di contains cycles, i = 1, 2, … , α}, Dc = {D1,D2, … ,Dα} \ Dc. If Dc ≠ Ø, then D contains a pair of componentwise complementary cycles.  
Keywordscomplementary cycles,   componentwise complementary cycles,   multipartite tournaments     
Received: 2006-05-24;
Fund:

Supported by the National Natural Science Foundation of China (No. 10801114) and the Nature Science Foundation of Shandong Province, China (No. ZR2011AL019; No. ZR2011AM005).

Corresponding Authors: Zhi-hong HE     Email: zhihhe@126.com
Cite this article:   
.Componentwise Complementary Cycles in Multipartite Tournaments[J]  Acta Mathematicae Applicatae Sinica, English Serie, 2012,V28(1): 201-208
URL:  
http://www.applmath.com.cn/jweb_yysxxb_en/EN/10.1007/s10255-012-0135-9      或     http://www.applmath.com.cn/jweb_yysxxb_en/EN/Y2012/V28/I1/201
 
[1] Bondy, J.A. Diconnected orientation and a conjecture of Las Vergnas. J. London Math. Soc., 14: 277-282 (1976)
[2] Guo, Y., Pinkernell, A., Volkmann, L. On cycles through a given vertex in multipartite tournaments. Discrete Math., 164: 165-170 (1997)
[3] Gutin, G. On cycles in multipartite tournaments. J. Combin. Theory Ser.B., 58(2): 319-321 (1993)
[4] J?rgen, B.-J., Gregory, Z.G. Digraphs Theory Algorithms and Applications. Springer-Verlag, London Limited, 2001
[5] Reid, K.B. Two complementary circuits in two-connected tournaments. Ann. Discrete Math., 27: 321-334 (1985)
[6] Song, Z.M. Complementary cycles of all lengths in tournaments. J. Combin. Theory Ser. B., 57(1): 18-25 (1993)
[7] Tewes, M., Volkmann, L. Vertex deletion and cycles in multipartite tournaments. Discrete Math., 197: 769-779 (1999)
[8] Volkmann, L. Cycles in multipartite tournaments: results and problems. Discrete Math., 245: 19-53 (2002)
没有找到本文相关文献
Copyright 2010 by Acta Mathematicae Applicatae Sinica, English Serie