We studied facility location problems in which we sought to find the best place to put a facility equally accessible to a number of people. By creating a graph we found that the center of a graph is the best place for such a facility since the center is the vertex or vertices that have minimum eccentricity. We studied various properties and theorems related to the center and pathcenter of trees and connected graphs.

If there is a distinct airport that only allows for three flights out, passengers would want the shortest way (fewest connections) to get to their destinations. For example, if there are 8 airports that are in conjunction with each other, and a passenger would like to get to airport 6 from airport 3, there may be one path that would take three flights; however, there may also be a direct flight to airport 6 from airport 3. In this instance, the passenger would be wiser and more efficient to use his time by taking the direct flight. However, the problem becomes more complex when there are more than 8 airports. The goal of this project is to find a formula that would find minimum amount of flights it would take to get from one airport to another, considering that only three flights are allowed in and out of each port. We hope to solve the problem by making tables of the graphs of consecutive even number of ports until we see a certain pattern that will help us discover a formula that will help us if we have 100 or 1000 airports.

The Traveling Salesman Problem (TSP) is an optimization problem involving Hamilton Circuits. We studied four algorithms used for solving the TSP and analyzed the efficiency and efficacy of each algorithm. We also explored the TSP as an example of an NP - Complete problem.

This presentation will introduce minimum spanning trees and how to find them using Kruskal's Algorithm. The presentation will also include how you can minimize the distance traveled if a Steiner point is introduced into the problem. The presentation will demonstrate how using Torricelli's Method can help in finding the Steiner point.

Our graph theory research project, is titled "Solving Shortest Path, Minimal Distance, and Traveling Salesman Problems Using Weighted Graphs and Various Algorithms." We have done both internet and textbook research. In doing this we have found that by cross-referencing internet materials and textbook definitions we are better able to understand the information and present it in a less complex manner. Our project, a lesson plan to be taught to the class using overheads and practice problems, will contain basic definitions of key words and concepts pertaining to this field, as well as algorithms. The algorithms we will cover include: brute-force, nearest neighbor, cheapest link, and the approximate algorithm. We are also going to introduce formulas used to solve traveling salesman problems.

A zookeeper is given the charge of determining the least number of habitats (cages) to house a certain number of animals. Some of these animals cannot coexist. What is the least number of habitats to build so that all animals can live peacefully?

In this presentation, we will be discussing formulas for solving line-distinguishing and harmonious coloring for paths, cycles, wheels, and complete bipartite graphs. To find the chromatic number for line-distinguishing coloring, you must know that this coloring is not proper, so two adjacent vertices can use the same color, but no two edges can have the same color class. For example: no two lines with a red vertex on one side and a blue one on the other. Harmonious coloring, which is a proper coloring, may not have two edges labeled with the same color class.

In this paper, we will be investigating winning strategies for the popular Dots and Boxes Game. We will be looking in to the strategies for different board sizes: two by two, three by three, four by four, etc. We will look into strategies against greedy types of players.

This presentaion will include a discussion of differentiating sets of graphs. A brief explanation of differetniating sets will be given. Methods of placing detectors on n-cubes (specifically Q2, Q3, and Q4) and other graphs will be discussed.

This presentation will explore the concept of harmonious coloring through one of the most basic graph structures, the path. After a brief introduction of paths and coloring, I will explain the specific objectives of harmonious coloring. The path, inherently simple in form, will serve as a good platform for initial investigation of harmonious coloring. An interactive demonstration will allow attendees to absorb a solid understanding of the harmonious coloring procedure. It will also illustrate, however, the complex nature of harmonious coloring as graphs get larger. The remainder of the presentation time will be used to both tackle this complexity and show how aspects of the process can be automated. I will show how I found one solution by algebraically reproducing a pattern I saw. My presentation will conclude with an overview of the related forms of harmonious coloring and will attempt to relate it to some problems of the real world.

For any two vertices U and V in a graph, the distance d(U,V) is the number of edges of the shortest path between U and V. The total distance the graph is the sum of the distances from each vertex to every other vertex. I will demonstrate an algorithm to arrange the edges of three regular graphs to minimize the total distance of the graph. I will present the three regular graphs for n=8 and n=10 and use the algorithm to arrange these graphs.

This presentation includes discussion of designing and drawing a senior class connectedness graph. Related topics of cliques, cutsets, edge connectivity, and girth will also be presented with reference to the senior class graph.

The acyclic chromatic number is a variation of the chromatic number of a graph. The method for coloring graphs to find the acyclic number will be discussed using specific graphs where conjectures were proven. Further results on other classes of graphs will be examined. Finally, a proof that shows a graph exists for any given combination of chromatic number and acyclic chromatic number.

In this talk we will review definitions and examples pertaining to proper and equitable graph coloring. Our main result is the formula for the equitable chromatic number of a bipartite graph. A sketch of the proof of this result will be presented.

Our project concerns finding the k-level domination number for 2 x m grids. In k-level domination, one selects a random vertex, and all vertices k edges away from that vertex are said to be dominated by that vertex. One then continues selecting vertices until all the vertices of the graph are dominated, and the minimum number of vertices required to dominate the entire graph is called the domination number. Our goal is a formula for finding the domination number d at level k for 2 x m grids. We have also explored the domination numbers for l x m grids at 2, 3, and 4 level domination. We discovered the maximum number of vertices that one vertex could dominate with various levels of domination, and the figure that represents the area that one vertex (or square) can dominate can be tessellated to form a larger repeating pattern. From these patterns, we attempted to derive a formula for 2, 3, and 4-level domination numbers in l x m grids.

A dominating set S of vertices in a graph G is a subset of the vertices of G such that each vertex in G is in or adjacent to a vertiex in S. K-domination extends this idea to allow the vertices in G to be at most k units apart from a vertex in S. Applications to the theorems existing , developed and discussed in a paper written this summer at Dimacs by our team - Lorraine Lurie, Joanie Funderburk, Jennifer Schwartz - on "K-domination in Graphs" was explored by Leo Perez, who will be demonstrating and talking about his research on this topic.

Leo will be talking about k-domination in cycles, and grids as it relates to geometry and matrices (the level of math that he learned this term).

Leo was able to come up with his own concept and work on one of my applications that I developed this summer:

"How many smart students and where do we place them in a classroom when these smart students must optimally sit only one desk away from two other students?"

"How do we reconfigure the students when the attendance changes daily." (Can be used for cooperative learning)

With all the mayhem that went on in Florida during this last presidential election, one wonders if an alternative voting system might actually be more fair and accurate than traditional plurality voting.  Some alternatives inlcude approval voting, borda count, cumulative voting, and run-off voting, each with their own advantages and disadvantages.  In 1948, economist Kenneth Arrow came up with some conditions that a "fair" voting system must meet, but later discovered that there can actually be no perfect voting system.  I tested out his findings by carrying out my own voting simulation at my school using three of the voting methods.  My contradicting results prove that the choice of which voting system used can greatly impact the outcome.

My topic is graphy theory dominations. It opens with an introduction to graph theory then goes into what a domination is. Paul Dreyer's work about Dominating the Roman empire is a large portion of my study. It then branches into my own domination graph, a caterpillar. I then show all different types of examples using the Roman model and the open series.

We are looking for the minimum number of fire detectors we would need to make our school safe from fires. Our detectors are able to detect fire in the room in which they are placed as well as any room attached to it. By creating a graph of our school we were able to use our research of placing detectors on Paths to solve this problem.

Modern day buildings and bridges are dependent on the strength and configuration of their steel girders. The fate of the structure lies in the rigidity of the joints. If the structure is braced properly, the joints will be rigid, and the structure will be able to withstand the effects of the "elements". Where and how should the braces be placed so the number of braces used is a minimum? Our objective is to find the optimum solution so that the structure is rigid but uses the least number of braces.

Steiner points are points placed within a figure to facilitate the creation of the shortest possible connection between more than two points. The actual connection of the points is called the Steiner Tree, and the Steiner Tree is drawn by having three lines radiate out of each Steiner Point (surrounding each point with three 120 degree angles) that connects either to points of the figure or to other Steiner Points. The talk will begin with an explanation of the way the use of Steiner Points helped Delta airlines to reduce the cost of their phone lines between its three major offices. After this a definition of Steiner Points will be presented and the manner in which they can be placed within the regular polygons to make the shortest possible connection of the points of the polygons will be shown. During this explanation the fact that a 120 degree Steiner Tree is the shortest possible connection of more than two points will be proven by using a demonstration diagram. The formula that is used to determine how many Steiner Points must be placed within a figure will be explained next (N-2=the number of Steiner Points where N represents the number of sides of the polygon). A relationship will be established between the ratio of the length of the Steiner Tree to the perimeter of the polygon and the number of sides of the polygon to establish the relationship between the number of sides and the efficiency of the Steiner Tree. Soap bubbles, which are the way in which Steiner Points are found in nature, will be discussed and will lead into both an explanation and demonstration of Steiner Points in three dimensions. The way in which Steiner Points are used in irregular polygons will be briefly shown. Finally, the uses of Steiner Points, such as shortening telephone wires, networking computers, setting up an intercom system, and creating the shortest possible routes (for golf courses and ambulances), will be discussed along with the irregularities that arise when Steiner Points are used in the real world (fractal arrays, physical obstacles, a taxicab plane, and collinear points).