Discrete Mathematics and Combinatorics Commons^™

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

Electronic Journal of Linear Algebra

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

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, Mary K. Flagg

Number Theory

No abstract provided.

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, 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, 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, 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, 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, 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, Brian Davis

brian davis

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