First Advisor

John Caughman

Date of Award

Spring 2021

Document Type

Thesis

Degree Name

Bachelor of Science (B.S.) in Mathematics and University Honors

Department

Mathematics and Statistics

Language

English

Subjects

Spanning trees (Graph theory)

DOI

10.15760/honors.1151

Abstract

Spanning trees are typically used to solve least path problems for finding the minimal spanning tree of a graph. Given a number t ≥ 3 what is the least number n = α(t) such that there exists a graph on n vertices having precisely t spanning trees? Specifically, how will the factoring of t with the use of cycles connected by one vertex affect α(t)? Lower and upper bounds of α(t) are graphed by using properties of cycles and complete graphs. The upper bound of α(t) is then improved by constructing a graph of connected cycles {Cp1, C­p2, Cp3, … , Cpn} where p1, p2, p3 … pn belong to the prime factorization of t. The bounds of α(t) are significantly improved.

Rights

In Copyright. URI: http://rightsstatements.org/vocab/InC/1.0/ This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).

Persistent Identifier

https://archives.pdx.edu/ds/psu/36145

Download

Share

COinS