Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- ETD (2)
- K-forcing number (2)
- Block (1)
- Claw-free graph (1)
- Combinatorial game theory (1)
-
- Connected hypergraph (1)
- Connectivity (1)
- Cut edge (1)
- Cut vertex (1)
- Cycle (1)
- Dense tree (1)
- Distances between leaves (1)
- Domineering (1)
- Edge-swap heuristic (1)
- Euclidean distance graph (1)
- Fractional chromatic number (1)
- Girth (1)
- Graph isomorphisms (1)
- Graph theory (1)
- Graphs (1)
- Hackenbush (1)
- Havel hakimi (1)
- Hypergraph (1)
- Incidence graph (1)
- Independent set (1)
- Isomorphism (1)
- K-forcing set (1)
- Leech tree (1)
- Minimum spanning tree (1)
- Modular Leech tree (1)
- Publication
- Publication Type
Articles 1 - 12 of 12
Full-Text Articles in Physical Sciences and Mathematics
Packing Densities Of Colored And Non-Colored Patterns, Matthew R. Just
Packing Densities Of Colored And Non-Colored Patterns, Matthew R. Just
GS4 Georgia Southern 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 …
An Isomorphism Problem In Z2, Matt Noble
An Isomorphism Problem In Z2, Matt Noble
Theory and 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.
Dynamic Approach To K-Forcing, Yair Caro, Ryan Pepper
Dynamic Approach To K-Forcing, Yair Caro, Ryan Pepper
Theory and 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].
Scheduling N Burgers For A K-Burger Grill: Chromatic Numbers With Restrictions, Peter Johnson, Xiaoya Zha
Scheduling N Burgers For A K-Burger Grill: Chromatic Numbers With Restrictions, Peter Johnson, Xiaoya Zha
Theory and 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 …
Path-Tables Of Trees: A Survey And Some New Results, Kevin Asciak
Path-Tables Of Trees: A Survey And Some New Results, Kevin Asciak
Theory and 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 …
Properly Colored Notions Of Connectivity - A Dynamic Survey, Xueliang Li, Colton Magnant
Properly Colored Notions Of Connectivity - A Dynamic Survey, Xueliang Li, Colton Magnant
Theory and 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.
Second Hamiltonian Cycles In Claw-Free Graphs, Hossein Esfandiari, Colton Magnant, Pouria Salehi Nowbandegani, Shirdareh Haghighi
Second Hamiltonian Cycles In Claw-Free Graphs, Hossein Esfandiari, Colton Magnant, Pouria Salehi Nowbandegani, Shirdareh Haghighi
Theory and 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.
Connection And Separation In Hypergraphs, Mohammad A. Bahmanian, Mateja Sajna
Connection And Separation In Hypergraphs, Mohammad A. Bahmanian, Mateja Sajna
Theory and 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.
Bounds For The Zero Forcing Number Of Graphs With Large Girth, Randy Davila, Franklin Kenter
Bounds For The Zero Forcing Number Of Graphs With Large Girth, Randy Davila, Franklin Kenter
Theory and 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 …
Combinatorial Game Theory: An Introduction To Tree Topplers, John S. Ryals Jr.
Combinatorial Game Theory: An Introduction To Tree Topplers, John S. Ryals Jr.
Electronic Theses and 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.
Graphs Of Classroom Networks, Rebecca Holliday
Graphs Of Classroom Networks, Rebecca Holliday
Electronic Theses and 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 …
Labeled Trees And Spanning Trees: Computational Discrete Mathematics And Applications, Demet Yalman
Labeled Trees And Spanning Trees: Computational Discrete Mathematics And Applications, Demet Yalman
Electronic Theses and 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 …