首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Even cycle creating paths
Authors:Daniel Soltész
Institution:MTA, Rényi Institute, Budapest, Hungary
Abstract:We say that two graphs H 1 , H 2 on the same vertex set are G-creating if the union of the two graphs contains G as a subgraph. Let H ( n , k ) be the maximum number of pairwise C k -creating Hamiltonian paths of the complete graph K n . The behavior of H ( n , 2 k + 1 ) is much better understood than the behavior of H ( n , 2 k ) , the former is an exponential function of n whereas the latter is larger than exponential, for every fixed k. We study H ( n , k ) for fixed k and n tending to infinity. The only nontrivial upper bound on H ( n , 2 k ) was proved by Cohen, Fachini, and Körner in the case of k = 2 : n ( 1 / 2 ) n o ( n ) H ( n , 4 ) n ( 1 1 / 4 ) n o ( n ) . In this paper, we generalize their method to prove that for every k 2, n ( 1 / k ) n o ( n ) H ( n , 2 k ) n ( 1 2 / ( 3 k 2 2 k ) ) n o ( n ) and a similar, slightly better upper bound holds when k is odd. Our proof uses constructions of bipartite, regular, C 2 k -free graphs with many edges given in papers by Reiman, Benson, Lazebnik, Ustimenko, and Woldar.
Keywords:even cycle  Hamiltonian path  permutations  union
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号