Determining the Pebbling Number for Endpoint Root Vertices of Generalized Theta Graphs

Overview

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.

Competition history

• ISEF 2022 Mathematics · Entry MATH038 · Atlanta, Georgia, United States

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.