Even cycle creating paths

Soltész, Dániel (2020) Even cycle creating paths. JOURNAL OF GRAPH THEORY, 93 (3). pp. 350-362. ISSN 0364-9024

Preview

Text 1801.00737.pdf Download (182kB) | Preview

Abstract

We say that two graphs H1, H2 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 Ck-creating Hamiltonian paths of the complete graph Kn. The behavior of H (n, 2k + 1) is much better understood than the behavior of H (n, 2k), 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, 2k) was proved by Cohen, Fachini, and Körner in the case of k = 2: : (Formula presented.) In this paper, we generalize their method to prove that for every k ≥ 2, (Formula presented.) and a similar, slightly better upper bound holds when k is odd. Our proof uses constructions of bipartite, regular, C2k-free graphs with many edges given in papers by Reiman, Benson, Lazebnik, Ustimenko, and Woldar. © 2019 Wiley Periodicals, Inc.

Actions (login required)

Edit Item