Discrete Mathematics and Combinatorics Commons^™

Policy-Preferred Paths In As-Level Internet Topology Graphs, Mehmet Engin Tozal

Theory & Applications of Graphs

Using Autonomous System (AS) level Internet topology maps to determine accurate AS-level paths is essential for network diagnostics, performance optimization, security enforcement, business policy management and topology-aware application development. One significant drawback that we have observed in many studies is simplifying the AS-level topology map of the Internet to an undirected graph, and then using the hop distance as a means to find the shortest paths between the ASes. A less significant drawback is restricting the shortest paths to only valley-free paths. Both approaches usually inflate the number of paths between ASes; introduce erroneous paths that do not conform to …

Traveling In Networks With Blinking Nodes, Braxton Carrigan, James Hammer

Theory & Applications of Graphs

We say that a blinking node system modulo n is an ordered pair (G,L) where G is a graph and L is an on-labelling which indicates when vertices can be visited. An On-Hamiltonian walk is a sequence of all the vertices of G such that the position of each vertex modulo n is an integer of the label of that vertex. This paper will primarily investigate finding the shortest On-Hamiltonian walks in a blinking node system on complete graphs and complete bipartite graphs but also establishes the terminology and initial observations for working with blinking node systems on other graphs.

Sparse Trees With A Given Degree Sequence, Ao Shen

College of Graduate Studies: Theses & Dissertations

In this thesis, we consider the properties of sparse trees and summarized a certain class of trees under some constraint (including with a given degree sequence, with given number of leaves, with given maximum degree, etc.) which have maximum Wiener index and the minimum number of subtrees at the same time. Wiener index is one of the most important topological indices in chemical graph theory. Steiner k�� Wiener index can be regarded as the generalization of Wiener index, when k = 2, Steiner Wiener index is the same as Wiener index. Steiner k�� Wiener index of a tree T is …

Generalized Matching Preclusion In Bipartite Graphs, Zachary Wheeler, Eddie Cheng, Dana Ferranti, Laszlo Liptak, Karthik Nataraj

Theory & Applications of Graphs

The matching preclusion number of a graph with an even number of vertices is the minimum number of edges whose deletion results in a graph that has no perfect matchings. For many interconnection networks, the optimal such sets are precisely sets of edges incident to a single vertex. The conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond these, and it is defined as the minimum number of edges whose deletion results in a graph with neither isolated vertices nor perfect matchings. In this paper we generalize this concept to get a hierarchy of …

A General Lower Bound On Gallai-Ramsey Numbers For Non-Bipartite Graphs, Colton Magnant

Theory & Applications of Graphs

Given a graph H and a positive integer k, the k-color Gallai-Ramsey number gr_k(K3 : H) is defined to be the minimum number of vertices n for which any k-coloring of the complete graph K_n contains either a rainbow triangle or a monochromatic copy of H. The behavior of these numbers is rather well understood when H is bipartite but when H is not bipartite, this behavior is a bit more complicated. In this short note, we improve upon existing lower bounds for non-bipartite graphs H to a value that we conjecture to …

On The Planarity Of Generalized Line Graphs, Khawlah H. Alhulwah, Mohra Zayed, Ping Zhang

Theory & Applications of Graphs

One of the most familiar derived graphs is the line graph. The line graph L(G) of a graph G is that graph whose vertices are the edges of G where two vertices of L(G) are adjacent if the corresponding edges are adjacent in G. Two nontrivial paths P and Q in a graph G are said to be adjacent paths in G if P and Q have exactly one vertex in common and this vertex is an end-vertex of both P and Q. For an integer ℓ ≥ 2, the ℓ -line graph Lℓ (G) of a …

A Survey On Monochromatic Connections Of Graphs, Xueliang Li, Di Wu

Theory & Applications of Graphs

The concept of monochromatic connection of graphs was introduced by Caro and Yuster in 2011. Recently, a lot of results have been published about it.
In this survey, we attempt to bring together all the results that dealt with it.
We begin with an introduction, and then classify the results into the following categories: monochromatic connection coloring of edge-version, monochromatic connection coloring of vertex-version, monochromatic index, monochromatic connection coloring of total-version.

Edge Colorings Of Complete Multipartite Graphs Forbidding Rainbow Cycles, Peter Johnson, Andrew Owens

Theory & Applications of Graphs

It is well known that if the edges of a finite simple connected graph on n vertices are colored so that no cycle is rainbow, then no more than n-1 colors can appear on the edges. In previous work it has been shown that the essentially different rainbow-cycle-forbidding edge colorings of K_n with n-1 colors appearing are in 1-1 correspondence with (can be encoded by) the (isomorphism classes of) full binary trees with n leafs. In the encoding, the natural Huffman labeling of each tree arising from the assignment of 1 to each leaf plays a role. Very recently …

Network Modeling Of Infectious Disease: Transmission, Control And Prevention, Christina M. Chandler

Honors College Theses

Many factors come into play when it comes to the transmission of infectious diseases. In disease control and prevention, it is inevitable to consider the general population and the relationships between individuals as a whole, which calls for advanced mathematical modeling approaches.

We will use the concept of network flow and the modified Ford-Fulkerson algorithm to demonstrate the transmission of infectious diseases over a given period of time. Through our model one can observe what possible measures should be taken or improved upon in the case of an epidemic. We identify key nodes and edges in the resulted network, which …

On The Graceful Cartesian Product Of Alpha-Trees, Christian Barrientos, Sarah Minion

Theory & Applications of Graphs

A graceful labeling of a graph G of size n is an injective assignment of integers from the set {0,1,…,n} to the vertices of G such that when each edge has assigned a weight, given by the absolute value of the difference of the labels of its end vertices, all the weights are distinct. A graceful labeling is called an α-labeling when the graph G is bipartite, with stable sets A and B, and the labels assigned to the vertices in A are smaller than the labels assigned to the vertices in B. In this …

Note On 6-Regular Graphs On The Klein Bottle, Michiko Kasai, Naoki Matsumoto, Atsuhiro Nakamoto, Takayuki Nozawa, Hiroki Seno, Yosuke Takiguchi

Theory & Applications of Graphs

Altshuler classified six regular graphs on the torus, but Thomassen and Negami gave different classifications for six regular graphs on the Klein bottle. In this note, we unify those two classifications, pointing out their difference and similarity.

An Updated Survey On Rainbow Connections Of Graphs - A Dynamic Survey, Xueliang Li, Yuefang Sun

Theory & Applications of Graphs

The concept of rainbow connection was introduced by Chartrand, Johns, McKeon and Zhang in 2008. Nowadays it has become a new and active subject in graph theory. There is a book on this topic by Li and Sun in 2012, and a survey paper by Li, Shi and Sun in 2013. More and more researchers are working in this field, and many new papers have been published in journals. In this survey we attempt to bring together most of the new results and papers that deal with this topic. We begin with an introduction, and then try to organize the …

Edge Colorings Of K(M,N) With M+N-1 Colors Which Forbid Rainbow Cycles, Peter Johnson, Claire Zhang

Theory & Applications of Graphs

For positive integers m, n, the greatest number of colors that can appear in an edge coloring of K(m,n) which avoids rainbow cycles is m + n - 1. Here these colorings are constructively characterized. It turns out that these colorings can be encoded by certain vertex labelings of full binary trees with m + n leafs.

An Eternal Domination Problem In Grids, William Klostermeyer, Margaret-Ellen Messinger, Alejandro Angeli Ayello

Theory & Applications of Graphs

A dynamic domination problem in graphs is considered in which an infinite sequence of attacks occur at vertices with mobile guards; the guard at the attacked vertex is required to vacate the vertex by moving to a neighboring vertex with no guard. Other guards are allowed to move at the same time, and before and after each attack, the vertices containing guards must form a dominating set of the graph. The minimum number of guards that can defend the graph against such an arbitrary sequence of attacks is called the m-eviction number of the graph. In this paper, the m-eviction …

Two Short Proofs Of The Perfect Forest Theorem, Yair Caro, Josef Lauri, Christina Zarb

Theory & Applications of Graphs

A perfect forest is a spanning forest of a connected graph G, all of whose components are induced subgraphs of G and such that all vertices have odd degree in the forest. A perfect forest can be thought of as a generalization of a perfect matching since, in a matching, all components are trees on one edge. Scott first proved the Perfect Forest Theorem, namely, that every connected graph of even order has a perfect forest. Gutin then gave another proof using linear algebra.

We give here two very short proofs of the Perfect Forest Theorem which use only …

Application Of An Extremal Result Of Erdős And Gallai To The (N,K,T) Problem, Matt Noble, Peter Johnson, Dean Hoffman, Jessica Mcdonald

Theory & Applications of Graphs

An extremal result about vertex covers, attributed by Hajnal to Erdős and Gallai, is applied to prove the following: If n, k, and t are integers satisfying n ≥ k ≥ t ≥ 3 and k ≤ 2t - 2, and G is a graph with the minimum number of edges among graphs on n vertices with the property that every induced subgraph on k vertices contains a complete subgraph on t vertices, then every component of G is complete.

Dynamics Of Gene Networks In Cancer Research, Paul Scott

College of Graduate Studies: Theses & Dissertations

Cancer prevention treatments are being researched to see if an optimized treatment schedule would decrease the likelihood of a person being diagnosed with cancer. To do this we are looking at genes involved in the cell cycle and how they interact with one another. Through each gene expression during the life of a normal cell we get an understanding of the gene interactions and test these against those of a cancerous cell. First we construct a simplified network model of the normal gene network. Once we have this model we translate it into a transition matrix and force changes on …

Graph Invariants Of Trees With Given Degree Sequence, Rachel Bass

College of Graduate Studies: Theses & Dissertations

Graph invariants are functions defined on the graph structures that stay the same under taking graph isomorphisms. Many such graph invariants, including some commonly used graph indices in Chemical Graph Theory, are defined on vertex degrees and distances between vertices. We explore generalizations of such graph indices and the corresponding extremal problems in trees. We will also briefly mention the applications of our results.

Combinatorics Of Compositions, Meghann M. Gibson

College of Graduate Studies: Theses & Dissertations

Integer compositions and related enumeration problems have been extensively studied. The cyclic analogues of such questions, however, have significantly fewer results. In this thesis, we follow the cyclic construction of Flajolet and Soria to obtain generating functions for cyclic compositions and n-color cyclic compositions with various restrictions. With these generating functions we present some statistics and asymptotic formulas for the number of compositions and parts in such compositions. Combinatorial explanations are also provided for many of the enumerative observations presented.

Pattern Containment In Circular Permutations, Charles Lanning

College of Graduate Studies: Theses & Dissertations

Pattern containment in permutations, as opposed to pattern avoidance, involves two aspects. The first is to contain every pattern at least once from a given set, known as finding superpatterns; while the second is to contain some given pattern as many times as possible, known as pattern packing. In this thesis, we explore these two questions in circular permutations and present some interesting observations. We also raise some questions and propose some directions for future study.

Combinatorial Optimization Of Subsequence Patterns In Words, Matthew R. Just

College of Graduate Studies: Theses & Dissertations

Packing patterns in words concerns finding a word with the maximum number of a prescribed pattern. The majority of the work done thus far is on packing patterns into permutations. In 2002, Albert, Atkinson, Handley, Holton and Stromquist showed that there always exists a layered permutation containing the maximum number of a layered pattern among all permutations of length n. Consequently, the packing density for all but two (up to equivalence) permutation patterns up to length 4 can be obtained. In this thesis we consider the analogous question for colored patterns and permutations. By introducing the concept of colored blocks …

Path-Factors Involving Paths Of Order Seven And Nine, Yoshimi Egawa, Michitaka Furuya

Theory & Applications of Graphs

In this paper, we show the following two theorems (here c_i(G-Χ) is the number of components C of G-Χ with |V(C)|=i): (i) If a graph G satisfies c₁(G-Χ)+⅓c₃(G-Χ)+⅓c₅(G-Χ) ≤ ⅔ |Χ| for all Χ ≤ V(G), then G has a {Ρ₂},Ρ₇}-factor. (ii)If a graph G satisfies c₁}(G-Χ)+c₃}(G-Χ)+⅔ c₅}(G-Χ)+⅓c₇}(G-Χ) ≤ ⅔|Χ| for all Χ⊆ V(G), then G has a {P₂,P₉}-factor.

Classifying Resolving Lists By Distances Between Members, Paul Feit

Theory & Applications of Graphs

Let G be a connected graph and let w₁,…w_r be a list of vertices. We refer the choice of a triple (r;G;w₁,…w_r), as a metric selection. Let ρ be the shortest path metric of G. We say that w₁,…w_r resolves G (metricly) if the function c:V(G) → ℤ^r given by

x → (ρ (w1,x),…,ρ(wr,x))

is injective. We refer to c as the code map and to its image as the codes of the triple (r;G;w₁,…,w_r).

This paper proves basic results …

Induced Subgraph Saturated Graphs, Craig M. Tennenhouse

Theory & Applications of Graphs

A graph G is said to be H-saturated if G contains no subgraph isomorphic to H but the addition of any edge between non-adjacent vertices in G creates one. While induced subgraphs are often studied in the extremal case with regard to the removal of edges, we extend saturation to induced subgraphs. We say that G is induced H-saturated if G contains no induced subgraph isomorphic to H and the addition of any edge to G results in an induced copy of H. We demonstrate constructively that there are non-trivial examples of saturated graphs for …

On Minimum Spanning Subgraphs Of Graphs With Proper Connection Number 2, Zhenming Bi, Gary Chartrand, Garry L. Johns, Ping Zhang

Theory & Applications of Graphs

An edge coloring of a connected graph G is a proper-path coloring if every two vertices of G are connected by a properly colored path. The minimum number of colors required of a proper-path coloring of G is called the proper connection number pc(G) of G. For a connected graph G with proper connection number 2, the minimum size of a connected spanning subgraph H of G with pc(H) = 2 is denoted by μ(G). It is shown that if s and t are integers such that t ≥ s + 2 ≥ 5 …

Eternal Independent Sets In Graphs, Yair Caro, William F. Klostermeyer

Theory & Applications of Graphs

The use of mobile guards to protect a graph has received much attention in the literature of late in the form of eternal dominating sets, eternal vertex covers and other models of graph protection. In this paper, eternal independent sets are introduced. These are independent sets such that the following can be iterated forever: a vertex in the independent set can be replaced with a neighboring vertex and the resulting set is independent.

Group-Antimagic Labelings Of Multi-Cyclic Graphs, Dan Roberts, Richard M. Low

Theory & Applications of Graphs

Let Α be a non-trivial abelian group. A connected simple graph G = (V, E) is Α-antimagic if there exists an edge labeling f: Ε(G) → A \{0} such that the induced vertex labeling f+: V(G) → Α, defined by f+(v) = Σ{f(u,v): (u, v) ∈ E(G)}, is a one-to-one map. The integer-antimagic spectrum of a graph G is the set IAM(G) = {κ: G is ℤ_k - antimagic and κ ≥ 2}. In this paper, we analyze the integer-antimagic spectra for various classes of multi-cyclic graphs.

An Edge-Swap Heuristic For Finding Dense Spanning Trees, Mustafa Ozen, Hua Wang, Kai Wang, Demet Yalman

Theory & Applications of Graphs

Finding spanning trees under various restrictions has been an interesting question to researchers. A "dense" tree, from a graph theoretical point of view, has small total distances between vertices and large number of substructures. In this note, the "density" of a spanning tree is conveniently measured by the weight of a tree (defined as the sum of products of adjacent vertex degrees). By utilizing established conditions and relations between trees with the minimum total distance or maximum number of sub-trees, an edge-swap heuristic for generating "dense" spanning trees is presented. Computational results are presented for randomly generated graphs and specific …

An Extremal Problem For Finite Lattices, John Goldwasser, Brendan Nagle, Andres Saez

Theory & Applications of Graphs

For a fixed M x N integer lattice L(M,N), we consider the maximum size of a subset A of L(M,N) which contains no squares of prescribed side lengths k(1),...,k(t). We denote this size by ex(L(M,N), {k(1),...,k(t)}), and when t = 1, we abbreviate this parameter to ex(L(M,N), k), where k = k(1).

Our first result gives an exact formula for ex(L( …

Gallai-Ramsey Number Of An 8-Cycle, Jonathan Gregory

College of Graduate Studies: Theses & Dissertations

Given a graph G and a positive integer k, define the Gallai-Ramsey number to be the minimum number of vertices n such that any k-edge-coloring of Kn contains either a rainbow (all different colored) triangle or a monochromatic copy of G. In this work, we establish the Gallai-Ramsey number of an 8-cycle for all positive integers.