Rochester Institute of Technology
Unique Transmissions of Cycle Graphs With Pendant Paths
Abstract
dc:description.abstractWe consider a variant of the well-known Traveling Salesman Problem where the salesman must return to the starting point after each delivery. Ramanathan et al. asked whether different starting locations in a network yield the same total travel distance. The transmission of a vertex $u$ is defined to be T(u)=\sum\limitsv\in V(G)d(u,v) where $d(u,v)$ is the number of edges in a shortest path between $u$ and $v$. For specialized families of graphs, we investigate necessary and sufficient conditions for a graph to have distinct transmissions. Graph asymmetry is a necessary condition for unique transmissions. However, it is not sufficient, as asymmetric graphs may still contain vertices with identical transmission values. Motivated by past constructions, we introduce a family of asymmetric graphs that possess unique transmissions and analyze how this property behaves under structural modifications. We call this family "noodle arm graphs." We further examine connections between unique transmissions and the Wiener Index, which can be expressed as half the sum of all vertex transmissions. Finally, we extend our constructions to a generalization of cycle graphs with attached pendant paths, within which the noodle arm graphs form a subfamily, providing a broader framework for analyzing transmission uniqueness in unicyclic graphs.
Degree
thesis:*- Name thesis:degree_name
- Applied and Computational Mathematics (MS)
- Level thesis:degree_level
- Thesis
- Discipline thesis:degree_discipline
- Mathematics and Statistics, School of
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Li, Alek
- Contributors dc:contributor
-
- Darren Narayan
Subjects
dc:subject × 3Identifiers
dc:identifier.*- Repository record dc:identifier
- https://repository.rit.edu/theses/12652