Open Access. Powered by Scholars. Published by Universities.®
Discrete Mathematics and Combinatorics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 4 of 4
Full-Text Articles in Discrete Mathematics and Combinatorics
Triangle Packing On Tripartite Graphs Is Hard, Peter A. Bradshaw
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
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 (𝑡,2) Broadcast Domination On Finite Grids, Timothy W. Randolph
Asymptotically Optimal Bounds For (𝑡,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
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.