Open Access. Powered by Scholars. Published by Universities.®

Discrete Mathematics and Combinatorics Commons

Open Access. Powered by Scholars. Published by Universities.®

1,081 Full-Text Articles 1,236 Authors 294,667 Downloads 113 Institutions

All Articles in Discrete Mathematics and Combinatorics

Faceted Search

1,081 full-text articles. Page 1 of 42.

Unomaha Problem Of The Week (2021-2022 Edition), Brad Horner, Jordan M. Sahs 2022 University of Nebraska at Omaha

Unomaha Problem Of The Week (2021-2022 Edition), Brad Horner, Jordan M. Sahs

Student Research and Creative Activity Fair

The University of Omaha math department's Problem of the Week was taken over in Fall 2019 from faculty by the authors. The structure: each semester (Fall and Spring), three problems are given per week for twelve weeks, with each problem worth ten points - mimicking the structure of arguably the most well-regarded university math competition around, the Putnam Competition, with prizes awarded to top-scorers at semester's end. The weekly competition was halted midway through Spring 2020 due to COVID-19, but relaunched again in Fall 2021, with massive changes.

Now there are three difficulty tiers to POW problems, roughly corresponding ...


An Even 2-Factor In The Line Graph Of A Cubic Graph, SeungJae Eom, Kenta Ozeki 2022 Yokohama National University

An Even 2-Factor In The Line Graph Of A Cubic Graph, Seungjae Eom, Kenta Ozeki

Theory and Applications of Graphs

An even 2-factor is one such that each cycle is of even length. A 4- regular graph G is 4-edge-colorable if and only if G has two edge-disjoint even 2- factors whose union contains all edges in G. It is known that the line graph of a cubic graph without 3-edge-coloring is not 4-edge-colorable. Hence, we are interested in whether those graphs have an even 2-factor. Bonisoli and Bonvicini proved that the line graph of a connected cubic graph G with an even number of edges has an even 2-factor, if G has a perfect matching [Even cycles and even ...


On Two-Player Pebbling, Garth Isaak, Matthew Prudente, Andrea Potylycki, William Fagley, Joseph Marcinik 2022 Lehigh University

On Two-Player Pebbling, Garth Isaak, Matthew Prudente, Andrea Potylycki, William Fagley, Joseph Marcinik

Communications on Number Theory and Combinatorial Theory

Graph pebbling can be extended to a two-player game on a graph G, called Two-Player Graph Pebbling, with players Mover and Defender. The players each use pebbling moves, the act of removing two pebbles from one vertex and placing one of the pebbles on an adjacent vertex, to win. Mover wins if they can place a pebble on a specified vertex. Defender wins if the specified vertex is pebble-free and there are no more pebbling moves on the vertices of G. The Two-Player Pebbling Number of a graph G, η(G), is the minimum m such that for every arrangement ...


Tiling Rectangles And 2-Deficient Rectangles With L-Pentominoes, Monica Kane 2022 California Lutheran University

Tiling Rectangles And 2-Deficient Rectangles With L-Pentominoes, Monica Kane

Rose-Hulman Undergraduate Mathematics Journal

We investigate tiling rectangles and 2-deficient rectangles with L-pentominoes. First, we determine exactly when a rectangle can be tiled with L-pentominoes. We then determine locations for pairs of unit squares that can always be removed from an m × n rectangle to produce a tileable 2-deficient rectangle when m ≡ 1 (mod 5), n ≡ 2 (mod 5) and when m ≡ 3 (mod 5), n ≡ 4 (mod 5).


Extremal Problems In Graph Saturation And Covering, Adam Volk 2022 University of Nebraska-Lincoln

Extremal Problems In Graph Saturation And Covering, Adam Volk

Dissertations, Theses, and Student Research Papers in Mathematics

This dissertation considers several problems in extremal graph theory with the aim of finding the maximum or minimum number of certain subgraph counts given local conditions. The local conditions of interest to us are saturation and covering. Given graphs F and H, a graph G is said to be F-saturated if it does not contain any copy of F, but the addition of any missing edge in G creates at least one copy of F. We say that G is H-covered if every vertex of G is contained in at least one copy of H. In the former setting, we ...


3-Uniform 4-Path Decompositions Of Complete 3-Uniform Hypergraphs, Rachel McCann 2022 University of Arkansas, Fayetteville

3-Uniform 4-Path Decompositions Of Complete 3-Uniform Hypergraphs, Rachel Mccann

Mathematical Sciences Undergraduate Honors Theses

The complete 3-uniform hypergraph of order v is denoted as Kv and consists of vertex set V with size v and edge set E, containing all 3-element subsets of V. We consider a 3-uniform hypergraph P7, a path with vertex set {v1, v2, v3, v4, v5, v6, v7} and edge set {{v1, v2, v3}, {v2, v3, v4}, {v4, v5, v6}, {v5, v6, v7}}. We provide the necessary and sufficient conditions for the existence of a decomposition of Kv ...


Modern Theory Of Copositive Matrices, Yuqiao Li 2022 William & Mary

Modern Theory Of Copositive Matrices, Yuqiao Li

Undergraduate Honors Theses

Copositivity is a generalization of positive semidefiniteness. It has applications in theoretical economics, operations research, and statistics. An $n$-by-$n$ real, symmetric matrix $A$ is copositive (CoP) if $x^T Ax \ge 0$ for any nonnegative vector $x \ge 0.$ The set of all CoP matrices forms a convex cone. A CoP matrix is ordinary if it can be written as the sum of a positive semidefinite (PSD) matrix and a symmetric nonnegative (sN) matrix. When $n < 5,$ all CoP matrices are ordinary. However, recognizing whether a given CoP matrix is ordinary and determining an ordinary decomposition (PSD + sN) is still an unsolved problem. Here, we give an overview on modern theory of CoP matrices, talk about our progress on the ordinary recognition and decomposition problem, and emphasis the graph theory aspect of ordinary CoP matrices.


Quantum Dimension Polynomials: A Networked-Numbers Game Approach, Nicholas Gaubatz 2022 Murray State University

Quantum Dimension Polynomials: A Networked-Numbers Game Approach, Nicholas Gaubatz

Honors College Theses

The Networked-Numbers Game--a mathematical "game'' played on a simple graph--is incredibly accessible and yet surprisingly rich in content. The Game is known to contain deep connections to the finite-dimensional simple Lie algebras over the complex numbers. On the other hand, Quantum Dimension Polynomials (QDPs)--enumerative expressions traditionally understood through root systems--corresponding to the above Lie algebras are complicated to derive and often inaccessible to undergraduates. In this thesis, the Networked-Numbers Game is defined and some known properties are presented. Next, the significance of the QDPs as a method to count combinatorially interesting structures is relayed. Ultimately, a novel closed-form expression ...


How To Guard An Art Gallery: A Simple Mathematical Problem, Natalie Petruzelli 2022 St. John Fisher College

How To Guard An Art Gallery: A Simple Mathematical Problem, Natalie Petruzelli

The Review: A Journal of Undergraduate Student Research

The art gallery problem is a geometry question that seeks to find the minimum number of guards necessary to guard an art gallery based on the qualities of the museum’s shape, specifically the number of walls. Solved by Václav Chvátal in 1975, the resulting Art Gallery Theorem dictates that ⌊n/3⌋ guards are always sufficient and sometimes necessary to guard an art gallery with n walls. This theorem, along with the argument that proves it, are accessible and interesting results even to one with little to no mathematical knowledge, introducing readers to common concepts in both geometry and graph ...


A New Method To Compute The Hadamard Product Of Two Rational Functions, Ishan Kar 2022 Prospect High School, Saratoga

A New Method To Compute The Hadamard Product Of Two Rational Functions, Ishan Kar

Rose-Hulman Undergraduate Mathematics Journal

The Hadamard product (denoted by∗) of two power series A(x) =a0+a1x+a2x2+···and B(x) =b0+b1x+b2x2+··· is the power series A(x)∗B(x) =a0b0+a1b1x+a2b2x2+···. Although it is well known that the Hadamard product of two rational functions is also rational, a closed form expression of the Hadamard product of rational functions has not been found. Since any rational power series can be expanded by partial fractions as a polynomial ...


Some Np-Complete Edge Packing And Partitioning Problems In Planar Graphs, Jed Yang 2022 Bethel University

Some Np-Complete Edge Packing And Partitioning Problems In Planar Graphs, Jed Yang

Communications on Number Theory and Combinatorial Theory

Graph packing and partitioning problems have been studied in many contexts, including from the algorithmic complexity perspective. Consider the packing problem of determining whether a graph contains a spanning tree and a cycle that do not share edges. Bernáth and Király proved that this decision problem is NP-complete and asked if the same result holds when restricting to planar graphs. Similarly, they showed that the packing problem with a spanning tree and a path between two distinguished vertices is NP-complete. They also established the NP-completeness of the partitioning problem of determining whether the edge set of a graph can be ...


Characterizations Of Certain Classes Of Graphs And Matroids, Jagdeep Singh 2022 Louisiana State University and Agricultural and Mechanical College

Characterizations Of Certain Classes Of Graphs And Matroids, Jagdeep Singh

LSU Doctoral Dissertations

``If a theorem about graphs can be expressed in terms of edges and cycles only, it probably exemplifies a more general theorem about matroids." Most of my work draws inspiration from this assertion, made by Tutte in 1979.

In 2004, Ehrenfeucht, Harju and Rozenberg proved that all graphs can be constructed from complete graphs via a sequence of the operations of complementation, switching edges and non-edges at a vertex, and local complementation. In Chapter 2, we consider the binary matroid analogue of each of these graph operations. We prove that the analogue of the result of Ehrenfeucht et. al. does ...


Unavoidable Structures In Large And Infinite Graphs, Sarah Allred 2022 Louisiana State University and Agricultural and Mechanical College

Unavoidable Structures In Large And Infinite Graphs, Sarah Allred

LSU Doctoral Dissertations

In this work, we present results on the unavoidable structures in large connected and large 2-connected graphs. For the relation of induced subgraphs, Ramsey proved that for every positive integer r, every sufficiently large graph contains as an induced subgraph either Kr or Kr. It is well known that, for every positive integer r, every sufficiently large connected graph contains an induced subgraph isomorphic to one of Kr, K1,r, and Pr. We prove an analogous result for 2-connected graphs. Similarly, for infinite graphs, every infinite connected graph contains an induced subgraph isomorphic to one ...


The Enumeration Of Minimum Path Covers Of Trees, Merielyn Sher 2022 William & Mary

The Enumeration Of Minimum Path Covers Of Trees, Merielyn Sher

Undergraduate Honors Theses

A path cover of a tree T is a collection of induced paths of T that are vertex disjoint and cover all the vertices of T. A minimum path cover (MPC) of T is a path cover with the minimum possible number of paths, and that minimum number is called the path cover number of T. A tree can have just one or several MPC's. Prior results have established equality between the path cover number of a tree T and the largest possible multiplicity of an eigenvalue that can occur in a symmetric matrix whose graph is that tree ...


Prime Labelings On Planar Grid Graphs, Stephen James Curran 2022 University of Pittsburgh - Johnstown

Prime Labelings On Planar Grid Graphs, Stephen James Curran

Theory and Applications of Graphs

It is known that for any prime p and any integer n such that 1≤np there exists a prime labeling on the pxn planar grid graph PpxPn. We show that PpxPn has a prime labeling for any odd prime p and any integer n such that that p<n≤p2.


Characterizing Edge Betweenness-Uniform Graphs, Jana Coroničová Hurajová, Tomas Madaras, Darren A. Narayan 2022 University of Economics, Tajovského

Characterizing Edge Betweenness-Uniform Graphs, Jana Coroničová Hurajová, Tomas Madaras, Darren A. Narayan

Theory and Applications of Graphs

The \emph{betweenness centality} of an edge $e$ is, summed over all $u,v\in V(G)$, the ratio of the number of shortest $u,v$-paths in $G$ containing $e$ to the number of shortest $u,v$-paths in $G$. Graphs whose vertices all have the same edge betweenness centrality are called \emph{edge betweeness-uniform}. It was recently shown by Madaras, Hurajová, Newman, Miranda, Fl\'{o}rez, and Narayan that of the over 11.7 million graphs with ten vertices or fewer, only four graphs are edge betweenness-uniform but not edge-transitive.In this paper we present new results involving ...


Chromatic Polynomials Of Signed Book Graphs, Deepak Sehrawat, Bikash Bhattacharjya 2022 Indian Institute of Technology Guwahati

Chromatic Polynomials Of Signed Book Graphs, Deepak Sehrawat, Bikash Bhattacharjya

Theory and Applications of Graphs

For $m \geq 3$ and $n \geq 1$, the $m$-cycle \textit{book graph} $B(m,n)$ consists of $n$ copies of the cycle $C_m$ with one common edge. In this paper, we prove that (a) the number of switching non-isomorphic signed $B(m,n)$ is $n+1$, and (b) the chromatic number of a signed $B(m,n)$ is either 2 or 3. We also obtain explicit formulas for the chromatic polynomials and the zero-free chromatic polynomials of switching non-isomorphic signed book graphs.


Moving Polygon Methods For Incompressible Fluid Dynamics, Chris Chartrand 2022 University of Massachusetts Amherst

Moving Polygon Methods For Incompressible Fluid Dynamics, Chris Chartrand

Doctoral Dissertations

Hybrid particle-mesh numerical approaches are proposed to solve incompressible fluid flows. The methods discussed in this work consist of a collection of particles each wrapped in their own polygon mesh cell, which then move through the domain as the flow evolves. Variables such as pressure, velocity, mass, and momentum are located either on the mesh or on the particles themselves, depending on the specific algorithm described, and each will be shown to have its own advantages and disadvantages. This work explores what is required to obtain local conservation of mass, momentum, and convergence for the velocity and pressure in a ...


Minimality Of Integer Bar Visibility Graphs, Emily DeHoff 2022 Portland State University

Minimality Of Integer Bar Visibility Graphs, Emily Dehoff

University Honors Theses

A visibility representation is an association between the set of vertices in a graph and a set of objects in the plane such that two objects have an unobstructed, positive-width line of sight between them if and only if their two associated vertices are adjacent. In this paper, we focus on integer bar visibility graphs (IBVGs), which use horizontal line segments with integer endpoints to represent the vertices of a given graph. We present results on the exact widths of IBVGs of paths, cycles, and stars, and lower bounds on trees and general graphs. In our main results, we find ...


Application Of The Combinatorial Nullstellensatz To Integer-Magic Graph Labelings, Richard M. Low, Dan Roberts 2022 San Jose State University

Application Of The Combinatorial Nullstellensatz To Integer-Magic Graph Labelings, Richard M. Low, Dan Roberts

Theory and Applications of Graphs

Let $A$ be a nontrivial abelian group and $A^* = A \setminus \{0\}$. A graph is $A$-magic if there exists an edge labeling $f$ using elements of $A^*$ which induces a constant vertex labeling of the graph. Such a labeling $f$ is called an $A$-magic labeling and the constant value of the induced vertex labeling is called an $A$-magic value. In this paper, we use the Combinatorial Nullstellensatz to show the existence of $\mathbb{Z}_p$-magic labelings (prime $p \geq 3$ ) for various graphs, without having to construct the $\mathbb{Z}_p$-magic labelings. Through many examples ...


Digital Commons powered by bepress