Discrete Mathematics and Combinatorics Commons^™

Counting Hamiltonian Cycles In Quartic Circulant Graphs, Allison Hilliard

Seaver College Research And Scholarly Achievement Symposium

We consider the problem of counting Hamiltonian cycles in circulant graphs $C_n^{1,k}$. Our method is to partition the set of Hamiltonian cycles according to their winding numbers. Then, we construct a weighted digraph that allows us to produce a generating function that counts the number of Hamiltonian cycles for each winding number. Summing these generating functions derives a formula for the total number of Hamiltonian cycles in a circulant graph with $n$ vertices.

32 - Nested Two Level Decomposition For Quantum Computing, Andrew Maciejunes, John Stenger, Dan Gunlycke, Nikos Chrisochoides

Undergraduate Research Symposium

Abstract—We present a two-level decomposition strategy for solving the Vehicle Routing Problem (VRP) using the Quantum Approximate Optimization Algorithm (QAOA). A Problem-Level Decomposition (PLD) partitions a 9-node (72-qubit) VRP into smaller Traveling Salesman Problem (TSP) instances. Each TSP is then further simplified via Circuit-Level Decomposition (CLD), enabling execution on near-term quantum devices. Our approach achieves up to 90% reductions in circuit depth and qubit count. These results demonstrate the feasibility of solving VRPs previously too complex for quantum simulators and provide early evidence of potential quantum utility.

Chain Theorems For Different Classes Of 3-Connected Graphs, Avin Sunuwar

LSU Doctoral Dissertations

This dissertation explores the structural properties of graphs by extending the classical result of Tutte's Wheel Theorem. In particular, we develop an improved version of Tutte's Wheel Theorem along with new chain theorems for subclasses of 3-connected graphs. These chain theorems provide a systematic approach to characterizing graphs that exclude certain minors, leading to significantly shorter proofs of established results.

In Chapter 5, we present a generalization of the block-tree theorem for connected graphs, which removes the restriction on cut vertices and allows greater flexibility in separator sizes. By integrating the results from Chapters 3, 4, and 5, we …

Irreversible K-Threshold Number Ck(G) And Saturation Probability P[G] For Corona Product And Double Corona Product Graphs, Eric J. Moon, Soumya Bhoumik, Paul Flesher

SACAD: Scholarly Activities

We discuss the Irreversible k-conversion process for graphs, where a vertex becomes saturated and remains saturated indefinitely if at least k of its neighbors are saturated. We investigate sets S₀, which when initially saturated, lead to complete graph saturation. We are interested in the minimum |S₀| = C_k(G), called the k-threshold number. We consider the construction of the Corona Product Graphs (of C_n and K_p). Additionally, we extend our analysis by defining and exploring Double Corona Product Graphs (of C_n and K_p). Then we incorporate …

Patterns Within The Collatz Conjecture, Kiel Harrison

SACAD: Scholarly Activities

The Collatz Conjecture, also known as 3n+1, one of the most famous unsolved problems in mathematics, has been forever out of reach of being truly solved. However, through the application of traces, there is now a new pathway forward to working out a potential solution. This study shows how this pathway was found, and what steps need to be taken to follow it.

Unavoidable Immersions And Topological Minors Of K-Edge-Connected Graphs, Brittian Qualls

LSU Doctoral Dissertations

In this work, we present results concerning the unavoidable structures in large and infinite k-edge-connected graphs. These results are inspired by the classical result of Ramsey, who proved that for every positive integer r, every sufficiently large graph contains as an induced subgraph either K_r or $\overline{K_r}$. We consider different graph containment relations, focusing primarily on the immersion relation. In the case of finite graphs, we provide the unavoidable immersions of 4-edge-connected graphs and prove that linear edge-connectivity suffices to immerse the graph C_t,r.

This dissertation also considers infinite graphs. We present the …

Robust Spacecraft Autonomy For Deep Space Exploration In Special Euclidean Group Se(3), Matthew Wittal

Doctoral Dissertations and Master's Theses

Over the past half-century, humanity has gained extensive experience conducting manned spaceflight near Earth. Arguably, "near Earth" could even include the Moon — the most distant destination humans have reached. However, "near" in this work primarily refers low Earth orbit (LEO). One could argue that we have not truly left Earth since the Apollo, as spacecraft in some LEOs remain subject to atmospheric drag thus emphasizing their continued connection to Earth's immediate environment. Reflecting on this, it becomes clear that humanity has largely remained bound to Earth’s immediate vicinity since the Apollo missions reached the Moon. However, that is set …

On Unavoidable Infinite Hypergraphs, Samuel Weiner

LSU Doctoral Dissertations

Ramsey's Theorem states that every infinite graph contains either K_∞ or $\overline{K_∞}$ as an induced subgraph. For this reason, K_∞ and $\overline{K_∞}$ are often referred to as the unavoidable infinite graphs. Many similar results have characterized the unavoidable members for various classes of infinite graphs; perhaps the most notable of these is König's Infinity Lemma, which states that every infinite, connected, locally finite graph contains a ray as an induced subgraph. From these findings, one can easily deduce that every infinite, connected graph contains an infinite clique, star, or ray as an induced subgraph; …

New View Of Some Propositions On Hesitant Fuzzy Set And Its Application In Selecting The Best Person In Any Job, Manar Mohamed Omran Dr., Arafa A. Nasef A.Dr, Reham Abd El-Aziz Abo Khadra Dr., Mahmoud Arafa Nasef Dr.

Journal of Engineering Research

An essential part of uncertainty is played by the hesitant fuzzy set (HFS). So, it can be utilized when making decisions. The suggested use of HFS to choose the best candidate for any post is thoroughly discussed and introduces new HFS concepts

Component Order Edge Connectivity, Vertex Degrees, And Integer Partitions, Michael R. Yatauro

Theory & Applications of Graphs

Given a finite, simple graph G, the k-component order connectivity (resp. edge connectivity) of G is the minimum number of vertices (resp. edges) whose removal results in a subgraph in which every component has an order of at most k − 1. In general, determining the k-component order edge connectivity of a graph is NP-hard. We identify conditions on the vertex degrees of G that can be used to imply a lower bound on the k-component order edge connectivity of G. We will discuss the process for generating such conditions for a lower bound of 1 or 2, and we …

Induced-Minor-Closed Classes Of Matroids, James Dylan Douthitt

LSU Doctoral Dissertations

A graph is chordal if every cycle of length at least four has a chord. In 1961, Dirac characterized chordal graphs as those graphs that can be built from complete graphs by repeated clique-sums. Generalizing this, we consider the class of simple GF(q)-representable matroids that can be built from projective geometries over GF(q) by repeated generalized parallel connections across projective geometries. We show that this class of matroids is closed under induced minors and characterize the class by its forbidden induced minors, noting that the case when q=2 is distinctive. Additionally, we show that the class of GF(2)-chordal matroids coincides …

The Intricacies Of Pairwise Modular Multiplicative Inverse In Lucas Numbers, Charles Liu

Rose-Hulman Undergraduate Mathematics Journal

Let (p,q) be a pair of relatively prime integers greater than 1. The pairwise modular multiplicative inverse (PMMI) of (p,q) is defined as the unique pair of positive integers (p′, q′) such that p p′ ≡ 1 (mod q), p′ < q, qq′ ≡ 1 (mod p), q′ < p. In this paper, we determine all pairs of Lucas numbers such that their PMMIs are pairs of Lucas numbers.

Discrete Math For Computer Science - Chapter 8: Union And Intersection And Complement: Set Identities, Houman Kamran Habibkhani

Pacific Open Videos

See this OER textbook full record by clicking here.

Discrete Math For Computer Science - Chapter 15: Mathematical Induction, Houman Kamran Habibkhani

Pacific Open Videos

See this OER textbook full record by clicking here.

Discrete Math For Computer Science - Chapter 13: Sequences: Recurrence Relations, Houman Kamran Habibkhani

Pacific Open Videos

See this OER textbook full record by clicking here.

Discrete Math For Computer Science - Chapter 26: Introduction To Graphs: Graph Representations, Houman Kamran Habibkhani

Pacific Open Videos

See this OER textbook full record by clicking here.

Discrete Math For Computer Science - Chapter 2: Logical Equivalence: Laws Of Propositional Logic, Houman Kamran Habibkhani

Pacific Open Videos

See this OER textbook full record by clicking here.

Discrete Math For Computer Science - Chapter 11: Inverse Of A Function: Composition Of Functions, Houman Kamran Habibkhani

Pacific Open Videos

See this OER textbook full record by clicking here.

Discrete Math For Computer Science - Chapter 16: Recursive Definitions: Recursive Algorithms, Houman Kamran Habibkhani

Pacific Open Videos

See this OER textbook full record by clicking here.

Discrete Math For Computer Science, Houman Kamran Habibkhani

Pacific Open Texts

Discrete Mathematics and its Applications is a focused introduction to the primary themes in a discrete mathematics course, as introduced through extensive applications, expansive discussion, and detailed exercise sets. These themes include mathematical reasoning, combinatorial analysis, discrete structures, algorithmic thinking, and enhanced problem-solving skills through modeling. Its intent is to demonstrate the relevance and practicality of discrete mathematics to all students.