Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 4 of 4
Full-Text Articles in Physical Sciences and Mathematics
Graceful Colorings And Connection In Graphs, Alexis D. Byers
Graceful Colorings And Connection In Graphs, Alexis D. Byers
Dissertations
For a graph G of size m, a graceful labeling of G is an injective function f : V (G) → {0, 1, . . . , m} that gives rise to a bijective function f 1 : E(G) → {1, 2, . . . , m} defined by f 1(uv) = |f (u) − f (v)|. A graph is graceful if it has a graceful labeling. Over the years, a number of variations of graceful …
The Graphs And Matroids Whose Only Odd Circuits Are Small, Kristen Nicole Wetzler
The Graphs And Matroids Whose Only Odd Circuits Are Small, Kristen Nicole Wetzler
LSU Doctoral Dissertations
This thesis is motivated by a graph-theoretical result of Maffray, which states that a 2-connected graph with no odd cycles exceeding length 3 is bipartite, is isomorphic to K_4, or is a collection of triangles glued together along a common edge. We first prove that a connected simple binary matroid M has no odd circuits other than triangles if and only if M is affine, M is M(K_4) or F_7, or M is the cycle matroid of a graph consisting of a collection of triangles glued together along a common edge. This result implies that a 2-connected loopless graph G …
Networks, (K)Nots, Nucleotides, And Nanostructures, Ada Morse
Networks, (K)Nots, Nucleotides, And Nanostructures, Ada Morse
Graduate College Dissertations and Theses
Designing self-assembling DNA nanostructures often requires the identification of a route for a scaffolding strand of DNA through the target structure. When the target structure is modeled as a graph, these scaffolding routes correspond to Eulerian circuits subject to turning restrictions imposed by physical constraints on the strands of DNA. Existence of such Eulerian circuits is an NP-hard problem, which can be approached by adapting solutions to a version of the Traveling Salesperson Problem. However, the author and collaborators have demonstrated that even Eulerian circuits obeying these turning restrictions are not necessarily feasible as scaffolding routes by giving examples of …
Quick Trips: On The Oriented Diameter Of Graphs, Garner Paul Cochran
Quick Trips: On The Oriented Diameter Of Graphs, Garner Paul Cochran
Theses and Dissertations
In this dissertation, I will discuss two results on the oriented diameter of graphs with certain properties. In the first problem, I studied the oriented diameter of a graph G. Erdos et al. in 1989 showed that for any graph with |V | = n and δ(G) = δ the maximum the diameter could possibly be was 3 n/ δ+1. I considered whether there exists an orientation on a given graph with |G| = n and δ(G) = δ that has a small diameter. Bau and Dankelmann (2015) showed that there is an orientation of diameter 11 n/ δ+1 + …