Discrete Mathematics and Combinatorics Commons^™

Ramsey Chains In Graphs, Ritabrato Chatterjee

Dissertations

The research in this work deals with decomposition of graphs and Ramsey theory, two popular areas of research in graph theory due to numerous fascinating problems and the sheer mathematical beauty of the subjects. A decomposition {G₁, G₂, ..., G_k} of a graph G into subgraphs of G is ascending if the subgraph G_i is isomorphic to a proper subgraph of G_i+1 for i = 1, 2, ..., k − 1. The well-known and long-standing of Ascending Subgraph Decomposition Conjecture states that every graph has an ascending subgraph …

From Total Domination To Graph Coloring, Sawyer Isaac Osborn

Dissertations

A question involving a chess piece called a prince on the 8×8 chessboard leads to a concept in graph theory involving total domination. We say a vertex u in a graph G totally dominates a vertex v if u is adjacent to v. A subset S of the vertex set of a graph G is a total dominating set for G if every vertex in G is totally dominated by at least one vertex of S. If S is a total dominating set of G, then σ_S(v) denotes the number of …

Multiple Monochromatic Subgraphs In Edge-Colored Graphs, Emma Felicity Jent

Dissertations

Ramsey theory, though a relatively young branch of mathematics, has captivated the attention of graph theorists, combinatorialists, and theoretical computer scientists alike through its raw beauty, versatility, and powerful applications. Before it emerged as a branch of mathematics, the central idea of Ramsey theory appeared in the form of three lemmas in three separate papers by three different mathematicians working on three distinct areas of research. The first such lemma was published by David Hilbert in 1892, followed by the second lemma published by Issai Schur in 1916. However, Frank Ramsey’s renowned lemma, published in 1930, compelled mathematicians to establish …

Zonality In Graphs, Andrew Bowling

Dissertations

Graph labeling and coloring are among the most popular areas of graph theory due to both the mathematical beauty of these subjects as well as their fascinating applications. While the topic of labeling vertices and edges of graphs has existed for over a century, it was not until 1966 when Alexander Rosa introduced a labeling, later called a graceful labeling, that brought the area of graph labeling to the forefront in graph theory. The subject of graph colorings, on the other hand, goes back to 1852 when the young British mathematician Francis Guthrie observed that the countries in a map …

Irregular Domination In Graphs, Caryn Mays

Dissertations

Domination in graphs has been a popular area of study due in large degree to its applications to modern society as well as the mathematical beauty of the topic. While this area evidently began with the work of Claude Berge in 1958 and Oystein Ore in 1962, domination did not become an active area of research until 1977 with the appearance of a survey paper by Ernest Cockayne and Stephen Hedetniemi. Since then, a large number of variations of domination have surfaced and provided numerous applications to different areas of science and real-life problems. Among these variations are domination parameters …

Vertex Identification In Graphs, Yuya Kono

Dissertations

In recent decades, there has been increased interest in studying ways touniquely identify the vertices of a given graph. Two of best-known vertex identification methods are referred to as the metric dimension introduced by Slater and by Harary, and Melter in the1970s, and the partition dimension introduced by Chartrand in 2000. The first method deals with locating an ordered set of vertices in a connected graph G and uniquely identifying each vertex of G by means of the distance between this vertex and the vertices in the ordered set. The second method deals with partitioning the vertex set of a …

From Multi-Prime To Subset Labelings Of Graphs, Bethel I. Mcgrew

Dissertations

A graph labeling is an assignment of labels (elements of some set) to the vertices or edges (or both) of a graph G. If only the vertices of G are labeled, then the resulting graph is a vertex-labeled graph. If only the edges are labeled, the resulting graph is an edge-labeled graph. The concept was first introduced in the 19th century when Arthur Cayley established Cayley’s Tree Formula, which proved that there are n^n-2 distinct labeled trees of order n. Since then, it has grown into a popular research area.

In this study, we first review several types …

Extremal Problems On Induced Graph Colorings, James Hallas

Dissertations

Graph coloring is one of the most popular areas of graph theory, no doubt due to its many fascinating problems and applications to modern society, as well as the sheer mathematical beauty of the subject. As far back as 1880, in an attempt to solve the famous Four Color Problem, there have been numerous examples of certain types of graph colorings that have generated other graph colorings of interest. These types of colorings only gained momentum a century later, however, when in the 1980s, edge colorings were studied that led to vertex colorings of various types, led by the introduction …

Chromatic Connectivity Of Graphs, Elliot Laforge

Dissertations

No abstract provided.

Average Genus Of The Cube, Jody Koenemann

Honors Theses

In recent years, there has been interest in the mathematical community in a rapidly developing branch of theoretical mathematics known as random topological graph theory. This new area of mathematics explores the different ways in which certain graphs can be imbedded in given surfaces. The random nature of the new branch results when one also imposes a random distribution on set of all imbeddings of a fixed graph, via the orientation of the edges at each vertex. Using the technique of J. Edmonds, developed in 1960, this paper explores the imbeddings for the graph Q₃ using a particular group …

Third Order Degree Regular Graphs, Leslie D. Hayes

Honors Theses

A graph G is regular of degree d if for every vertex v in G there exist exactly d vertices at distance 1 from v. A graph G is kth order regular of degree d if for every vertex v in G, there exist exactly d vertices at distance k from v. In this paper, third order regular graphs of degree 1 with small order are characterized.

Generalized Distance In Graphs, Garry L. Johns

Dissertations

No abstract provided.

Imbedding Problems In Graph Theory, William Goodwin

Honors Theses

For some years there has been interest among mathematicians in determining the different ways in which certain graphs can be imbedded in given surfaces. M.P. VanStraten in 1948, determined that it is possible to imbed the graph K_3,3 (which is the graph representing the famous three houses, three utilities problem) in the torus in only two ways. She then used this fact to show that the graph representing the configuration of Desargues (containing K_3,3 as a subgraph) has genus two. One major source of motivation for the work on imbedding problems has been their relation to coloring problems …