The Element Spectrum Of A Graph

Characterizations of graphs and matroids that have cycles or circuits of specified cardinality have been given by authors including Edmonds, Junior, Lemos, Murty, Reid, Young, and Wu. In particular, a matroid with circuits of a single cardinality is called a Matroid Design. We consider a generalization of this problem by assigning a weight function to the edges of a graph. We characterize when it is possible to assign a positive integer value weight function to a simple 3-connected graph G such that the graph G contains an edge that is only in cycles of two different weights. For example, as part of the main theorem we show that if this assignment is possible, then the graph G is an extension of a three-wheel, a four-wheel, a five-wheel , K3,n, a prism, a certain seven-vertex graph, or a certain eight-vertex graph, or G is obtained from the latter three graphs by attaching triads in a certain manner. The reason for assigning weights is that if each edge of such a graph is subdivided according to the weight function, then the resulting subdivided graph will contain cycles through a fixed edge of just a few different cardinalities. We consider the case where the graph has a pair of vertex-disjoint cycles and the case where the graph does not have a pair of vertex-disjoint cycles. Results from graph structure theory are used to give these characterizations.

Name thesis:degree_name

Ph.D. in Mathematics

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Year dc:date.available

2017

Author dc:creator

• Hart-Simmons, Milisha

Contributors dc:contributor

• Talmadge James Reid
• Qingying Bu
• Bing Wei

• Cycle
• Edge Weights
• Graph
• Subdivision
• Mathematics

Repository record dc:identifier

https://egrove.olemiss.edu/etd/682

OAI identifier oai:identifier

oai:egrove.olemiss.edu:etd-1681