Mathematics Commons^™

The Color Number Of Cubic Graphs Having A Spanning Tree With A Bounded Number Of Leaves, Analen A. Malnegro, Gina A. Malacas, Kenta Ozeki

Theory & Applications of Graphs

The color number c(G) of a cubic graphG is the minimum cardinality of a color class of a proper 4-edge-coloring of G. It is well-known that every cubic graph G satisfies c(G) = 0 if G

The Structure Of Functional Graphs For Functions From A Finite Domain To Itself For Which A Half Iterate Exists, Paweł Marcin Kozyra

Theory & Applications of Graphs

The notion of a replica of a nontrivial in-tree is defined. A result enabling to determine whether an in-tree is a replica of another in-tree employing an injective mapping between some subsets of sources of these in-trees is presented. There are given necessary and sufficient conditions for the existence of a functional square root of a function from a finite set to itself through presenting necessary and sufficient conditions for the existence of a square root of a component of the functional graph for the function and for the existence of a square root of the union of two components …

Classification Of Cayley Rose Window Graphs, Angsuman Das, Arnab Mandal

Theory & Applications of Graphs

Rose window graphs are a family of tetravalent graphs, introduced by Steve Wilson. Following it, Kovacs, Kutnar and Marusic classified the edge-transitive rose window graphs and Dobson, Kovacs and Miklavic characterized the vertex transitive rose window graphs. In this paper, we classify the Cayley rose window graphs.

Reducing The Maximum Degree Of A Graph: Comparisons Of Bounds, Peter Borg

Theory & Applications of Graphs

Let λ(G) be the smallest number of vertices that can be removed from a non-empty graph G so that the resulting graph has a smaller maximum degree. Let λ_e(G) be the smallest number of edges that can be removed from G for the same purpose. Let k be the maximum degree of G, let t be the number of vertices of degree k, let M(G) be the set of vertices of degree k, let n be the number of vertices in the closed neighbourhood of M(G), and let m be the …

Teacher Educators Learning With Prospective Teachers: Finding Relevant Mathematics In Our (Their) Lives, Lindsay M. Keazer, Eryn Stehr Maher

Mathematical Sciences: Faculty Publications

Two mathematics teacher educators (MTEs) discuss the mathematical contexts generated by prospective teachers (PTs) when pushed to look for relevant mathematics in their lives and communities. Through collaborative teacher action research focused on iterations of collecting, categorizing, and discussing PTs’ mathematical contexts, and posing selected examples for PTs’ own examination, layers of learning occurred for both PTs and MTEs. PTs began to craft more personalized, story-like contexts, seemingly noticing more mathematics in their lives. MTEs were unexpectedly pushed to clarify their thinking about what it means to develop contexts that are authentic and relevant, and to contemplate how their actions …

The Conditional Strong Matching Preclusion Of Augmented Cubes, Mohamad Abdallah, Eddie Cheng

Theory & Applications of Graphs

The strong matching preclusion is a measure for the robustness of interconnection networks in the presence of node and/or link failures. However, in the case of random link and/or node failures, it is unlikely to find all the faults incident and/or adjacent to the same vertex. This motivates Park et al. to introduce the conditional strong matching preclusion of a graph. In this paper we consider the conditional strong matching preclusion problem of the augmented cube AQ_n, which is a variation of the hypercube Q_n that possesses favorable properties.

Characterizing 2-Trees Relative To Chordal And Series-Parallel Graphs, Terry A. Mckee

Theory & Applications of Graphs

The 2-connected 2-tree graphs are defined as being constructible from a single 3-cycle by recursively appending new degree-2 vertices so as to form 3-cycles that have unique edges in common with the existing graph. Such 2-trees can be characterized both as the edge-minimal chordal graphs and also as the edge-maximal series-parallel graphs. These are also precisely the 2-connected graphs that are simultaneously chordal and series-parallel, where these latter two better-known types of graphs have themselves been both characterized and applied in numerous ways that are unmotivated by their interaction with 2-trees and with each other.

Toward providing such motivation, the …

Designing Efficient Algorithms For Sensor Placement, Gabriel Loos

Honors College Theses

Sensor placement has many applications and uses that can be seen everywhere you go.These include, but not limited to, monitoring the structural health of buildings and bridgesand navigating Unmanned Aerial Vehicles(UAV).We study ways that leads to efficient algorithms that will place as few as possible sen-sors to cover an entire area. We will tackle the problem from both 2-dimensional and3-dimensional points of view. Two famous related problems are discussed: the art galleryproblem and the terrain guarding problem. From the top view an area presents a 2-D im-age which will enable us to partition polygonal shapes and use graph theoretical results …

An Efficient Algorithm To Test Potential Bipartiteness Of Graphical Degree Sequences, Kai Wang

Theory & Applications of Graphs

As a partial answer to a question of Rao, a deterministic and customizable efficient algorithm is presented to test whether an arbitrary graphical degree sequence has a bipartite realization. The algorithm can be configured to run in polynomial time, at the expense of possibly producing an erroneous output on some ``yes'' instances but with very low error rate.

Nilpotent Graph, Dhiren Kumar Basnet, Ajay Sharma, Rahul Dutta

Theory & Applications of Graphs

In this article, we introduce the concept of nilpotent graph of a finite commutative ring. The set of all non nilpotent elements of a ring is taken as the vertex set and two vertices are adjacent if and only if their sum is nilpotent. We discuss some graph theoretic properties of nilpotent graph.

The Integer-Antimagic Spectra Of Graphs With A Chord, Richard M. Low, Dan Roberts, Jinze Zheng

Theory & Applications of Graphs

Let Α be a nontrival abelian group. A connected simple graph G = (V, E) is Α-antimagic if there exists an edge labeling f: E(G) → A \ {0} such that the induced vertex labeling f+: V(G) → Α, defined by f+(v) = Σ_{{uv ∈ E(G)} f(uv), is injective. The integer-antimagic spectrum of a graph G is the set IAM(G) = {k |G is {Ζ}_k-antimagic} and k ≥2. In this paper, we determine the integer-antimagic spectra for cycles with a chord, paths with a chord, and wheels with a chord.

Numerical Approximation Of Lyapunov Exponents And Its Applications In Control Systems, Nakita K. Andrews

College of Graduate Studies: Theses & Dissertations

The progression of state trajectories with respect to time, and its stability properties can be described by a system of nonlinear differential equations. However, since most nonlinear dynamical systems cannot be solved by hand, one must rely on computer simulations to observe the behavior of the system. This work focuses on chaotic systems. The Lyapunov Exponent (LE) is frequently used in the quantitative studies of a chaotic system. Lyapunov exponents give the average rate of separation of nearby orbits in phase space, which can be used to determine the state of a system, e.g. stable or unstable. The objective of …

Addendum For The Article Radio Graceful Labelling Of Graphs, Laxman Saha, Alamgir Rahaman Basunia

Theory & Applications of Graphs

Additional references listed for the article: Saha, Laxman and Basunia, Alamgir Rahaman (2020) "Radio Graceful Labelling of Graphs," Theory and Applications of Graphs: Vol. 7: Iss. 1, Article 7. DOI: 10.20429/tag.2020.070107

A Nonlinear Multi-Population Behavioral Model To Assess The Roles Of Education Campaigns, Random Supply Of Aids, And Delayed Art Treatment In Hiv/Aids Epidemics, Divine Wanduku

Mathematical Sciences: Faculty Publications

The successful reduction in prevalence rates of HIV in many countries is attributed to control measures such as information and education campaigns (IEC), antiretroviral therapy (ART), and national, multinational and multilateral support providing offcial developmental assistance (ODAs) to combat HIV. However, control of HIV epidemics can be interrupted by limited random supply of ODAs, high poverty rates and low living standards. This study presents a stochastic HIV/AIDS model with treatment assessing the roles of IEC, the supply of ODAs and early treatment in HIV epidemics. The supply of ODAs is assessed via the availability of medical and financial resources leading …

Isomorphism Of Trees And Isometry Of Ultrametric Spaces, Oleksiy Dovgoshey

Theory & Applications of Graphs

We study the conditions under which the isometry of spaces with metrics generated by weights given on the edges of finite trees is equivalent to the isomorphism of these trees. Similar questions are studied for ultrametric spaces generated by labelings given on the vertices of trees. The obtained results generalized some facts previously known for phylogenetic trees and for Gurvich---Vyalyi monotone trees.

Decomposition Of Certain Complete Graphs And Complete Multipartite Graphs Into Almost-Bipartite Graphs And Bipartite Graphs, G. Sethuraman, M. Sujasree

Theory & Applications of Graphs

In his classical paper [14], Rosa introduced a hierarchical series of labelings called ρ, σ, β and α labeling as a tool to settle Ringel’s Conjecture which states that if T is any tree with m edges then the complete graph K2m+1 can be decomposed into 2m + 1 copies of T . Inspired by the result of Rosa [14] many researchers significantly contributed to the theory of graph decomposition using graph labeling. In this direction, in 2004, Blinco et al. [6] introduced γ-labeling as a stronger version of ρ-labeling. A function g defined on the vertex set …

Laplacian Spectral Properties Of Signed Circular Caterpillars, Maurizio Brunetti

Theory & Applications of Graphs

A circular caterpillar of girth n is a graph such that the removal of all pendant vertices yields a cycle C_n of order n. A signed graph is a pair Γ =(G,σ), where G is a simple graph and σ: E(G) →{+1, -1} is the sign function defined on the set E(G) of edges of G. The signed graph Γ is said to be balanced if the number of negatively signed edges in each cycle is even, and it is said to be unbalanced otherwise. We determine some bounds for the first n Laplacian eigenvalues …

The Burning Number Of Directed Graphs: Bounds And Computational Complexity, Remie Janssen

Theory & Applications of Graphs

The burning number of a graph was recently introduced by Bonato et al. Although they mention that the burning number generalizes naturally to directed graphs, no further research on this has been done. Here, we introduce graph burning for directed graphs, and we study bounds for the corresponding burning number and the hardness of finding this number. We derive sharp bounds from simple algorithms and examples. The hardness question yields more surprising results: finding the burning number of a directed tree with one indegree-0 node is NP-hard, but FPT; however, it is W[2]-complete for DAGs. Finally, we give a fixed-parameter …

Radio Graceful Labelling Of Graphs, Laxman Saha, Alamgir Rahaman Basunia

Theory & Applications of Graphs

Radio labelling problem of graphs have their roots in communication problem known as Channel Assignment Problem. For a simple connected graph G=(V(G), E(G)), a radio labeling is a mapping f : V(G) →{0,1,2,…} such that |f(u)-f(v)|≥ diam(G)+1-d(u,v) for each pair of distinct vertices u,v ∈ V(G), where diam(G) is the diameter of G and d(u,v) is the distance between u and v. A radio labeling f of a graph G is a radio graceful labeling of G if f(V(G)) = {0,1,… |V(G)|-1}. A graph for which a radio graceful labeling exists is called radio graceful. …

Domination Number Of Annulus Triangulations, Toshiki Abe, Junki Higa, Shin-Ichi Tokunaga

Theory & Applications of Graphs

An annulus triangulation G is a 2-connected plane graph with two disjoint faces f₁ and f₂ such that every face other than f₁ and f₂ are triangular, and that every vertex of G is contained in the boundary cycle of f₁ or f₂. In this paper, we prove that every annulus triangulation G with t vertices of degree 2 has a dominating set with cardinality at most ⌊ \frac{|V(G)|+t+1}{4} ⌋ if G is not isomorphic to the octahedron. In particular, this bound is best possible.

Some Asymptotic Properties Of Seirs Models Withnonlinear Incidence And Random Delays, Divine Wanduku, Broderick O. Oluyede

Mathematical Sciences: Faculty Publications

This paper presents the dynamics of mosquitoes and humans with general nonlinear incidence rate and multiple distributed delays for the disease. The model is a SEIRS system of delay differential equations. The normalized dimensionless version is derived; analytical techniques are applied to find conditions for deterministic extinction and permanence of disease. The BRN R0* and ESPR E(e–(μvT1+μT2)) are computed. Conditions for deterministic extinction and permanence are expressed in terms of R0* and E(e–(μvT1+μT2)) and applied to a P. vivax malaria scenario. Numerical results are given.

An Improvement In The Two-Packing Bound Related To Vizing's Conjecture, Kimber Wolff

Theory & Applications of Graphs

Vizing's conjecture states that the domination number of the Cartesian product of graphs is at least the product of the domination numbers of the two factor graphs. In this note we improve the recent bound of Breŝar by applying a technique of Zerbib to show that for any graphs G and H, γ(G x H)≥ γ (G) 2/3(γ(H)-ρ(H)+1), where γ is the domination number, ρ is the 2-packing number, and x is the Cartesian product.

On A Vizing-Type Integer Domination Conjecture, Elliot Krop, Randy R. Davila

Theory & Applications of Graphs

Given a simple graph G, a dominating set in G is a set of vertices S such that every vertex not in S has a neighbor in S. Denote the domination number, which is the size of any minimum dominating set of G, by γ(G). For any integer k ≥ 1, a function f : V (G) → {0, 1, . . ., k} is called a {k}-dominating function if the sum of its function values over any closed neighborhood is at least k. The weight of a {k}-dominating function is the sum of its values over all …

Recursive Formulas For Beans Functions Of Graphs, Kengo Enami, Seiya Negami

Theory & Applications of Graphs

In this paper, we regard each edge of a connected graph G as a line segment having a unit length, and focus on not only the "vertices" but also any "point" lying along such a line segment. So we can define the distance between two points on G as the length of a shortest curve joining them along G. The beans function B_G(x) of a connected graph G is defined as the maximum number of points on G such that any pair of points have distance at least x>0. We shall show a recursive formula for …

Triangles In Ks-Saturated Graphs With Minimum Degree T, Craig Timmons, Benjamin Cole, Albert Curry, David Davini

Theory & Applications of Graphs

For n ≥ 15, we prove that the minimum number of triangles in an n-vertex K₄-saturated graph with minimum degree 4 is exactly 2n-4, and that there is a unique extremal graph. This is a triangle version of a result of Alon, Erdos, Holzman, and Krivelevich from 1996. Additionally, we show that for any s > r ≥ 3 and t ≥ 2 (s-2)+1, there is a K_s-saturated n-vertex graph with minimum degree t that has \binom{ s-2}{r-1}2^{r-1} n + c_{s,r,t} copies of K_r. This shows that …

Graham's Pebbling Conjecture Holds For The Product Of A Graph And A Sufficiently Large Complete Graph, Nopparat Pleanmani

Theory & Applications of Graphs

For connected graphs G and H, Graham conjectured that π(G □ H) ≤ π(G) π(H) where π(G), π (H), and π(G □ H) are the pebbling numbers of G, H, and the Cartesian product G □ H, respectively. In this paper, we show that the inequality holds when H is a complete graph of sufficiently large order in terms of graph parameters of G.

Analysis On Sharp And Smooth Interface, Elizabeth V. Hawkins

College of Graduate Studies: Theses & Dissertations

In biology, minimizing a free energy functional gives an equilibrium shape that is the most stable in nature. The formulation of these functionals can vary in many ways, in particular they can have either a smooth or sharp interface. Minimizing a functional can be done through variational calculus or can be proved to exist using various analysis techniques. The functionals investigated here have a smooth and sharp interface and are analyzed using analysis and variational calculus respectively. From the former we find the condition for extremum and its second variation. The second variation is commonly used to analyze stability of …

Explicit Pseudo-Kähler Metrics On Flag Manifolds, Thomas A. Mason Iii

College of Graduate Studies: Theses & Dissertations

The coadjoint orbits of compact Lie groups each carry a canonical (positive definite) Kähler structure, famously used to realize the group's irreducible representations in holomorphic sections of certain line bundles (Borel-Weil theorem). Less well-known are the (indefinite) invariant pseudo-Kähler structures they also admit, which can be used to realize the same representations in higher cohomology of the sections (Bott), and whose analogues in a non-compact setting lead to new representations (Kostant-Langlands). The purpose of this thesis is to give an explicit description of these metrics in the case of the unitary group G=U_n.

Artificial Neural Network Models For Pattern Discovery From Ecg Time Series, Mehakpreet Kaur

College of Graduate Studies: Theses & Dissertations

Artificial Neural Network (ANN) models have recently become de facto models for deep learning with a wide range of applications spanning from scientific fields such as computer vision, physics, biology, medicine to social life (suggesting preferred movies, shopping lists, etc.). Due to advancements in computer technology and the increased practice of Artificial Intelligence (AI) in medicine and biological research, ANNs have been extensively applied not only to provide quick information about diseases, but also to make diagnostics accurate and cost-effective. We propose an ANN-based model to analyze a patient's electrocardiogram (ECG) data and produce accurate diagnostics regarding possible heart diseases …

Reduced Dataset Neural Network Model For Manuscript Character Recognition, Mohammad Anwarul Islam

College of Graduate Studies: Theses & Dissertations

The automatic character recognition task has been of practical interest for a long time. Nowadays, there are well-established technologies and software to perform character recognition accurately from scanned documents. Although handwritten character recognition from the manuscript image is challenging, the advancement of modern machine learning techniques makes it astonishingly manageable. The problem of accurately recognizing handwritten character remains of high practical interest since a large number of manuscripts are currently not digitized, and hence inaccessible to the public. We create our repository of the datasets by cropping each letter image manually from the manuscript images. The availability of datasets is …