# Discrete Mathematics and Combinatorics Commons™

859 Full-Text Articles 1,069 Authors 73,100 Downloads 91 Institutions

## All Articles in Discrete Mathematics and Combinatorics

859 full-text articles. Page 1 of 31.

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.

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.

Ordering Cacti With Signless Laplacian Spread, 2018 China University of Mining and Technology

#### Ordering Cacti With Signless Laplacian Spread, Zhen Lin, Shu-Guang Guo

##### Electronic Journal of Linear Algebra

A cactus is a connected graph in which any two cycles have at most one vertex in common. The signless Laplacian spread of a graph is defined as the difference between the largest eigenvalue and the smallest eigenvalue of the associated signless Laplacian matrix. In this paper, all cacti of order n with signless Laplacian spread greater than or equal to n − 1/2 are determined.

Two Linear Preserver Problems On Graphs, 2018 Hunan University

#### Two Linear Preserver Problems On Graphs, Yanan Hu, Zhenhua Lyu

##### Electronic Journal of Linear Algebra

Let n, t, k be integers such that 3 ≤ t,k ≤ n. Denote by G_n the set of graphs with vertex set {1,2,...,n}. In this paper, the complete linear transformations on G_n mapping K_t-free graphs to K_t-free graphs are characterized. The complete linear transformations on G_n mapping C_k-free graphs to C_k-free graphs are also characterized when n ≥ 6.

Subsets Of Vertices Of The Same Size And The Same Maximum Distance, 2018 Karlsruhe Institute of Technology

#### Subsets Of Vertices Of The Same Size And The Same Maximum Distance, Maria Axenovich, Dominik Duerrschnabel

##### Theory and Applications of Graphs

For a simple connected graph $G=(V,E)$ and a subset $X$ of its vertices, let $$d^*(X) = \max\{{\rm dist}_G(x,y): x,y\in X\}$$ and let

$h^*(G)$ be the largest $k$ such that there are disjoint vertex subsets $A$ and $B$ of $G$, each of size $k$ such that $d^*(A) = d^*(B).$

Let $h^*(n) = \min \{h^*(G): |V(G)|=n\}$. We prove that $h^*(n) = \lfloor (n+1)/3 \rfloor,$ for $n\geq 6.$ This solves the homometric set problem restricted to the largest distance exactly. In addition we compare $h^*(G)$ with ...

Italian Domination On Ladders And Related Products, 2018 East Tennessee State University

#### Italian Domination On Ladders And Related Products, Bradley Gardner

##### Electronic Theses and Dissertations

An Italian dominating function on a graph $G = (V,E)$ is a function such that $f : V \to \{0,1,2\}$, and for each vertex $v \in V$ for which $f(v) = 0$, we have $\sum_{u\in N(v)}f(u) \geq 2$. The weight of an Italian dominating function is $f(V) = \sum_{v\in V(G)}f(v)$. The minimum weight of all such functions on a graph $G$ is called the Italian domination number of $G$. In this thesis, we will consider Italian domination in various types of products of a graph $G$ with the complete ...

Pentagons In Triangle-Free Graphs, 2018 Iowa State University

#### Pentagons In Triangle-Free Graphs, Bernard Lidicky, Florian Pfender

##### Mathematics Publications

For all n≥9, we show that the only triangle-free graphs on n vertices maximizing the number 5-cycles are balanced blow-ups of a 5-cycle. This completely resolves a conjecture by Erd\H{o}s, and extends results by Grzesik and Hatami, Hladky, Kral, Norin and Razborov, where they independently showed this same result for large n and for all n divisible by 5.

Finite Simple Graphs And Their Associated Graph Lattices, 2018 Middle Tennessee State University

#### Finite Simple Graphs And Their Associated Graph Lattices, James B. Hart, Brian Frazier

##### Theory and Applications of Graphs

In his 2005 dissertation, Antoine Vella explored combinatorical aspects of finite graphs utilizing a topological space whose open sets are intimately tied to the structure of the graph. In this paper, we go a step further and examine some aspects of the open set lattices induced by these topological spaces. In particular, we will characterize all lattices that constitute the opens for finite simple graphs endowed with this topology, explore the structure of these lattices, and show that these lattices contain information necessary to reconstruct the graph and its complement in several ways.

Erasure Coding For Distributed Matrix Multiplication For Matrices With Bounded Entries, 2018 Iowa State University

#### Erasure Coding For Distributed Matrix Multiplication For Matrices With Bounded Entries, Li Tang, Konstantinos Konstantinidis, Aditya Ramamoorthy

##### Electrical and Computer Engineering Publications

Distributed matrix multiplication is widely used in several scientific domains. It is well recognized that computation times on distributed clusters are often dominated by the slowest workers (called stragglers). Recent work has demonstrated that straggler mitigation can be viewed as a problem of designing erasure codes. For matrices A and B, the technique essentially maps the computation of ATB into the multiplication of smaller (coded) submatrices. The stragglers are treated as erasures in this process. The computation can be completed as long as a certain number of workers (called the recovery threshold) complete their assigned tasks. We present a novel ...

Inducibility Of Directed Paths, 2018 Hankuk University of Foreign Studies

#### Inducibility Of Directed Paths, Ilkyoo Choi, Bernard Lidicky, Florian Pfender

##### Mathematics Publications

A long standing open problem in extremal graph theory is to describe all graphs that maximize the number of induced copies of a path on four vertices. The character of the problem changes in the setting of oriented graphs, and becomes more tractable. Here we resolve this problem in the setting of oriented graphs without transitive triangles.

Decomposing Graphs Into Edges And Triangles, 2018 University of Warwick

#### Decomposing Graphs Into Edges And Triangles, Daniel Kral, Bernard Lidicky, Taisa L. Martins, Yanitsa Pehova

##### Bernard Lidický

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. 