Font Size: a A A

2 -factors and line graphs

Posted on:2001-08-04Degree:Ph.DType:Dissertation
University:Emory UniversityCandidate:Hynds, Emily AFull Text:PDF
GTID:1460390014451796Subject:Mathematics
Abstract/Summary:
We begin by introducing a generalization of the result of Harary and Nash-Williams characterizing graphs with hamiltonian line graphs. The generalization allows us to characterize those graphs whose line graphs contain a 2-factor with exactly k (k ≥ 1) cycles. With this tool we then show that certain properties of a graph G, that were formerly shown to imply the hamiltonicity of the line graph, L(G), are actually strong enough to imply that L(G) has a 2-factor with k cycles for 1 ≤ k ≤ f(n), where n is the order of the graph G.;The family of all line graphs can be characterized in terms of forbidden subgraphs. We conclude by investigating the existence of 2-factors in other families of graphs characterized by forbidden subgraphs.
Keywords/Search Tags:Graphs
Related items