Edge Closures of Hamiltonian Type

摘要

Let K_n be the complete graph of order n. For each integer θ > 0, there is a closure defined on the edges of K_n. Specifically, for any set S of edges of K_n an edge uv of K_n is θ-dependent on S iff deg_s(u) - deg_s(v) ≥ θ. S is θ-closed provided S contains all edges that are θ-dependent on S. The now classical case θ = n was studied by Bondy and Chvatal who proved that if the n-closure of a graph is Hamiltonian, then the original graph must be Hamiltonian. In this paper, we will investigate the notions of independence and span for θ-closure, determining the maximum size of θ-independent sets of edges. In particular, we completely characterize the degree sequence of maximum θ-independent sets when 9 is odd.