# Discrete Mathematics and Combinatorics Commons™

## All Articles in Discrete Mathematics and Combinatorics

960 full-text articles. Page 2 of 36.

Potentially Eventually Positive 2-Generalized Star Sign Patterns, 2019 Huaiyin Institute of Technology

#### Potentially Eventually Positive 2-Generalized Star Sign Patterns, Yu Ber-Lin, Ting-Zhu Huang, Xu Sanzhang

A sign pattern is a matrix whose entries belong to the set $\{+, -, 0\}$. An $n$-by-$n$ sign pattern $\mathcal{A}$ is said to be potentially eventually positive if there exists at least one real matrix $A$ with the same sign pattern as $\mathcal{A}$ and a positive integer $k_{0}$ such that $A^{k}>0$ for all $k\geq k_{0}$. An $n$-by-$n$ sign pattern $\mathcal{A}$ is said to be potentially eventually exponentially positive if there exists at least one real matrix $A$ with the same sign pattern as $\mathcal{A}$ and a nonnegative integer $t_ ... 2019 The University of Western Ontario #### Approximation Algorithms For Problems In Makespan Minimization On Unrelated Parallel Machines, Daniel R. Page ##### Electronic Thesis and Dissertation Repository A fundamental problem in scheduling is makespan minimization on unrelated parallel machines (R||Cmax). Let there be a set J of jobs and a set M of parallel machines, where every job Jj ∈ J has processing time or length pi,j ∈ ℚ+ on machine Mi ∈ M. The goal in R||Cmax is to schedule the jobs non-preemptively on the machines so as to minimize the length of the schedule, the makespan. A ρ-approximation algorithm produces in polynomial time a feasible solution such that its objective value is within a multiplicative factor ρ of the optimum ... Fractional Matching Preclusion For Butterfly Derived Networks, 2019 Qinghai University #### Fractional Matching Preclusion For Butterfly Derived Networks, Xia Wang, Tianlong Ma, Chengfu Ye, Yuzhi Xiao, Fang Wang ##### Theory and Applications of Graphs The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost perfect matchings. As a generalization, Liu and Liu [18] recently introduced the concept of fractional matching preclusion number. The fractional matching preclusion number (FMP number) of G, denoted by fmp(G), is the minimum number of edges whose deletion leaves the resulting graph without a fractional perfect matching. The fractional strong matching preclusion number (FSMP number) of G, denoted by fsmp(G), is the minimum number of vertices and edges whose deletion leaves the ... Greatest Common Divisor: Algorithm And Proof, 2019 University of St. Thomas - Houston #### Greatest Common Divisor: Algorithm And Proof, Mary K. Flagg ##### Number Theory No abstract provided. Congruence Relations Mod 2 For (2 X 4^T + 1)-Colored Partitions, 2019 University of South Carolina #### Congruence Relations Mod 2 For (2 X 4^T + 1)-Colored Partitions, Nicholas Torello ##### Senior Theses Let p_r(n) denote the difference between the number of r-colored partitions of n into an even number of distinct parts and into an odd number of distinct parts. Inspired by proofs involving modular forms of the Hirschhorn-Sellers Conjecture, we prove a similar congruence for p_r(n). Using the Jacobi Triple Product identity, we discover a much stricter congruence for p_3(n). The Knill Graph Dimension From Clique Cover, 2019 Pepperdine #### The Knill Graph Dimension From Clique Cover, Evatt Salinger, Dr. Kassahun Betre ##### Seaver College Research And Scholarly Achievement Symposium In this paper we prove that the recursive (Knill) dimension of the join of two graphs has a simple formula in terms of the dimensions of the component graphs: dim (G1 + G2) = 1 + dim G1 + dim G2. We use this formula to derive an expression for the Knill dimension of a graph from its minimum clique cover. A corollary of the formula is that a graph made of the arbitrary union of complete graphs KN of the same order KN will have dimension N − 1. Triangle Packing On Tripartite Graphs Is Hard, 2019 University of Kansas #### Triangle Packing On Tripartite Graphs Is Hard, Peter A. Bradshaw ##### Rose-Hulman Undergraduate Mathematics Journal The problem of finding a maximum matching on a bipartite graph is well-understood and can be solved using the augmenting path algorithm. However, the similar problem of finding a large set of vertex-disjoint triangles on tripartite graphs has not received much attention. In this paper, we define a set of vertex-disjoint triangles as a “tratching.” The problem of finding a tratching that covers all vertices of a tripartite graph can be shown to be NP-complete using a reduction from the three-dimensional matching problem. In this paper, however, we introduce a new construction that allows us to emulate Boolean circuits using ... Graphs, Random Walks, And The Tower Of Hanoi, 2019 Baldwin Wallace University, Berea #### Graphs, Random Walks, And The Tower Of Hanoi, Stephanie Egler ##### Rose-Hulman Undergraduate Mathematics Journal The Tower of Hanoi puzzle with its disks and poles is familiar to students in mathematics and computing. Typically used as a classroom example of the important phenomenon of recursion, the puzzle has also been intensively studied its own right, using graph theory, probability, and other tools. The subject of this paper is “Hanoi graphs”, that is, graphs that portray all the possible arrangements of the puzzle, together with all the possible moves from one arrangement to another. These graphs are not only fascinating in their own right, but they shed considerable light on the nature of the puzzle itself ... Asymptotically Optimal Bounds For (T,2) Broadcast Domination On Finite Grids, 2019 Williams College #### Asymptotically Optimal Bounds For (T,2) Broadcast Domination On Finite Grids, Timothy W. Randolph ##### Rose-Hulman Undergraduate Mathematics Journal Let G = (V,E) be a graph and t,r be positive integers. The signal that a tower vertex T of signal strength t supplies to a vertex v is defined as sig(T, v) = max(t − dist(T,v),0), where dist(T,v) denotes the distance between the vertices v and T. In 2015 Blessing, Insko, Johnson, and Mauretour defined a (t, r) broadcast dominating set, or simply a (t, r) broadcast, on G as a set T ⊆ V such that the sum of all signal received at each vertex v ∈ V from the set of towers T ... A Generalized Newton-Girard Identity, 2019 University of Maryland, College Park #### A Generalized Newton-Girard Identity, Tanay Wakhare ##### Rose-Hulman Undergraduate Mathematics Journal We present a generalization of the Newton-Girard identities, along with some applications. As an addendum, we collect many evaluations of symmetric polynomials to which these identities apply. Decomposing Graphs Into Edges And Triangles, 2019 University of Warwick #### Decomposing Graphs Into Edges And Triangles, Daniel Kral, Bernard Lidicky, Taisa L. Martins, Yanitsa Pehova ##### Mathematics Publications We prove the following 30 year-old conjecture of Győri and Tuza: the edges of every n-vertex graph G can be decomposed into complete graphs C1,. . .,Cℓ of orders two and three such that |C1|+···+|Cℓ| ≤ (1/2+o(1))n2. This result implies the asymptotic version of the old result of Erdős, Goodman and Pósa that asserts the existence of such a decomposition with ℓ ≤ n2/4. Dissertation_Davis.Pdf, 2019 University of Kentucky #### Dissertation_Davis.Pdf, Brian Davis ##### brian davis Simplices are the simplest" examples of polytopes, and yet they exhibit much of the rich and subtle combinatorics and commutative algebra of their more general cousins. In this way they are sufficiently complicated --- insights gained from their study can inform broader research in Ehrhart theory and associated fields. In this dissertation we consider two previously unstudied properties of lattice simplices; one algebraic and one combinatorial. The first is the Poincare series of the associated semigroup algebra, which is substantially more complicated than the Hilbert series of that same algebra. The second is the partial ordering of the elements of the ... Singular Ramsey And Turán Numbers, 2019 University of Haifa-Oranim #### Singular Ramsey And Turán Numbers, Yair Caro, Zsolt Tuza ##### Theory and Applications of Graphs We say that a subgraph F of a graph G is singular if the degrees d_G(v) are all equal or all distinct for the vertices v of F. The singular Ramsey number Rs(F) is the smallest positive integer n such that, for every m at least n, in every edge 2-coloring of K_m, at least one of the color classes contains F as a singular subgraph. In a similar flavor, the singular Turán number Ts(n,F) is defined as the maximum number of edges in a graph of order n, which does not contain F as a ... Random Models Of Idempotent Linear Maltsev Conditions. I. Idemprimality, 2019 Iowa State University #### Random Models Of Idempotent Linear Maltsev Conditions. I. Idemprimality, Clifford Bergman, Agnes Szendrei ##### Mathematics Publications We extend a well-known theorem of Murski\v{\i} to the probability space of finite models of a system M of identities of a strong idempotent linear Maltsev condition. We characterize the models of M in a way that can be easily turned into an algorithm for producing random finite models of M, and we prove that under mild restrictions on M, a random finite model of M is almost surely idemprimal. This implies that even if such an M is distinguishable from another idempotent linear Maltsev condition by a finite model A of M, a random search for a ... Resolution Of Conjectures Related To Lights Out! And Cartesian Products, 2019 University of Wyoming #### Resolution Of Conjectures Related To Lights Out! And Cartesian Products, Bryan A. Curtis, Jonathan Earl, David Livingston, Bryan L. Shader ##### Electronic Journal of Linear Algebra Lights Out!\ is a game played on a$5 \times 5\$ grid of lights, or more generally on a graph. Pressing lights on the grid allows the player to turn off neighboring lights. The goal of the game is to start with a given initial configuration of lit lights and reach a state where all lights are out. Two conjectures posed in a recently published paper about Lights Out!\ on Cartesian products of graphs are resolved.

Lattice Simplices: Sufficiently Complicated, 2019 University of Kentucky

#### Lattice Simplices: Sufficiently Complicated, Brian Davis

##### Theses and Dissertations--Mathematics

Simplices are the "simplest" examples of polytopes, and yet they exhibit much of the rich and subtle combinatorics and commutative algebra of their more general cousins. In this way they are sufficiently complicated --- insights gained from their study can inform broader research in Ehrhart theory and associated fields.

In this dissertation we consider two previously unstudied properties of lattice simplices; one algebraic and one combinatorial. The first is the Poincar\'e series of the associated semigroup algebra, which is substantially more complicated than the Hilbert series of that same algebra. The second is the partial ordering of the elements of ...

#### Induction Of Nontrivial Supercharacter Theories For Finite Groups, Jesse Franklin

This study focuses on the partitions of a group that arise from: action by conjugation, a two sided multiplicative generalization of conjugation, and inclusion of a subgroup into the group. Since conjugacy classes correspond to irreducible characters, studying the partitions in a group compatible with conjugacy classes in the subgroup, and by analogy, studying the partition of a group compatible with superclasses in a subgroup, invariances in the group can be derived from the subgroup's simpler structure. The fusion of conjugacy classes, and superclasses, has some effects on the calculation of an induced and superinduced function. However, these effects ...

Polychromatic Colorings On The Integers, 2019 Karlsruhe Institute of Technology

#### Polychromatic Colorings On The Integers, Maria Axenovich, John Goldwasser, Bernard Lidicky, Ryan R. Martin, David Offner, John Talbot, Michael Young

##### Mathematics Publications

We show that for any set S ⊆ Z, |S| = 4 there exists a 3-coloring of Z in which every translate of S receives all three colors. This implies that S has a codensity of at most 1/3, proving a conjecture of Newman. We also consider related questions in Zd, d ≥ 2.

Cop Throttling Number: Bounds, Values, And Variants, 2019 Ryerson University

#### Cop Throttling Number: Bounds, Values, And Variants, Anthony Bonato, Jane Breen, Boris Brimkov, Joshua Carlson, Sean English, Jesse Geneson, Leslie Hogben, K. E. Perry, Carolyn Reinhart

##### Mathematics Publications

The cop throttling number thc(G) of a graph G for the game of Cops and Robbers is the minimum of k+captk(G), where k is the number of cops and captk(G) is the minimum number of rounds needed for k cops to capture the robber on G over all possible games in which both players play optimally. In this paper, we answer in the negative a question from [Breen et al., Throttling for the game of Cops and Robbers on graphs, {\em Discrete Math.}, 341 (2018) 2418--2430.] about whether the cop throttling number of any graph is ...

Edge Colorings Of Graphs On Surfaces And Star Edge Colorings Of Sparse Graphs, 2019 West Virginia University

#### Edge Colorings Of Graphs On Surfaces And Star Edge Colorings Of Sparse Graphs, Katherine M. Horacek

##### Graduate Theses, Dissertations, and Problem Reports

In my dissertation, I present results on two types of edge coloring problems for graphs.

For each surface Σ, we define ∆(Σ) = max{∆(G)| G is a class two graph with maximum degree ∆(G) that can be embedded in Σ}. Hence Vizing’s Planar Graph Conjecture can be restated as ∆(Σ) = 5 if Σ is a sphere. For a surface Σ with characteristic χ(Σ) ≤ 0, it is known ∆(Σ) ≥ H(χ(Σ))−1, where H(χ(Σ)) is the Heawood number of the surface, and if the Euler char- acteristic χ(Σ) ∈ {−7, −6, . . . , −1, 0}, ∆(Σ) is already ...