Euler Tours of Maximum Girth in K_(2n+1) and K_(2n,2n)

摘要

Given an eulerian graph G and an Euler tour T of G, the girth of T, denoted by g(T), is the minimum integer k such that some segment of k + 1 consecutive vertices of T is a cycle of length k in G. Let g~E(G) = max g(T) where the maximum is taken over all Euler tours of G. We prove that g~E(K_(2n,2n)) = 4n-4 and 2n-3 ≤ g~E(K_(2n+1)) ≤ 2n-1 for any n ≥ 2. We also show that g~E(K_7) = 4. We use these results to prove the following: 1) The graph K_(2n,2n) can be decomposed into edge disjoint paths of length k if and only if k ≤ 4n-1 and the number of edges in K_(2n,2n) is divisible by k. 2) The graph K_(2n+1) can be decomposed into edge disjoint paths of length k if and only if k ≤ 2n and the number edges in K_(2n+1) is divisible by k.