Open Access. Powered by Scholars. Published by Universities.®
Discrete Mathematics and Combinatorics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Keyword
-
- Graph theory (3)
- $K_n$ (1)
- Chromatic number (1)
- Cycle graphs (1)
- DNA (1)
-
- Divisibility (1)
- Earth-moon Problem (1)
- Edge coloring (1)
- Geometric topology. (1)
- Geometry (1)
- Graph (1)
- Graph coloring (1)
- Graph operations (1)
- Graph sequences (1)
- Graph thickness (1)
- Heuristic algorithms (1)
- Independence number (1)
- Jump graphs (1)
- Knot theory (1)
- Line graph (1)
- Linking number (1)
- Matching (1)
- Net graph (1)
- Planar graphs (1)
- Primality test (1)
- Probability (1)
- SageMath (1)
- Topology (1)
- Total independence number (1)
Articles 1 - 8 of 8
Full-Text Articles in Discrete Mathematics and Combinatorics
Divisibility Probabilities For Products Of Randomly Chosen Integers, Noah Y. Fine
Divisibility Probabilities For Products Of Randomly Chosen Integers, Noah Y. Fine
Rose-Hulman Undergraduate Mathematics Journal
We find a formula for the probability that the product of n positive integers, chosen at random, is divisible by some integer d. We do this via an inductive application of the Chinese Remainder Theorem, generating functions, and several other combinatorial arguments. Additionally, we apply this formula to find a unique, but slow, probabilistic primality test.
Structure Of A Total Independent Set, Lewis Stanton
Structure Of A Total Independent Set, Lewis Stanton
Rose-Hulman Undergraduate Mathematics Journal
Let $G$ be a simple, connected and finite graph with order $n$. Denote the independence number, edge independence number and total independence number by $\alpha(G), \alpha'(G)$ and $\alpha''(G)$ respectively. This paper establishes an upper bound for $\alpha''(G)$ in terms of $\alpha(G)$, $\alpha'(G)$ and $n$. We also describe the possible structures for a total independent set containing a given number of elements.
K-Distinct Lattice Paths, Eric J. Yager, Marcus Engstrom
K-Distinct Lattice Paths, Eric J. Yager, Marcus Engstrom
Rose-Hulman Undergraduate Mathematics Journal
Lattice paths can be used to model scheduling and routing problems, and, therefore, identifying maximum sets of k-distinct paths is of general interest. We extend the work previously done by Gillman et. al. to determine the order of a maximum set of k-distinct lattice paths. In particular, we disprove a conjecture by Gillman that a greedy algorithm gives this maximum order and also refine an upper bound given by Brewer et. al. We illustrate that brute force is an inefficient method to determine the maximum order, as it has time complexity O(nk).
Utilizing Graph Thickness Heuristics On The Earth-Moon Problem, Robert C. Weaver
Utilizing Graph Thickness Heuristics On The Earth-Moon Problem, Robert C. Weaver
Rose-Hulman Undergraduate Mathematics Journal
This paper utilizes heuristic algorithms for determining graph thickness in order to attempt to find a 10-chromatic thickness-2 graph. Doing so would eliminate 9 colors as a potential solution to the Earth-moon Problem. An empirical analysis of the algorithms made by the author are provided. Additionally, the paper lists various graphs that may or nearly have a thickness of 2, which may be solutions if one can find two planar subgraphs that partition all of the graph’s edges.
The Mean Sum Of Squared Linking Numbers Of Random Piecewise-Linear Embeddings Of $K_N$, Yasmin Aguillon, Xingyu Cheng, Spencer Eddins, Pedro Morales
The Mean Sum Of Squared Linking Numbers Of Random Piecewise-Linear Embeddings Of $K_N$, Yasmin Aguillon, Xingyu Cheng, Spencer Eddins, Pedro Morales
Rose-Hulman Undergraduate Mathematics Journal
DNA and other polymer chains in confined spaces behave like closed loops. Arsuaga et al. \cite{AB} introduced the uniform random polygon model in order to better understand such loops in confined spaces using probabilistic and knot theoretical techniques, giving some classification on the mean squared linking number of such loops. Flapan and Kozai \cite{flapan2016linking} extended these techniques to find the mean sum of squared linking numbers for random linear embeddings of complete graphs $K_n$ and found it to have order $\Theta(n(n!))$. We further these ideas by inspecting random piecewise-linear embeddings of complete graphs and give introductory-level summaries of the ideas …
The Determining Number And Cost Of 2-Distinguishing Of Select Kneser Graphs, James E. Garrison
The Determining Number And Cost Of 2-Distinguishing Of Select Kneser Graphs, James E. Garrison
Rose-Hulman Undergraduate Mathematics Journal
A graph $G$ is said to be \emph{d-distinguishable} if there exists a not-necessarily proper coloring with $d$ colors such that only the trivial automorphism preserves the color classes. For a 2-distinguishing labeling, the \emph{ cost of $2$-distinguishing}, denoted $\rho(G),$ is defined as the minimum size of a color class over all $2$-distinguishing colorings of $G$. Our work also utilizes \emph{determining sets} of $G, $ sets of vertices $S \subseteq G$ such that every automorphism of $G$ is uniquely determined by its action on $S.$ The \emph{determining number} of a graph is the size of a smallest determining set. We investigate …
Iterated Jump Graphs, Fran Herr, Legrand Jones Ii
Iterated Jump Graphs, Fran Herr, Legrand Jones Ii
Rose-Hulman Undergraduate Mathematics Journal
The jump graph J(G) of a simple graph G has vertices which represent edges in G where two vertices in J(G) are adjacent if and only if the corresponding edges in G do not share an endpoint. In this paper, we examine sequences of graphs generated by iterating the jump graph operation and characterize the behavior of this sequence for all initial graphs. We build on work by Chartrand et al. who showed that a handful of jump graph sequences terminate and two sequences converge. We extend these results by showing that there are no non-trivial repeating sequences of jump …
The Chromatic Index Of Ring Graphs, Lilian Shaffer
The Chromatic Index Of Ring Graphs, Lilian Shaffer
Rose-Hulman Undergraduate Mathematics Journal
The goal of graph edge coloring is to color a graph G with as few colors as possible such that each edge receives a color and that adjacent edges, that is, different edges incident to a common vertex, receive different colors. The chromatic index, denoted χ′(G), is the minimum number of colors required for such a coloring to be possible. There are two important lower bounds for χ′(G) on every graph: maximum degree, denoted ∆(G), and density, denoted ω(G). Combining these two lower bounds, we know that every graph’s chromatic index must be at least ∆(G) or …