Back to search

University of South Florida

Hamiltonian Sets of Polygonal Paths in 4-Valent Spatial Graphs

Abstract

dc:description

Spatial graphs with 4–valent rigid vertices and two single valent endpoints, called assembly graphs, model DNA recombination processes that appear in certain species of ciliates. Recombined genes are modeled by certain types of paths in an assembly graph that make a ”oper pendicular ” turn at each 4–valent vertex of the graph called polygonal paths. The assembly number of an assembly graph is the minimum number of polygonal paths that visit each vertex exactly once. In particular, an assembly graph is called realizable if the graph has a Hamiltonian polygonal path. An assembly graph ɣ^ obtained from a given assembly graph γ by substituting every edge of γ by a loop is called a loop-saturated graph. We show that a loop- saturated graph ɣ^ has an assembly number a unit larger than the size of ɣ. For a positive integer n, the minimum realization number for n is defined by Rmin(n) = min{|ɣ| : An(ɣ) = n}, where |γ| is the number of 4-valent vertices in γ. A graph γ that gives the minimum for Rmin(n) is called a realization of assembly number n. We denote by Rmin(n) the set of realization graphs for n. We prove that loop-saturated graphs with assembly number nachieve the upper bound of Rmin(n). If a simple assembly graph γ has no loops then γ is not in Rmin(n). With the introduction of left –additive, right–additive and middle additive operations, we study the properties of assembly graphs when composing increases their assembly number. We also introduce the notion of height sequence, a non-increasing sequence of positive integers, that counts the number of 4-valent vertices which the polygonal paths contain. We show properties of a height sequence for loop–saturated graphs. Assembly graphs are represented by double-occurrence words called assembly words. An assembly word is strongly-irreducible if it does not contain a proper subword that is also a double-occurrence word. We prove that, for every positive integer n there is a strongly-irreducible assembly graph with assembly number n, and if a simple assembly graph is strongly-irreducible, then γ ̸∈ Rmin(n).

Degree

thesis:*
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Mathematics and Statistics
Grantor
University of South Florida
Year dc:date
2012

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Muche, Tilahun Abay
Contributors dc:contributor
  • Natasha Jonoska

Subjects

dc:subject × 8

Rights

Language dc:language
EN-US

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.usf.edu/etd/4177

Chain of custody

source
Harvested from
University of South Florida
Base URL
digitalcommons.usf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Muche, Tilahun Abay. Hamiltonian Sets of Polygonal Paths in 4-Valent Spatial Graphs. Dissertation thesis, University of South Florida, 2012. https://digitalcommons.usf.edu/etd/4177