# Proposed Projects

## Project 19.01: Disjoint path covers of hypertori

Let *G* be a simple graph, and let *V* be the vertex set of *G*. Let *S* = {s_{1}, s_{2}, . . . , s_{k}} and *T* = {t_{1}, t_{2}, . . . , t_{k}} be disjoint subsets of *V* . A *paired disjoint k-path cover* of *G* is a subgraph of* G* consisting of paths P_{1}, P_{2}, . . . , P_{k} such that

• each path P_{i} has endpoints s_{i} and t_{i}, and

• the vertex sets of the paths partition *V* .

We will abbreviate the term “paired disjoint *k*-path cover” as “*k-path* cover”. If *G* has a *k-path* cover for every choice of *S* and *T*, then *G* is said to be paired *k-to-k disjoint path coverable*. If *k* = 1, then *G* is also said to be *Hamiltonian connected.*

## Project 19.02: Sum index of graphs

Definition 0.1. Let *G* be a simple graph with vertex set *V* and edge set *E*. Let *f* : *V → Z* be an injective vertex labeling of *G*, and let* f*^{+} : *E → Z* be an induced edge labeling defined by* f*^{+}(*uv*) = *f*(*u*) +*f(v*) for any edge *uv* in *E*. The sum index of *G* is the minimum positive integer *k* such that there exists an injective vertex labeling *f* of *G* with the cardinality of the range of *f*^{+} being *k*.

Some results that we currently have include:

• the sum index of a complete graph *K*_{n} is 2*n* − 3 for all positive integers *n* ≥ 2;

• the sum index of a complete bipartite graph *K _{n,m}* is

*n + m*− 1 for all positive integers

*n*and

*m*;

• the sum index of a caterpillar graph

*G*is ∆, where ∆ is the maximum degree of

*G*;

• the sum index of a tree

*G*with diameter at most 5 is ∆, where ∆ is the maximum degree of

*G*;

• there exists a tree with diameter 6 such that the sum index of

*G*is greater than ∆, where ∆ is the maximum degree of

*G*;

• the sum index of a tree

*G*with diameter

*D*is at most [D/2]∆, where ∆ is the maximum degree of

*G*.

## Project 19.03: Constructing matrices with prescribed number of bases

Let *A* be a matrix of size *r × n* over a field. Assume that *A* has full row rank, so we have *0 < r ≤ n* as a consequence. Let *b* be the number of invertible *r ×r* submatrices of *A*. What are the possible values of *b*? From basic linear algebra and simple counting, we know that *b *must be between 1 and (* ^{n}_{r}*) inclusively.

A more interesting and challenging question is....

## Project 19.04: Two person random race

Alice and Bob play the following game: they take turns to collect 1 or 2 chips randomly and independently with equal probability, with Alice going first. The first person who collects at least n chips is the winner. We have determined that the winning probability of Bob is...

## Project 19.05: 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 19.06: Diameters restricted Polyominoes

A polyomino is a plane geometric figure which is made up of square cells which are joined along an edge. Polyominoes are classified by the number of cells (*n*) present in the polyomino. For example, the classic game of tetris uses polyominoes where *n*=4. There are many different types of polyominoes including free (OEIS A000105), free with holes (OEIS A001419), one-sided (OEIS A000988), and fixed (OEIS A001168). In this project we will consider the diameter restricted polyominoes where the diameter, as in graph theory, is the maximum shortest distance between two cells. We will try to count the number of polyominoes with a fixed number of cells (*n*) and a fixed diameter (*d*) as well as investigate other properties of diameter restricted polyominoes.

## Project 19.07: A Survey on the Existence of G-Designs

A *G*-design of order *n* is a decomposition of the complete graph on *n* vertices into edge-disjoint subgraphs isomorphic to *G*. The spectrum for decomposing the complete graph into trees with up to 8 edges has been studied and the spectrum problem for cycles has been completely solved. A **Halin Graph** is defined by a tree whose leaves have been joined into a cycle. In this project, we will investigate the feasibility of determining necessary and sufficient conditions for the existence of a Halin-design for trees with fewer than eight edges.

## Project 19.08: Structural Results for 1HP on Bipartite Permutations Graphs

The Hamiltonian path problem is a well-known NP-complete graph theory problem which is to determine whether or not it is possible to find a path through all the vertices of a graph, visiting each vertex exactly once. A variation on this problem is the 1HP problem which is to determine, given a graph and a vertex in the graph, whether or not it is possible to find a Hamiltonian path in the graph which has the specified vertex as an end of the path. The problem is also NP-complete for graphs in general, though like the Hamiltonian path problem, 1HP can be polynomially solvable on certain types of graphs. Bipartite permutation graphs is a class of graphs for which the problem is known to be polynomially solvable. In this project, we will investigate whether there are structural properties of bipartite permutation graphs which can determine whether or not there is a Hamiltonian path which has an end at a given vertex.

## Project 19.09:Properly Colored Shortest Paths

An edge coloring of a graph is a **proper edge coloring** if incident edges are colored with distinct colors. A **properly colored path** in a graph is a path such that the edges of the path are properly edge colored. A graph, with an edge coloring, is said to be **properly connected** if there is a properly colored path between every pair of vertices. In this project, we will investigate the minimum number of colors required to color the edges such that every shortest path between a pair of vertices is properly colored.

## Project 19.10:The Game of Plates and Olives

The game of plates and olives begins with an empty plate. At each step either an empty plate is put down, an olive is put down on a plate, an olive is removed, an empty plate is removed, or the olives of two plates are combined on one plate with the other plate being removed. A game of plates and olives can be represented by ordered trees with with n vertices of degree 3 and n + 2 vertices of degree one. The game derives from the consideration of Morse functions on the 2-sphere. An excellent Morse function on the 2-sphere is defined as a function in which all the critical points are non-degenerate. The number of topological equivalence classes of excellent Morse functions on the 2-sphere that have order n (that is, they have 2n +2 critical points) is the same as the number of ways of returning to an empty table for the first time after exactly 2n + 2 steps. We call this number M(n). Upper and lower bounds are known for M(n), but exact values are known only for n <15. This project will examine M(n) by studying families of ordered trees with n vertices of degree 3 and n + 2 vertices of degree 1.

## Project 19.11:Generating Determinants of Latin Squares

Considering a randomly generated collection of samples allows an unbiased investigation of collections that are too extensive to be investigated exhaustively. For example, for each positive integer n, let Dn denote the set of integers consisting of every number that is the determinant of an n by n Latin square. There are many questions concerning the elements of Dn. For instance: For which odd n is 0 in Dn? For which n is n(1 + 2 + ... + n) in Dn?

## Project 19.12:Good Edge-labeling Graphs

A good edge-labeling of a graph is a labeling of its edges such that for any ordered pair of vertices u and v, there is at most one non-decreasing path from u to v. A graph is good if it admits a good edge-labeling. This project will examine if graphs of large girth admit a good edge-labeling.