   Mathematics

# Proposed Projects

## Project 21.01: Network Reliability Measures Based on Size and Order

Assume a network can be represented by a graph G with vertex set V and edge set E. The network is operational as long as the graph maintains some property P. The network reliability measures how quickly a network loses property P. Often vertices fail, or edges fail, or both. Often we use this information backwards; meaning we want to construct a network with maximum reliability relative to property P, however we are restricted by the number of vertices and edges in the graph. Given n vertices, m edges, and property P, what graphs will produce the most (and least) reliable networks? The aid of computers allows us to experiment with small values of n and m in order to make conjectures.

## Project 21.02: Random Race

Alice and Bob take turns to collect chips in the following manner.  In each turn, Alice tosses a fair coin, which decides whether she collects a or b chips, where a and b are positive integers.  If Alice collects a chips, then Bob collects b chips, and vice versa.  Alice wins if her total number of chips is divisible by n and Bob wins if his total number of chips is divisible by m.  In this project, we study the winning probability of each player.

A harshad number is a number that is divisible by its digit sum.  For example, 2412 is a harshad number since 2+4+1+2=9 and 9 divides 2412.  In this project we study the existence of hashad numbers in various interesting sequences of positive integers

## Project 21.04:Induced $H$-Saturated Graphs

An \textit{induced $H$-saturated graph} $G$ is a non-complete graph that does not contain $H$ as an induced subgraph, but when any missing edge $e$ is added to $G$, the resulting graph $G \cup e$ does indeed contain $H$ as an induced subgraph.  It has been shown that there exists an induced $K_{1,3}$-saturated graph on $n$ vertices for $n\geq 12$. The proof of this result involves finding a nice'' construction on 12 vertices and then creatively inserting edges/vertices into the construction so that $n$ can grow arbitrarily large.  The goal of this project would be to study this construction and to determine if it can be extended to general star graphs, $K_{1,s}$ where $s\geq 4$.  Another goal would be to ask similar questions for other graph families.  For example, is it possible to find a nice'' construction that proves the existence of induced kite-saturated graphs of arbitrary size or perhaps of induced wheel-saturated graphs of arbitrary size?

## Project 21.05: Assignment Graphs

Graph pebbling is a mathematical game played on a simple graph (i.e., an undirected graph with no loops or multiple edges). A pebbling move consists of removing two pebbles from a vertex and adding one pebble to an adjacent vertex. A pebble assignment (S_G) on a finite, simple graph G is a distribution of a finite number of pebbles on the vertices of G. An assignment graph [S_G] is a Hasse diagram whose nodes correspond to all assignments that can be reached from (S_G) by applying a sequence of pebbling moves. Edges of [S_G] adjoin any two assignment nodes where one can be reached from the other via a single pebbling move. Assignment graphs are a relatively new concept introduced into the literature within the last two years. This project will explore some of the properties of assignment graphs as well as investigate what assignment graphs arise when the pebbling move is generalized. That is, removing a pebbles from a vertex and placing b pebbles on an adjacent vertex.

## Project 21.06: Impartial Two-Player Graph Pebbling Games

Graph pebbling is a mathematical game played on a simple graph (i.e., an undirected graph with no loops or multiple edges). A pebbling move consists of removing two pebbles from a vertex and adding one pebble to an adjacent vertex. A pebble assignment (S_G) on a finite, simple graph G is a distribution of a finite number of pebbles on the vertices of G. This project will explore the question: Under what conditions will graph pebbling be an next-player game when it is played as an impartial two-person game on a given family of graphs.

## Project 21.07: Impartial Two-Player Games on an n by n Lattice

Let L be an n by n lattice and k<n be a positive integer. Player 1 selects a node and labels it with an integer value 1 <= m_1 \<= k. Player 2 must select a node within m_1 of the previous node and label it with a value  1 <= m_2 <= k. Player 1 must now select a node within m_2 of the previous node, avoiding all previously labeled nodes. Play continues in this fashion until no move is possible. The winner is the player who makes the last possible move. This project will explore for what values of n and k the game is a next-player game.

## Project 21.08: Algebraically Defined Graphs

An algebraically defined graph can be constructed as a bipartite graph in which each vertex is assigned an (x,y)-coordinate pair, and two vertices are adjacent when their coordinate pairs satisfy a given equation.  For example, one could study a graph in which (a,b) is adjacent to [x,y] whenever  b+y=a2x5+ax3.  In this project, we will be interested in the distances between vertices in these graphs, which are related to the existence of solutions to special equations (or systems of equations).  We will explore how the graphs’ properties change when the coordinates are subject to different restrictions, as well as when we generalize the graphs in various ways.  This project is related to areas of math such as algebra, graph theory, and incidence geometry (although no special prior knowledge is assumed or required).