Digital Commons Network^™

The Four Color Theorem: A Possible New Approach, Matthew Brady

All Student Theses

The goal of this thesis is to explore the topic of graph coloring and expand on existing ideas in the field of Graph Theory. These developments will then be used to provide a possible approach in proving the 4 – color theorem that was made famous by Guthrie in the 1800’s.

Since the theorem was presented, many proofs were presented and eventually disregarded for one reason or another. Today, the types of proofs that are considered correct all rely on a computer. The first of this kind was set forth by Appel and Haken in 1977. The driving idea behind …

Realizing Tournaments As Models For K-Majority Voting, Gina Marie Cheney

Electronic Theses, Projects, and Dissertations

A k-majority tournament is a directed graph that models a k-majority voting scenario, which is realized by 2k - 1 rankings, called linear orderings, of the vertices in the tournament. Every k-majority voting scenario can be modeled by a tournament, but not every tournament is a model for a k-majority voting scenario. In this thesis we show that all acyclic tournaments can be realized as 2-majority tournaments. Further, we develop methods to realize certain quadratic residue tournaments as k-majority tournaments. Thus, each tournament within these classes of tournaments is a model for a k …

Chromatic Connectivity Of Graphs, Elliot Laforge

Dissertations

No abstract provided.

Neighborhood-Restricted Achromatic Colorings Of Graphs, James D. Chandler Sr.

Electronic Theses and Dissertations

A (closed) neighborhood-restricted 2-achromatic-coloring of a graph G is an assignment of colors to the vertices of G such that no more than two colors are assigned in any closed neighborhood. In other words, for every vertex v in G, the vertex v and its neighbors are in at most two different color classes. The 2-achromatic number is defined as the maximum number of colors in any 2-achromatic-coloring of G. We study the 2-achromatic number. In particular, we improve a known upper bound and characterize the extremal graphs for some other known bounds.

On The Conjugacy Problem For Automorphisms Of Trees, Kyle Douglas Beserra

Boise State University Theses and Dissertations

In this thesis we identify the complexity of the conjugacy problem of automorphisms of regular trees. We expand on the results of Kechris, Louveau, and Friedman on the complexities of the isomorphism problem of classes of countable trees. We see in nearly all cases that the complexity of isomorphism of subtrees of a given regular countable tree is the same as the complexity of conjugacy of automorphisms of the same tree, though we present an example for which this does not hold.

A Cycle Generating Function On Finite Local Rings, Tristen Kirk Wentling

MSU Graduate Theses

We say a function generates a cycle if its output returns the initial value for some number of successive applications of . In this thesis, we develop a class of polynomial functions for finite local rings and associated functions . We show that the zeros of one are precisely the fixed points of the other and that every ring element is either one of these fixed points or is in a cycle of fixed length equal to the order of 2 in the associated group of units. Particular emphasis is given to rings of integers modulo the square of a …

Global Supply Sets In Graphs, Christian G. Moore

Electronic Theses and Dissertations

For a graph G=(V,E), a set S⊆V is a global supply set if every vertex v∈V\S has at least one neighbor, say u, in S such that u has at least as many neighbors in S as v has in V \S. The global supply number is the minimum cardinality of a global supply set, denoted γgs (G). We introduce global supply sets and determine the global supply number for selected families of graphs. Also, we give bounds on the global supply number for general graphs, trees, and grid graphs.

On Edge-Minimization Of Vertex Minimal Graphs With Dicyclic Automorphism Group, Peter E. Huston

Undergraduate Honors Thesis Projects

We find the smallest degree of a graph with automorphism group isomorphic to the dicyclic group with 4n elements, denoted α(Dic_n). We also find the fewest edges a minimum-order graph with dicyclic automorphism group and a minimal number of vertices can have. For n not a power of 2, the value of α(Dic_n) is significantly less than the best previously known upper bound, 8n. Such an edge-minimized vertex-minimal graph is constructed and shown to have automorphism group Dic_n . That the exhibited graph is minimal is verified using a combination of techniques similar to those developed previously for Abelian groups …

Automated Conjecturing Approach For Benzenoids, David Muncy

Theses and Dissertations

Benzenoids are graphs representing the carbon structure of molecules, defined by a closed path in the hexagonal lattice. These compounds are of interest to chemists studying existing and potential carbon structures. The goal of this study is to conjecture and prove relations between graph theoretic properties among benzenoids. First, we generate conjectures on upper bounds for the domination number in benzenoids using invariant-defined functions. This work is an extension of the ideas to be presented in a forthcoming paper. Next, we generate conjectures using property-defined functions. As the title indicates, the conjectures we prove are not thought of on our …

The Automorphism Group Of The Halved Cube, Benjamin B. Mackinnon

Theses and Dissertations

An n-dimensional halved cube is a graph whose vertices are the binary strings of length n, where two vertices are adjacent if and only if they differ in exactly two positions. It can be regarded as the graph whose vertex set is one partite set of the n-dimensional hypercube, with an edge joining vertices at hamming distance two. In this thesis we compute the automorphism groups of the halved cubes by embedding them in R n and realizing the automorphism group as a subgroup of GLn(R). As an application we show that a halved cube is a circulant graph if …