Booth Id:
MATH038
Category:
Mathematics
Year:
2022
Finalist Names:
Liu, Kevin (School: High Technology High School)
Abstract:
Graph theory is the study of relationships between objects. Whether those objects are city blocks or web pages, graph theory can provide significant insight into optimization. A specific area of graph theory, graph pebbling is a mathematical game dealing with the movement of pebbles. Given any distribution of pebbles on a graph G, the pebbling number is the minimum number of pebbles such that at least one pebble is achieved at a root vertex through a series of pebbling moves (removing two pebbles from a vertex and adding one to an adjacent vertex). Due to the payoffs of pebbling moves, graph pebbling will help in understanding the nature of information loss between computers on a network. Past results on the pebbling number of an n-vertex path were rederived by representing the graph pebbling game through an invariant function. Using this invariant, a novel method was introduced on computing the pebbling number of theta-graphs. Through smoothing inequalities and generalizing results on a regular theta-graph, the pebbling number was evaluated for generalized theta-graphs with same path-lengths.