# Discrete Mathematics and Combinatorics Commons™

865 Full-Text Articles 1,078 Authors 104,022 Downloads 92 Institutions

## All Articles in Discrete Mathematics and Combinatorics

865 full-text articles. Page 1 of 31.

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.

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.

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.

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 ...

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 ...

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.

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 ...

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.