Back to search

Rochester Institute of Technology

Unique Transmissions of Cycle Graphs With Pendant Paths

Abstract

dc:description.abstract

We 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 × 3

Identifiers

dc:identifier.*
Repository record dc:identifier
https://repository.rit.edu/theses/12652

Chain of custody

source
Harvested from
Rochester Institute of Technology
Base URL
repository.rit.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Li, Alek. Unique Transmissions of Cycle Graphs With Pendant Paths. Thesis thesis, https://repository.rit.edu/theses/12652