Open Access. Powered by Scholars. Published by Universities.®

Discrete Mathematics and Combinatorics Commons™

Open Access. Powered by Scholars. Published by Universities.®

Georgia Southern University

Discipline
Keyword
Publication Year
Publication
Publication Type

Articles 151 - 167 of 167

Full-Text Articles in Discrete Mathematics and Combinatorics

A Class Of Graphs Approaching Vizing's Conjecture, Aziz Contractor, Elliot Krop Jan 2016

A Class Of Graphs Approaching Vizing's Conjecture, Aziz Contractor, Elliot Krop

Theory & Applications of Graphs

For any graph G=(V,E), a subset S ⊆ V dominates G if all vertices are contained in the closed neighborhood of S, that is N[S]=V. The minimum cardinality over all such S is called the domination number, written γ(G). In 1963, V.G. Vizing conjectured that γ(G □ H) ≥ γ(G)γ(H) where □ stands for the Cartesian product of graphs. In this note, we define classes of graphs Αn, for n≥0, so that every graph belongs to some such class, and Α0 corresponds to class A of Bartsalkin and German. We prove that …

Go to article

Packing Densities Of Colored And Non-Colored Patterns, Matthew R. Just Apr 2015

Packing Densities Of Colored And Non-Colored Patterns, Matthew R. Just

GS4 Student Scholars Symposium

Pattern packing concerns finding an optimal permutation that contains the maximum number of occurrences of a given pattern and computing the corresponding packing density. In many instances such an optimal permutation can be characterized directly and the number of occurrences of the pattern in interest may be enumerated explicitly. In more complicated patterns a direct characterization may be more challenging, however computational results for long permutations can help provide an indirect characterization of the general form of an optimal permutation. Much work has been done on the study of pattern packing in layered patterns, as the optimal permutation of a …

Go to article

An Isomorphism Problem In Z2, Matt Noble Jan 2015

An Isomorphism Problem In Z2, Matt Noble

Theory & Applications of Graphs

We consider Euclidean distance graphs with vertex set ℚ2 or ℤ2 and address the possibility or impossibility of finding isomorphisms between such graphs. It is observed that for any distances d1, d2 the non-trivial distance graphs G(ℚ2, d1) and G(ℚ2, d2) are isomorphic. Ultimately it is shown that for distinct primes p1, p2 the non-trivial distance graphs G(ℤ2, √p1) and G(ℤ2, √p2) are not isomorphic. We conclude with a few additional questions related to this work.

Go to article

Properly Colored Notions Of Connectivity - A Dynamic Survey, Xueliang Li, Colton Magnant Jan 2015

Properly Colored Notions Of Connectivity - A Dynamic Survey, Xueliang Li, Colton Magnant

Theory & Applications of Graphs

A path in an edge-colored graph is properly colored if no two consecutive edges receive the same color. In this survey, we gather results concerning notions of graph connectivity involving properly colored paths.

Go to article

Dynamic Approach To K-Forcing, Yair Caro, Ryan Pepper Jan 2015

Dynamic Approach To K-Forcing, Yair Caro, Ryan Pepper

Theory & Applications of Graphs

The k-forcing number of a graph is a generalization of the zero forcing number. In this note, we give a greedy algorithm to approximate the k-forcing number of a graph. Using this dynamic approach, we give corollaries which improve upon two theorems from a recent paper of Amos, Caro, Davila and Pepper [2], while also answering an open problem posed by Meyer [9].

Go to article

Second Hamiltonian Cycles In Claw-Free Graphs, Hossein Esfandiari, Colton Magnant, Pouria Salehi Nowbandegani, Shirdareh Haghighi Jan 2015

Second Hamiltonian Cycles In Claw-Free Graphs, Hossein Esfandiari, Colton Magnant, Pouria Salehi Nowbandegani, Shirdareh Haghighi

Theory & Applications of Graphs

Sheehan conjectured in 1975 that every Hamiltonian regular simple graph of even degree at least four contains a second Hamiltonian cycle. We prove that most claw-free Hamiltonian graphs with minimum degree at least 3 have a second Hamiltonian cycle and describe the structure of those graphs not covered by our result. By this result, we show that Sheehan’s conjecture holds for claw-free graphs whose order is not divisible by 6. In addition, we believe that the structure that we introduce can be useful for further studies on claw-free graphs.

Go to article

Bounds For The Zero Forcing Number Of Graphs With Large Girth, Randy Davila, Franklin Kenter Jan 2015

Bounds For The Zero Forcing Number Of Graphs With Large Girth, Randy Davila, Franklin Kenter

Theory & Applications of Graphs

The zero-forcing number, Ζ(G) is an upper bound for the maximum nullity of all symmetric matrices with a sparsity pattern described by the graph. A simple lower bound is δ ≤ Ζ(G) where δ is the minimum degree. An improvement of this bound is provided in the case that G has girth of at least 5. In particular, it is shown that 2δ − 2 ≤ Ζ(G) for graphs with girth of at least 5; this can be further improved when G has a small cut set. Lastly, a conjecture is made regarding a lower bound for Ζ(G) as a …

Go to article

Scheduling N Burgers For A K-Burger Grill: Chromatic Numbers With Restrictions, Peter Johnson, Xiaoya Zha Jan 2015

Scheduling N Burgers For A K-Burger Grill: Chromatic Numbers With Restrictions, Peter Johnson, Xiaoya Zha

Theory & Applications of Graphs

The chromatic number has a well-known interpretation in the area of scheduling. If the vertices of a finite, simple graph are committees, and adjacency of two committees indicates that they must never be in session simultaneously, then the chromatic number of the graph is the smallest number of hours during which the committees/vertices of the graph may all have properly scheduled meetings of one continuous hour each. Slivnik [3] showed that the fractional chromatic number can be similarly characterized. In that characterization, the meetings are allowed to be broken into a finite number of disjoint intervals. Here we consider chromatic …

Go to article

Path-Tables Of Trees: A Survey And Some New Results, Kevin Asciak Jan 2015

Path-Tables Of Trees: A Survey And Some New Results, Kevin Asciak

Theory & Applications of Graphs

The (vertex) path-table of a tree Τ contains quantitative information about the paths in Τ. The entry (i,j) of this table gives the number of paths of length j passing through vertex vi. The path-table is a slight variation of the notion of path layer matrix. In this survey we review some work done on the vertex path-table of a tree and also introduce the edge path-table. We show that in general, any type of path-table of a tree Τ does not determine Τ uniquely. We shall show that in trees, the number of paths passing through …

Go to article

Connection And Separation In Hypergraphs, Mohammad A. Bahmanian, Mateja Sajna Jan 2015

Connection And Separation In Hypergraphs, Mohammad A. Bahmanian, Mateja Sajna

Theory & Applications of Graphs

In this paper we study various fundamental connectivity properties of hypergraphs from a graph-theoretic perspective, with the emphasis on cut edges, cut vertices, and blocks. We prove a number of new results involving these concepts. In particular, we describe the exact relationship between the block decomposition of a hypergraph and the block decomposition of its incidence graph.

Go to article

Graphs Of Classroom Networks, Rebecca Holliday Jan 2015

Graphs Of Classroom Networks, Rebecca Holliday

College of Graduate Studies: Theses & Dissertations

In this work, we use the Havel-Hakimi algorithm to visualize data collected from students to investigate classroom networks. The Havel-Hakimi algorithm uses a recursive method to create a simple graph from a graphical degree sequence. In this case, the degree sequence is a representation of the students in a classroom, and we use the number of peers with whom a student studied or collaborated to determine the degree of each. We expand upon the Havel-Hakimi algorithm by coding a program in MATLAB that generates random graphs with the same degree sequence. Then, we run another algorithm to find the isomorphism …

Go to article

Labeled Trees And Spanning Trees: Computational Discrete Mathematics And Applications, Demet Yalman Jan 2015

Labeled Trees And Spanning Trees: Computational Discrete Mathematics And Applications, Demet Yalman

College of Graduate Studies: Theses & Dissertations

In this thesis, we examine two topics. In the first part, we consider Leech tree which is a tree of order n with positive integer edge weights such that the weighted distances between pairs of vertices are exactly from 1 to n choose 2. Only five Leech trees are known and some non-existence results have been presented through the years. Variations of Leech trees such as the minimal distinct distance trees and modular Leech trees have been considered in recent years. In this thesis, such Leech-type questions on distances between leaves are studied as well as some other labeling questions …

Go to article

Combinatorial Game Theory: An Introduction To Tree Topplers, John S. Ryals Jr. Jan 2015

Combinatorial Game Theory: An Introduction To Tree Topplers, John S. Ryals Jr.

College of Graduate Studies: Theses & Dissertations

The purpose of this thesis is to introduce a new game, Tree Topplers, into the field of Combinatorial Game Theory. Before covering the actual material, a brief background of Combinatorial Game Theory is presented, including how to assign advantage values to combinatorial games, as well as information on another, related game known as Domineering. Please note that this document contains color images so please keep that in mind when printing.

Go to article

Rainbow Generalizations Of Ramsey Theory - A Dynamic Survey, Shinya Fujita, Colton Magnant, Yaping Mao, Kenta Ozeki Jan 2014

Rainbow Generalizations Of Ramsey Theory - A Dynamic Survey, Shinya Fujita, Colton Magnant, Yaping Mao, Kenta Ozeki

Theory & Applications of Graphs

In this work, we collect Ramsey-type results concerning rainbow edge colorings of graphs.

Go to article

Note On Rainbow Connection In Oriented Graphs With Diameter 2, Rebecca Holliday, Colton Magnant, Pouria Salehi Nowbandegani Jan 2014

Note On Rainbow Connection In Oriented Graphs With Diameter 2, Rebecca Holliday, Colton Magnant, Pouria Salehi Nowbandegani

Theory & Applications of Graphs

In this note, we provide a sharp upper bound on the rainbow connection number of tournaments of diameter 2. For a tournament Τ of diameter 2, we show 2 ≤ → rc (Τ) ≤ 3. Furthermore, we provide a general upper bound on the rainbow κ-connection number of tournaments as a simple example of the probabilistic method. Finally, we show that an edge-colored tournament of κthdiameter 2 has rainbow κ-connection number at most approximately κ2.

Go to article

Precise Partitions Of Large Graphs, Pouria Salehi Nowbandegani Jan 2014

Precise Partitions Of Large Graphs, Pouria Salehi Nowbandegani

College of Graduate Studies: Theses & Dissertations

First by using an easy application of the Regularity Lemma, we extend some known results about cycles of many lengths to include a specified edge on the cycles. The results in this chapter will help us in rest of this thesis. In 2000, Enomoto and Ota posed a conjecture on the existence of path decomposition of graphs with fixed start vertices and fixed lengths. We prove this conjecture when |G| is large. Our proof uses the Regularity Lemma along with several extremal lemmas, concluding with an absorbing argument to retrieve misbehaving vertices. Furthermore, sharp minimum degree and degree sum conditions …

Go to article

Hamiltonicity And Sigma-Hypergraphs, Christina Zarb Jan 2014

Hamiltonicity And Sigma-Hypergraphs, Christina Zarb

Theory & Applications of Graphs

We define and study a special type of hypergraph. A σ-hypergraph Η= Η(n,r,q |σ), where σ is a partition of r, is an r-uniform hypergraph having nq vertices partitioned into n classes of q vertices each. If the classes are denoted by V1, V2,...,Vn, then a subset Κ of V(Η) of size r is an edge if the partition of r formed by the non-zero cardinalities |Κ ∩ Vi |, 1 ≤ i ≤ n, is σ. The non-empty intersections Κ ∩ Vi are called the parts of Κ, and s(σ) …

Go to article

First Prev