Date of Publication
2025
Document Type
Bachelor's Thesis
Degree Name
Bachelor of Science in Mathematics with Specialization in Computer Applications
Subject Categories
Mathematics
College
College of Science
Department/Unit
Mathematics and Statistics Department
Thesis Advisor
Francis Joseph H. Campeña
Defense Panel Chair
Severino V. Gervacio
Defense Panel Member
Luisette C. Candelaria
Abstract (English)
This study explores the edge contraction spectrum of a graph, a directed graph whose nodes represent all non-isomorphic graphs obtainable from an original graph G through sequences of edge contractions, and whose edges represent individual contraction steps. The analysis focuses on specific graph families: path, cycle, star, complete, complete bipartite, and fan graphs. For each family, the spectrum is computed and analyzed to quantify the number of distinct contraction paths and to understand the structural transformations involved. The results highlight patterns in contraction behavior, particularly the role of symmetry in producing linear or branching spectra. The study is restricted to simple, undirected, and unweighted graphs, excluding operations such as vertex or edge deletions. This framework offers insight into the combinatorial complexity of contraction processes across diverse graph structures.
Abstract Format
html
Abstract (Filipino)
Sinisiyasat ng pag-aaral na ito ang edge contraction spectrum ng isang graph, isang directed graph kung saan ang mga node ay kumakatawan sa lahat ng non-isomorphic graphs na maaaring makuha mula sa orihinal na graph G sa pamamagitan ng sunod-sunod na edge contractions, at ang mga edge ay kumakatawan sa bawat indibidwal na hakbang ng contraction. Nakatuon ang pagsusuri sa mga partikular na pamilya ng graph: path, cycle, star, complete, complete bipartite, at fan graphs. Para sa bawat pamilya, inaaalam at sinuri ang spectrum upang mabilang ang dami ng magkakaibang contraction paths at upang maunawaan ang mga kaakibat na pagbabagong estruktural. Binibigyang-diin ng mga resulta ang mga pattern sa gawi ng contraction, lalo na ang papel ng symmetry sa pagbuo ng mga linear o branching spectra. Ang pag-aaral ay limitado sa mga simple, undirected, at unweighted graphs. Isa sa sinusuri ng pagaaral na ito ng kombinatoryal na kumplikasyon ng mga proseso ng contraction sa iba’t ibang estruktura ng graph.
Abstract Format
html
Language
English
Format
Electronic
Keywords
Graph theory
Recommended Citation
Vilbar, J. S. (2025). On the edge contraction spectrum of some families of graphs. Retrieved from https://animorepository.dlsu.edu.ph/etdb_math/75
Upload Full Text
wf_yes
Embargo Period
12-13-2028
