Even cycle creating paths |
| |
Authors: | Daniel Soltész |
| |
Institution: | MTA, Rényi Institute, Budapest, Hungary |
| |
Abstract: | We say that two graphs on the same vertex set are -creating if the union of the two graphs contains as a subgraph. Let be the maximum number of pairwise -creating Hamiltonian paths of the complete graph . The behavior of is much better understood than the behavior of , the former is an exponential function of whereas the latter is larger than exponential, for every fixed . We study for fixed and tending to infinity. The only nontrivial upper bound on was proved by Cohen, Fachini, and Körner in the case of : In this paper, we generalize their method to prove that for every , and a similar, slightly better upper bound holds when is odd. Our proof uses constructions of bipartite, regular, -free graphs with many edges given in papers by Reiman, Benson, Lazebnik, Ustimenko, and Woldar. |
| |
Keywords: | even cycle Hamiltonian path permutations union |
|
|