Mathematics Commons^™

Obstructions To Some Injective Oriented Colourings, Russell J. Campbell, Nancy E. Clarke, Gary Macgillivray

Theory & Applications of Graphs

Each of several possible definitions of local injectivity for a homomorphism of an oriented graph $G$ to an oriented graph $H$ leads to an injective oriented colouring problem. For each case in which such a problem is solvable in polynomial time, we identify a set $\mathcal{F}$ of oriented graphs such that an oriented graph $G$ has an injective oriented colouring with the given number of colours if and only if there is no $F \in \mathcal{F}$ for which there is a locally-injective homomorphism of $F$ to $G$.

The Connected Vertex Cover In Graphs, Kamran Mirasheh, Elham Mirashe, Ebrahim Vatandoost

Theory & Applications of Graphs

This paper presents tight bounds and characterizations for the vertex cover number and the connected vertex cover number of graphs. In particular, we identify all graphs for which βc(G) = |V (G)| − 1, proving that these are exactly the cycles and complete graphs. The analysis employs tools such as the degree matrix and the Rayleigh quotient to derive new and sharp upper bounds.

The $K$-Total Bondage Number Of A Graph, Jean-Pierre Appel, Gabrielle Fischberg, Kyle Kelley, Nathan B. Shank, Eliel Sosis

Theory & Applications of Graphs

Let \(G=(V,E)\) be a connected, finite undirected graph. A set \(S \subseteq V\) is said to be a total dominating set of \(G\) if every vertex in \(V\) is adjacent to some vertex in \(S\). The total domination number, \(\gamma_{t}(G)\), is the minimum cardinality of a total dominating set in \(G\). We define the \(k\)-total bondage of $G$ to be the minimum number of edges to remove from \(G\) so that the resulting graph has a total domination number at least \(k\) more than \(\gamma_{t}(G)\). In this work we establish general properties of \(k\)-total bondage and find exact values for …

Hyper Face-Magic Graphs, Ross Belgram, Donald Mcginn

Theory & Applications of Graphs

For a planar graph G of order n, let F(G) be the set of all faces of G embedded into R 2 , including the exterior face. A bijective vertex labeling f : V (G) → {1, 2, ..., n} induces a face labeling f ∗ : F(G) → N defined by setting f ∗ (F) equal to the sum of all labels of the boundary vertices of F. The graph G is said to be hyper face-magic if there exists a vertex labeling whose induced face labeling is constant. In this paper, we state properties of hyper face-magic graphs …

On The Extreme Complexity Of Certain Nearly Regular Graphs, Gregory P. Constantine, Gregory C. Magda

Theory & Applications of Graphs

The complexity of a graph is the number of its labeled spanning trees. It is demonstrated that the seven known triangle-free strongly regular graphs are graphs of maximal complexity among all graphs of the same order and degree; their complements are shown to be of minimal complexity. A generalization to nearly regular graphs with two distinct eigenvalues of the Laplacian is presented. Conjectures and applications of these results to biological problems on neuronal activity are described.

Cycle-Based Characterizations Of The Cycle Completable Graphs, Terry A. Mckee

Theory & Applications of Graphs

Cycle completable graphs were originally defined to answer matrix completion problems and have since received diverse graph-theoretic descriptions, in spite of not directly mentioning cycles. This paper characterizes such graphs by their chordless cycles never having ``bridges'' (as defined in H.-J. Voss's 1991 monograph {\em Cycles and Bridges in Graphs\/}) that have more than two vertices of attachment in the cycle. This approach is then related to the well-studied, yet seemingly quite distinct, classes of chordal graphs and series-parallel graphs. This is done by allowing chords to be ``bridges'' that have exactly two vertices of attachment.

When The Gorenstein Projective Modules Are Precovering: A Survey On The Existence Of The Gorenstein Projective Precovers, Alexis L. Mcburney

College of Graduate Studies: Theses & Dissertations

This thesis surveys known results on the existence of Gorenstein projective precovers and studies conditions under which the class of Gorenstein projective modules is precovering. In classical homological algebra, projective resolutions are used to study modules, while relative homological algebra replaces projective modules with a different class that must be precovering for resolutions to exist. Gorenstein homological algebra extends these ideas using Gorenstein projective modules. We review key developments by Jorgensen, Murfet and Salarian, Estrada, Iacob, and Yeomans, and Cortés and Saroch. We discuss the strongest known existence result, showing that Gorenstein projective precovers exist under suitable conditions; in particular, …

Forbidden Triples For $2$-Connected Graphs With Minimum Degree Three Which Contain $K_4$ And $K_{2,2}$, Takafumi Kotani, Yoshimi Egawa

Theory & Applications of Graphs

For a family $\mathcal{H}$ of graphs, a graph $G$ is said to be $\mathcal{H}$-free if $G$ contains no member of $\mathcal{H}$ as an induced subgraph. Let $\mathcal{G}_2^{(3)}}(\mathcal{H})$ denote the family of $2$-connected $\mathcal{H}$-free graphs having minimum degree at least $3$. This paper is concerned with families $\mathcal{H}$ of connected graphs with $|\mathcal{H}| = 3$ such that $\mathcal{G}_2^{(3)}}(\mathcal{H})$ is a finite family. In particular, we show that for a connected graph $T$ of order at least $3$ that is not a star, $\mathcal{G}_2^{(3)}(\{K_4,K_{2,2},T\})$ is finite if and only if $T$ is a path of order at most $6$.

Star-Critical Weakened Ramsey Numbers, Mark R. Budden, Monu Moun, Jagjeet Jakhar

Theory & Applications of Graphs

The weakened Ramsey number $r^{s,t}(G)$ is defined to be the least $p\in \mathbb{N}$ such that every $t$-coloring of the edges of the complete graph $K_p$ contains a subgraph isomorphic to $G$ that is spanned by edges that use at most $s$ colors ($1\le s\le t-1$). The star-critical weakened Ramsey number $r^{s,t}_*(G)$ then determines the minimum number of edges that must join a vertex to $K_{r^{s,t}(G)-1}$ in order for this Ramsey property to hold. We begin by showing that $r_*^{s,t}(K_n)=r^{s,t}(K_n)-1$ for all $n\in \mathbb{N}$. Then, building off of Khamseh and Omidi's recent determination of $r^{s,t}(K_{1,n})$ when $s=t-1$ and $s=t-2$, we focus …

Packing Independent Cliques Into Planar Graphs, Csaba Biró, Gabriel Collado, Oscar Zamora

Theory & Applications of Graphs

The indeque number of a graph is largest set of vertices that induce an independent set of cliques. We study the extremal value of this parameter for the class and subclasses of planar graphs, most notably for forests and graphs of pathwidth at most $2$.

Corrigendum To "Face-Magic Labelings Of Polygonal Graphs", Wai Chee Shiu, Richard M. Low, Andy K. Liu

Theory & Applications of Graphs

In this note, we correct a misstatement of a theorem.

Degeneracies Of Triangulated Graphs, Allan Bickle

Theory & Applications of Graphs

A graph $G$ is $k$-degenerate if each subgraph has minimum degree

at most $k$. The degeneracy\textbf{ }$D\left(G\right)$ is the smallest

$k$ such that $G$ is $k$-degenerate. We determine the truth values

of four statements (using different quantifiers) about when a planar

graph $G$ with degeneracy $k$ has a triangulation with degeneracy

$l$. We characterize which 3-connected planar graphs can only be

triangulated to degeneracy 3. Then we consider analogous questions

for maximal planar bipartite graphs. We prove some structural results

on these graphs, including results on decomposition of planar graphs

into various types of bipartite graphs.

Skolem Number Of Kagome Lattice Graphs, Braxton Carrigan, Max Martone

Theory & Applications of Graphs

A proper Skolem labelling of a graph $G$ is a function assigning a positive integer to each vertex of $G$ such that any two vertices assigned the same integer are that distance apart in the graph. The Skolem number of a graph is smallest number $n$ such that there exists a proper Skolem labelling only using the positive integers less than or equal to $n$. In this paper, we will begin by proving the Skolem number for another family of subgraphs of the hexagonal lattice and then prove the Skolem number for two families of subgraphs of the Kagome Lattice.

Lower Bounds For The Total Distance $K$-Domination Number Of A Graph, Randy R. Davila

Theory & Applications of Graphs

For $k \geq 1$ and a graph $G$ without isolated vertices, a \emph{total distance $k$-dominating set} of $G$ is a set of vertices $S \subseteq V(G)$ such that every vertex in $G$ is within distance $k$ to some vertex of $S$ other than itself. The \emph{total distance $k$-domination number} of $G$ is the minimum cardinality of a total $k$-dominating set in $G$ and is denoted by $\gamma_{k}^t(G)$. When $k=1$, the total $k$-domination number reduces to the \emph{total domination number}, written $\gamma_t(G)$; that is, $\gamma_t(G) = \gamma_{1}^t(G)$. This paper shows that several known lower bounds on the total domination number generalize …

The Integer-Antimagic Spectra Of A Weak Join Of Hamiltonian Graphs, Ugur Odabasi, Dan Roberts, Richard M. Low

Theory & Applications of Graphs

A simple graph $G$ with vertex set $V(G)$ and edge set $E(G)$ is \emph{$\mathbb{Z}_{k}$-antimagic} if there exists a function $f: E(G) \to \mathbb{Z}_{k} \backslash \{0\}$ such that the induced function $f^+(v)=\sum_{uv\in E(G)} f(uv)$ is injective. The \textit{integer-antimagic spectrum} of a graph $G$ is the set IAM$(G) = \{k: G \textnormal{ is } \mathbb{Z}_k\textnormal{-antimagic and } k \geq 2\}$. A \emph{weak join} of vertex-disjoint graphs is the collection of the graphs with additional simple edges (possibly none) between the original graphs. In this paper, we characterize IAM$(H)$ where $H$ is a weak join of Hamiltonian graphs.

Prime Labelings On A 3xn Grid Graph, Stephen J. Curran, Matt A. Ollis

Theory & Applications of Graphs

It is conjectured that the mxn grid graph has a prime labeling for all positive integers m and n. It is known that for any prime p and any integer n such that 1≤n≤p², there exists a prime labeling on the pxn grid graph P_m x P_n. Also, it is known that the ladder P₂ x P_n has a prime labeling for all positive integers n. We assume that Goldbach's Even Conjecture and a strengthened variant of Lemoine's Conjecture are true in order to show that the 3xn grid graph P …

All Graphs Of Order N With Distinguishing Number N−1 Or N − 2, Andi Pujo Rahadi, Edy Tri Baskoro, Suhadi Wido Saputro

Theory & Applications of Graphs

Let G be a simple connected graph. The distinguishing number of G, denoted by D(G), is the least integer d such that G has a vertex d-labeling preserved only by the trivial automorphism. In this paper, we characterize all graphs of order n with distinguishing number n − 1, or n − 2.

Combinatorial Rigidity And Flexibility Of Simplicial 2-Complexes With Few Vertices, Serge A. Lawrence, Abdulkarim M. Magomedov, Olga I. Chelyapina, Valentina M. Rudenko

Theory & Applications of Graphs

We study the problem of reconstruction of a simplicial 2-complex from its 1- skeleton together with the prescribed quantities of 2-simplices at each 1-simplex, under the restriction that these quantities are bounded above by 2. It is a known fact that a 2-complex is uniquely reconstructible, or “combinatorially rigid”, if it has 5 or fewer vertices. In this paper “combinatorially flexible” 2-complexes (that is, non-uniquely reconstructible from their 1-skeletons) with 6 vertices are characterized in terms of necessary 2-subcomplexes.

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 …

Face-Magic Labelings Of Polygonal Graphs, Wai Chee Shiu, Richard M. Low, Andy K. Liu

Theory & Applications of Graphs

For a plane graph $G = (V, E)$ embedded in $\mathbb{R}^2$, let $\mathcal{F}(G)$ denote the set of faces of $G$. Then, $G$ is called a \textit{$C_n$-face-magic graph} if there exists a bijection $f: V(G) \to \{1, 2, \dots, |V(G)|\}$ such that for any $F \in \mathcal{F}(G)$ with $F \cong C_n$, the sum of all the vertex labels along $C_n$ is a constant $c$. In this paper, we investigate face-magic labelings of polygonal graphs.

A Characterization Of Chordal Graph Without Sun And Co-Rising Sun As Convex Geometry, Silvia B. Tondato

Theory & Applications of Graphs

In this paper we introduce the notion of $t_3$ \textit{convexity}, a natural restriction of triangle convexity. A \textit{triangle path} is a path allowing just short chords. A triangle path $P$ between two non-adjacent vertices in a graph $G$ is called $t_3$ \textit{path} if the first vertex of $P$ is among vertices from $P$ adjacent only to the second vertex of $P$, and the last vertex of $P$ is among vertices from $P$ adjacent only to the second-last vertex of $P$. A set $S \subseteq V(G)$ is $t_3$ \textit{convex} if for any two non-adjacent vertices $x, y \in S$ any vertex …

Failed Zero Forcing Numbers Of Trees And Circulant Graphs, Luis Gomez, Karla Rubi, Jorden Terrazas, Rigoberto Florez, Darren A. Narayan

Theory & Applications of Graphs

Given a graph $G$, the zero forcing number of $G$, $Z(G)$, is the smallest cardinality of any set $S$ of vertices on which repeated applications of the forcing rule (described below) results in all vertices being in $S$. The forcing rule is as follows: if a vertex $v$ is in $S$, and exactly one neighbor $u$ of $v$ is not in $S$, then $u$ is added to $S$ in the next iteration. Zero forcing numbers have attracted great interest over the past 15 years and have been well studied. The zero forcing number is used to study the maximum nullity/minimum …

Machine Learning Methods For Intrusion Detection And Response In Network Security, Ayomide Oyemaja

College of Graduate Studies: Theses & Dissertations

Intrusion Detection Systems (IDS) play a crucial role in computer network security by identifying malicious activities and potential cyberattacks. This thesis combines machine learning and cybersecurity by applying Reinforcement Learning (RL) in intrusion detection and response using the NSL-KDD dataset.

We designed and implemented a Q-learning framework where an agent learns to classify network traffic over time by interacting with the environment and receiving rewards based on detection accuracy. We also look at the importance of feature selection and classification techniques and how effective they are in improving model performance, reducing the complexity of computation, and producing more desirable results. …

Towards A Baker-Campbell-Hausdorff Theorem In Positive Characteristic, Nikolas A. Koutroulakis

College of Graduate Studies: Theses & Dissertations

We investigate whether there is an analog of the Baker-Campbell-Hausdorff (BCH) theorem for Lie algebras over fields of positive characteristic. We begin by introducing the proof of the BCH formula in characteristic zero. We then introduce the Artin-Hasse exponential and show that it is $p$-integral. Our main result provides sufficient conditions under which a BCH-type formula exists for the Artin-Hasse exponential in positive characteristic. Additionally, we derive a formula for computing an inverse of the Artin-Hasse exponential.

Gorenstein Flat Preenvelopes Over Coherent Rings, Alec Moore

College of Graduate Studies: Theses & Dissertations

The existence of precovers and preenvelopes of Gorenstein flat modules is of great interest in the field of Gorenstein homological algebra. We give a sufficient condition in order for the class of Gorenstein flat modules to be preenveloping. More precisely, we prove that if the ring R is coherent such that every injective module has finite flat dimension, then every R-module has a Gorenstein flat preenvelope.

On The Combinatorial Invariance For Kazhdan-Lusztig Polynomials, Grover C. Harrell Iii

College of Graduate Studies: Theses & Dissertations

This thesis will be a discussion on the Combinatorial Invariance Conjecture for Kazhdan Lusztig polynomials. The conjecture is widely suspected to be true; and there is an abun dance of computational evidence which supports it. Despite this, no complete proof has been discovered for more than forty years. We will explore some known results about the CIC, particularly those by Dyer, Incitti, Brenti, Caselli, and Marietti.

Apex Graphs And Cographs, Jagdeep Singh, Vaidy Sivaraman, Thomas Zaslavsky

Theory & Applications of Graphs

A class G of graphs is called hereditary if it is closed under taking induced subgraphs. We denote by G^{apex} the class of graphs G that contain a vertex v such that G − v is in G. Borowiecki, Drgas-Burchardt, and Sidorowicz proved that if a hereditary class G has finitely many forbidden induced subgraphs, then so does G^{apex}. We provide an elementary proof of this result.

The hereditary class of cographs consists of all graphs G that can be generated from K_1 using complementation and disjoint union. A graph is an apex cograph if it contains a …

Balanced N-Color Compositions, Jesus Omar Sistos Barron, Hua Wang

Mathematical Sciences: Faculty Publications

We introduce the notion of balanced n-color compositions, and consider the related enumeration problems. We also establish bijections with four other combinatorial objects, namely two types of Motzkin lattice paths, pairs of regular compositions with restricted parts, and regular compositions with a centered maximum.

Approval Gap Of Weighted K-Majority Tournaments, Jeremy Coste, Breeann Flesch, Joshua D. Laison, Erin Mcnicholas, Dane Miyata

Theory & Applications of Graphs

A $k$-majority tournament $T$ on a finite set of vertices $V$ is defined by a set of $2k-1$ linear orders on $V$, with an edge $u \to v$ in $T$ if $u>v$ in a majority of the linear orders. We think of the linear orders as voter preferences and the vertices of $T$ as candidates, with an edge $u \to v$ in $T$ if a majority of voters prefer candidate $u$ to candidate $v$. In this paper we introduce weighted $k$-majority tournaments, with each edge $u \to v$ weighted by the number of voters preferring $u$.

We define the …

Strongly I-Bicritical Graphs, Michelle Edwards, Gary Macgillivray, Shahla Nasserasr

Theory & Applications of Graphs

A graph $G$ is \emph{strongly $i$-bicritical} if it has independent domination number $i(G) \geq 3$, and $i(G - \{x, y\}) = i(G) - 2$ whenever $x$ and $y$ are two non-adjacent vertices of $G$. We describe five constructions of strongly $i$-bicritical graphs. For four of them, necessary and sufficient conditions for the graph produced by the construction to be strongly $i$-bicritical are given. The strongly $i$-bicritical graphs with independent domination number $i(G) = 3$ are characterized, and it is shown that the strongly $i$-bicritical graphs with independent domination number $i(G) \geq 5$ may be hard to characterize. It is shown …