Discrete Mathematics and Combinatorics Commons^™

Reducibility Of Eulerian Graphs And Digraphs, Akram B. Attar

Applications and Applied Mathematics: An International Journal (AAM)

In this paper the concept of reducibility in graph theory is discussed, and the deletable vertex (edge) in graph (digraph) is defined. The class of graphs (digraphs) ℛ is called vertex (edge) reducible if for any G∈ ℛ either ℛ is the trivial graph (null graph) or it contains a vertex (edge) v such that G-v∈ ℛ. We introduce some classes of graphs (digraphs) which are reducible and others which are not. The vertex reducibility and edge reducibility of Eulerian graphs and Eulerian digraphs have also been studied.

Extremal Results For Peg Solitaire On Graphs, Aaron D. Gray

Electronic Theses and Dissertations

In a 2011 paper by Beeler and Hoilman, the game of peg solitaire is generalized to arbitrary boards. These boards are treated as graphs in the combinatorial sense. An open problem from that paper is to determine the minimum number of edges necessary for a graph with a fixed number of vertices to be solvable. This thesis provides new bounds on this number. It also provides necessary and sufficient conditions for two families of graphs to be solvable, along with criticality results, and the maximum number of pegs that can be left in each of the two graph families.

Packings And Coverings Of Complete Graphs With A Hole With The 4-Cycle With A Pendant Edge, Yan Xia

Electronic Theses and Dissertations

In this thesis, we consider packings and coverings of various complete graphs with the 4-cycle with a pendant edge. We consider both restricted and unrestricted coverings. Necessary and sufficient conditions are given for such structures for (1) complete graphs K_v, (2) complete bipartite graphs K_m,n, and (3) complete graphs with a hole K(v,w).

Lattice Point Counting And Height Bounds Over Number Fields And Quaternion Algebras, Lenny Fukshansky, Glenn Henshaw

CMC Faculty Publications and Research

An important problem in analytic and geometric combinatorics is estimating the number of lattice points in a compact convex set in a Euclidean space. Such estimates have numerous applications throughout mathematics. In this note, we exhibit applications of a particular estimate of this sort to several counting problems in number theory: counting integral points and units of bounded height over number fields, counting points of bounded height over positive definite quaternion algebras, and counting points of bounded height with a fixed support over global function fields. Our arguments use a collection of height comparison inequalities for heights over a number …

Counting The Number Of Squares Reachable In K Knight's Moves., Amanda M. Miller, David L. Farnsworth

Articles

from its initial position on an infinite chessboard are derived. The number of squares reachable in exactly k moves are 1, 8, 32, 68, and 96 for k = 0, 1, 2, 3, and 4, respectively, and 28k – 20 for k ≥ 5. The cumulative number of squares reach- able in k or fever moves are 1, 9, 41, and 109 for k = 0, 1, 2, and 3, respectively, and 14k-squared – 6k + 5 for k ≥ 4. Although these formulas are known, the proofs that are presented are new and more mathematically accessible then preceding proofs.

A Discrete Approach To The Poincare-Miranda Theorem, Connor Thomas Ahlbach

HMC Senior Theses

The Poincare-Miranda Theorem is a topological result about the existence of a zero of a function under particular boundary conditions. In this thesis, we explore proofs of the Poincare-Miranda Theorem that are discrete in nature - that is, they prove a continuous result using an intermediate lemma about discrete objects. We explain a proof by Tkacz and Turzanski that proves the Poincare-Miranda theorem via the Steinhaus Chessboard Theorem, involving colorings of partitions of n-dimensional cubes. Then, we develop a new proof of the Poincare-Miranda Theorem that relies on a polytopal generalization of Sperner's Lemma of Deloera - Peterson - Su. …

Hypergraph Capacity With Applications To Matrix Multiplication, John Lee Thompson Peebles Jr.

HMC Senior Theses

The capacity of a directed hypergraph is a particular numerical quantity associated with a hypergraph. It is of interest because of certain important connections to longstanding conjectures in theoretical computer science related to fast matrix multiplication and perfect hashing as well as various longstanding conjectures in extremal combinatorics.

We give an overview of the concept of the capacity of a hypergraph and survey a few basic results regarding this quantity. Furthermore, we discuss the Lovász number of an undirected graph, which is known to upper bound the capacity of the graph (and in practice appears to be the best such …

Chip Firing Games And Riemann-Roch Properties For Directed Graphs, Joshua Z. Gaslowitz

HMC Senior Theses

The following presents a brief introduction to tropical geometry, especially tropical curves, and explains a connection to graph theory. We also give a brief summary of the Riemann-Roch property for graphs, established by Baker and Norine (2007), as well as the tools used in their proof. Various generalizations are described, including a more thorough description of the extension to strongly connected directed graphs by Asadi and Backman (2011). Building from their constructions, an algorithm to determine if a directed graph has Row Riemann-Roch Property is given and thoroughly explained.

Peg Solitaire On Trees With Diameter Four, Clayton A. Walvoort

Electronic Theses and Dissertations

In a paper by Beeler and Hoilman, the traditional game of peg solitaire is generalized to graphs in the combinatorial sense. One of the important open problems in this paper was to classify solvable trees. In this thesis, we will give necessary and sufficient conditions for the solvability for all trees with diameter four. We also give the maximum number of pegs that can be left on such a graph under the restriction that we jump whenever possible.

Simulated Annealing Approach To Flow Shop Scheduling, Sadhana Yellanki

UNLV Theses, Dissertations, Professional Papers, and Capstones

Flow Shop Scheduling refers to the process of allotting various jobs to the machines given, such that every job starts to process on a machine n only after it has finished processing on machine n-1, with each job having n operations to be performed one per machine. To find a schedule that leads to the optimal utilization of resources, expects the schedule to finish in a minimum span of time, and also satisfy the optimality criterion set for the related scheduling problem is NP-Hard, if n > 2. In this thesis, we have developed an algorithm adopting a heuristic called Simulated …

Generalizations Of Pascal's Triangle: A Construction Based Approach, Michael Anton Kuhlmann

UNLV Theses, Dissertations, Professional Papers, and Capstones

The study of this paper is based on current generalizations of Pascal's Triangle, both the expansion of the polynomial of one variable and the multivariate case. Our goal is to establish relationships between these generalizations, and to use the properties of the generalizations to create a new type of generalization for the multivariate case that can be represented in the third dimension.

In the first part of this paper we look at Pascal's original Triangle with properties and classical applications. We then look at contemporary extensions of the triangle to coefficient arrays for polynomials of two forms. The first of …

Restricted And Unrestricted Coverings Of Complete Bipartite Graphs With Hexagons, Wesley M. Surber

Electronic Theses and Dissertations

A minimal covering of a graph G with isomorphic copies of graph H is a set {H₁, H₂, H₃, ... , H_n} where H_i is isomorphic to H, the vertex set of H_i is a subset of G, the edge set of G is a subset of the union of H_i's, and the cardinality of the union of H_i's minus G is minimum. Some studies have been made of covering the complete graph in which case an added condition of the edge set of H_{i …}

Very Cost Effective Partitions In Graphs, Inna Vasylieva

Electronic Theses and Dissertations

For a graph G=(V,E) and a set of vertices S, a vertex v in S is said to be very cost effective if it is adjacent to more vertices in V -S than in S.

A bipartition pi={S, V- S} is called very cost effective if both S and V- S are very cost effective sets. Not all graphs have a very cost effective bipartition, for example, the complete graphs of odd order do not. We consider several families of graphs G, including Cartesian products and cacti graphs, to determine whether G has a very cost effective bipartition.

Information-Based Physics: An Intelligent Embedded Agent's Guide To The Universe, Kevin H. Knuth

Physics Faculty Scholarship

In this talk, I propose an approach to understanding the foundations of physics by considering the optimal inferences an intelligent agent can make about the universe in which he or she is embedded. Information acts to constrain an agent’s beliefs. However, at a fundamental level, any information is obtained from interactions where something influences something else. Given this, the laws of physics must be constrained by both the nature of such influences and the rules by which we can make inferences based on information about these influences. I will review the recent progress we have made in this direction. This …

The K-Dominating Graph, Ruth Haas, Karen Seyffarth

Mathematics Sciences: Faculty Publications

Abstract. Given a graph G, the k-dominating graph of G, D_k(G), is defined to be the graph whose vertices correspond to the dominating sets of G that have cardinality at most k. Two vertices in D_k(G) are adjacent if and only if the corresponding dominating sets of G differ by either adding or deleting a single vertex. The graph D_k(G) aids in studying the reconfiguration problem for dominating sets. In particular, one dominating set can be reconfigured to another by a sequence of single vertex additions and deletions, such that the intermediate set of …

Generalizing Tanisaki's Ideal Via Ideals Of Truncated Symmetric Functions, Aba Mbirika, Julianna Tymoczko

Mathematics Sciences: Faculty Publications

Abstract. We define a family of ideals I_h in the polynomial ring Z[_{x1, . . . , xn}] that are parametrized by Hessenberg functions h (equivalently Dyck paths or ample partitions). The ideals I_h generalize algebraically a family of ideals called the Tanisaki ideal, which is used in a geometric construction of permutation representations called Springer theory. To define I_h, we use polynomials in a proper subset of the variables {_{x1, . . . , xn}} that are symmetric under the corresponding permutation subgroup. We call these polynomials truncated symmetric functions and …

Chromatic Bounds On Orbital Chromatic Roots, Dae Hyun Kim, Alexander H. Mun, Mohamed Omar

All HMC Faculty Publications and Research

Given a group G of automorphisms of a graph Γ, the orbital chromatic polynomial OPΓ,G(x) is the polynomial whose value at a positive integer k is the number of orbits of G on proper k-colorings of Γ. In \cite{Cameron}, Cameron et. al. explore the roots of orbital chromatic polynomials, and in particular prove that orbital chromatic roots are dense in R, extending Thomassen's famous result (see \cite{Thomassen}) that chromatic roots are dense in [32/27,∞). Cameron et al \cite{Cameron} further conjectured that the real roots of the orbital chromatic polynomial of any graph are bounded above by the largest real root …

A New Recursion For Three-Column Combinatorial Macdonald Polynomials, Elizabeth Niese

Mathematics Faculty Research

The Hilbert series of the Garsia–Haiman module M_μ can be described combinatorially as the generating function of certain fillings of the Ferrers diagram of μ where μ is an integer partition of n . Since there are n ! fillings that generate , it is desirable to find recursions to reduce the number of fillings that need to be considered when computing combinatorially. In this paper, we present a combinatorial recursion for the case where μ is an n by 3 rectangle. This allows us to reduce the number of fillings under consideration from (3n)! to (3n)!/(3!ⁿn!).

Knight's Tours On 3 X N Chessboards With A Single Square Removed, Amanda M. Miller, David L. Farnsworth

Articles

The following theorem is proved: A knight’s tour exists on all 3 x n chessboards with one square removed unless: n is even, the removed square is (i, j) with i + j odd, n = 3 when any square other than the center square is removed, n = 5, n = 7 when any square other than square (2, 2) or (2, 6) is removed, n = 9 when square (1, 3), (3, 3), (1, 7), (3, 7), (2, 4), (2, 6), (2, 2), or (2, 8) is removed, or n = 11 when square (1, 3), (2, 4), …

Constructions And Enumeration Methods For Cubic Graphs And Trees, Erica R. Gilliland

Undergraduate Honors Thesis Collection

The goal of this thesis is to study two related problems that, in the broadest terms, lie in a branch of mathematics called graph theory. The first problem examines some new techniques for constructing a Hamilton graph of least possible order and having a preassigned girth, and the second concerns the enumeration of a certain type of graphs called trees.