Combinatorics, Graph Theory and Computing
SEICCGTC 2022, Boca Raton, USA, March 7–11
- 2024
- Book
- Editors
- Sarah Heuss
- Richard Low
- John C. Wierman
- Book Series
- Springer Proceedings in Mathematics & Statistics
- Publisher
- Springer Nature Switzerland
About this book
This proceedings volume compiles selected, revised papers presented at the 53rd SouthEastern International Conference on Combinatorics, Graph Theory, and Computing (SEICCGTC 2022), which took place at Florida Atlantic University in Boca Raton, USA, from March 7th to 11th, 2022.
The SEICCGTC is widely regarded as a trendsetter for other conferences worldwide. Many ideas and themes initially discussed here have subsequently been explored in other conferences and symposia.
Since 1970, the conference has been held annually in Baton Rouge, Louisiana, and Boca Raton, Florida. Over the years, it has grown to become the primary annual conference in its fields, playing a crucial role in disseminating results and fostering collaborative work.
This volume is tailored for the community of pure and applied mathematicians in academia, industry, and government, who work in combinatorics and graph theory, as well as related areas of computer science and the intersections among these fields.
Advertisement
Table of Contents
-
The Spectrum Problem for the 4-Uniform 4-Colorable 3-Cycles with Maximum Degree 2
Ryan C. Bunge, Saad I. El-Zanati, Julie N. Kirkpatrick, Shania M. Sanderson, Michael J. Severino, William F. TurnerThe chapter delves into the spectrum problem for 4-uniform 4-colorable 3-cycles with maximum degree 2, a specialized area within combinatorial design theory. It introduces the concept of hypergraphs and their decompositions, focusing on the specific conditions under which these hypergraphs can be decomposed. The author presents several examples and lemmas that lead to the main theorem, which establishes the necessary and sufficient conditions for the existence of such decompositions. This work builds on previous research and extends the understanding of hypergraph decompositions, making it a valuable contribution to the field.AI Generated
This summary of the content was generated with the help of AI.
AbstractThe complete t-uniform hypergraph of order v, denoted \(K^{(t)}_v\), has a set V with v elements as its vertex set and the set of all t-element subsets of V as its edge set. For the purposes of this work, we define a 4-uniform 3-cycle of maximum degree 2 to be any 4-uniform hypergraph of maximum degree 2 that can be obtained by adding two vertices to each of the three edges in \(K^{(2)}_3\). There are five such 4-uniform hypergraphs up to isomorphism. Two of them have chromatic number 4. We give necessary and sufficient conditions for the existence of a decomposition of the complete 4-uniform hypergraph of order v into these 4-colorable 3-cycles. -
A Matrix Criterion for Harmonic Morphisms of Graphs with Applications to Graph Products
Caroline G. Melles, David JoynerThe chapter 'A Matrix Criterion for Harmonic Morphisms of Graphs with Applications to Graph Products' presents a novel matrix-theoretic method to characterize harmonic morphisms between graphs. It begins by defining harmonic morphisms and introducing the necessary background material. The core of the chapter is the adjacency matrix criterion for harmonic morphisms, which uses diagonal matrices to establish conditions for a map to be harmonic. The authors also provide an equivalent criterion in terms of the Laplacian matrices. The chapter explores applications of this criterion to specific graph products, such as tensor, Cartesian, and strong products, and provides formulas for vertical and horizontal multiplicities in each case. Additionally, it applies the criterion to projections of lexicographic products and concludes with examples and a conjecture about harmonic morphisms of grid graphs. The chapter is particularly notable for its use of matrix methods to derive properties of harmonic morphisms and its potential for computer experiments in graph theory.AI Generated
This summary of the content was generated with the help of AI.
AbstractUrakawa, and later Baker and Norine, developed the notion of a harmonic morphism as a type of graph morphism with similar properties to holomorphic maps of Riemann surfaces. We give a matrix criterion for harmonic graph morphisms which allows us to translate combinatorial questions about harmonic morphisms to linear algebra questions. We illustrate its use by finding conditions under which certain maps of NEPS graph products (for example, tensor, Cartesian, and strong products) are harmonic, and calculating their vertical and horizontal multiplicity matrices and degrees. We also apply the matrix criterion to lexicographic products, the special case of graph blow-ups, and graph joins. -
Applications of Topological Graph Theory to 2-Manifold Learning
Tyrus Berry, Steven SchluchterThe chapter 'Applications of Topological Graph Theory to 2-Manifold Learning' presents a novel method for approximating embedded 2-manifolds from noisy point cloud data. It leverages topological graph theory and rotation systems to construct a combinatorial approximation of the manifold, which is then used for classification. The method involves three main steps: tangent space approximation using singular value decomposition, construction of a discrete global structure representation, and extraction of topological information. The algorithm is designed to handle both orientable and nonorientable surfaces, and its effectiveness is demonstrated through experimental results on various surfaces. This chapter is particularly valuable for researchers and practitioners in computer graphics, surface reconstruction, and manifold learning, offering a fresh perspective on these well-studied problems.AI Generated
This summary of the content was generated with the help of AI.
AbstractWe show how, given a sufficiently large point cloud sampled from an embedded 2-manifold in \(\mathbb {R}^n\), we may obtain a global representation of the embedded manifold as a cell complex with vertices given by a representative subset of the point cloud. We apply a known projection based approach (into approximations of tangent planes) from the studies of surface reconstruction and computer graphics, and we extend this with the application of techniques from topological graph theory for the purpose of topological identification of the sampled surface. We apply our methods to samples taken from orientable and nonorientable surfaces. Since our new approach is based on a cell complex rather than a triangulation, it does not derive from or apply Vornoi diagrams or any Delaunay structure. -
Properties of Sierpinski Triangle Graphs
Allan BickleThe chapter delves into the fascinating properties of Sierpinski triangle graphs, offering two distinct models for their representation as graphs. It explores recurrence relations for parameters such as order and size, and presents intriguing findings such as the existence of Hamiltonian cycles and the precise count of Eulerian circuits. Additionally, the chapter investigates the domination number and radius of these graphs, as well as their unique 3-colorability. The work also extends to Hanoi graphs, their construction, and their unique properties, including their connection to the Towers of Hanoi problem and Pascal’s Triangle. The chapter concludes with a discussion on the 2-tone chromatic number of these graphs, providing a comprehensive overview of their remarkable mathematical features.AI Generated
This summary of the content was generated with the help of AI.
AbstractA Nordhaus-Gaddum theorem states bounds on \(p\left (G\right )+p\left (\overline {G}\right )\) and \(p\left (G\right )\cdot p\left (\overline {G}\right )\) for some graph parameter \(p\left (G\right )\). Viewing \(\left \{ G,\overline {G}\right \} \) as a decomposition of \(K_{n}\) allows us to generalize these theorems to decompositions of \(K_{n}\) with more than two factors. We determine the sum upper bound for independence number, domination number, edge independence number, maximum degree, edge chromatic number, and clique number. We also determine the extremal decompositions for the product lower bound for chromatic number. -
Decomposing the -Fold Complete 3-Uniform Hypergraph into the Lines of the Pasch Configuration
Ryan C. Bunge, Skyler R. Dodson, Saad I. El-Zanati, Jacob Franzmeier, Dru HorneThe chapter delves into the decomposition of the -fold complete 3-uniform hypergraph into the lines of the Pasch configuration, a specific hypergraph known for its unique structure. It begins by defining key concepts in hypergraph theory, such as uniformity and regularity. The main focus is on determining the necessary conditions and constructing proofs for the existence of these decompositions, which are crucial for understanding the spectrum problem for hypergraph designs. The chapter also highlights several small examples and lemmas that are used to build larger decompositions, showcasing the intricate relationships between different hypergraph structures. The main theorem provides a comprehensive result on the existence of such decompositions under specific conditions, contributing significantly to the field of combinatorial design theory.AI Generated
This summary of the content was generated with the help of AI.
AbstractLet P denote the 3-uniform hypergraph on 6 vertices whose edges form the lines of the Pasch configuration. We give necessary and sufficient conditions for the existence of P-decompositions of the \(\lambda \)-fold complete 3-uniform hypergraph on v vertices. -
On Decompositions of the Johnson Graph
Atif Abueida, Mike DavenThe chapter delves into the decomposition of Johnson graphs, which are graphs whose vertices represent k-element subsets of an n-element set. It begins by defining decompositions and providing historical context on graph decomposition problems. The main theorem demonstrates that Johnson graphs can be decomposed into distinct copies of complete graphs, with specific conditions for the number of copies. This leads to various applications, such as cycle and path decompositions, and decompositions into other common subgraphs. The chapter also explores decompositions into two or more subgraphs, providing theorems and conditions for such partitions. Throughout, the chapter highlights the structural properties of Johnson graphs that facilitate these decompositions and offers a comprehensive overview of the topic, making it a valuable resource for researchers and professionals in graph theory.AI Generated
This summary of the content was generated with the help of AI.
AbstractMost of the results on graph decompositions involve a partition of the edges of the complete graph, complete bipartite graph, or complete multipartite graph into disjoint copies of one or more small graphs. In this chapter we find conditions for the decompositions of the Johnson graph into a variety of smaller subgraphs including cycles, path, and other common subgraphs. -
Tiling With Three Element Sets
Aaron MeyerowitzThe chapter 'Tiling With Three Element Sets' delves into the intricate world of tiling integer sets using translates of a three-element integer set and its reflection. It improves and recasts existing results, enabling the treatment of similar cases and presenting open problems for both integer and real cases. The introduction of a greedy rule for generating interval tilings is a key highlight, along with a direct proof that demonstrates the rule's applicability to various initial states and its adaptation to real cases. The length of interval tilings is also explored, with the chapter providing explicit patterns for tilings in different cases. Additionally, the chapter discusses the challenge of finding real interval tilings and presents Theorem 8, which provides an affirmative answer and improves the upper bound for tilings in the integer case. The chapter concludes with a discussion of further results and open questions, making it a comprehensive resource for specialists in the field.AI Generated
This summary of the content was generated with the help of AI.
AbstractWe consider tilings of intervals and other sets in \(\mathbb {Z}\) with translates of a three element integer set \(\mathcal {A}=\{0,a,a+b\}\) and its reflection \(\mathcal {B}=\{0,b,a+b\}.\) We also consider these questions for intervals and other sets in \(\mathbb {R}\) where a and b are real numbers. -
Deques on a Torus
Thomas McKenzie, Shannon OverbayThe chapter delves into the visualization and processing of data structures such as stacks, queues, and deques using graph embeddings. It begins by discussing the known results for these structures and extends the concepts to cylinder and torus books. A key contribution is the introduction of toroidal deques, which allow for the processing of non-planar graphs. The chapter also includes edge bounds and optimal embeddings for complete graphs, highlighting the added value of torus books over other structures. Additionally, it explores embeddings of Cartesian products of paths and cycles on these structures, providing alternate embeddings that preserve the order and orientation of vertices. The chapter concludes by showcasing how these embeddings can be interpreted as signing documents in a circular hall, offering a unique perspective on data structure processing.AI Generated
This summary of the content was generated with the help of AI.
AbstractWe provide an overview of graphical representations of stacks, queues, and deques. In the case of a cylinder book, corresponding to a deque, we give edge bounds and determine the deque number of the complete graph. We extend the deque in a natural way, forming a toroidal deque. Unlike the other three structures, the toroidal deque can process certain non-planar graphs, including \(K_7\) and the Cartesian product of two cycles. -
Möbius Book Embeddings
Nicholas Linthacum, Luke Martin, Thomas McKenzie, Shannon Overbay, Lin Ai TanThe chapter delves into the innovative concept of Möbius book embeddings, an extension of traditional book embeddings where the pages are Möbius bands. It introduces the Möbius deque, a data structure analogous to deques and torus deques, and demonstrates its utility through practical applications, such as modeling office layouts and delivery systems. The chapter also establishes edge bounds for Möbius book embeddings and presents examples of graphs that can be embedded in Möbius books, including complete graphs and bipartite graphs. Additionally, it explores the Möbius book thickness of various graphs and discusses future research directions, such as Klein book embeddings.AI Generated
This summary of the content was generated with the help of AI.
AbstractBook embeddings of graphs have been the subject of extensive study. In this chapter we generalize the definition of such embeddings by allowing book pages to be Möbius strips, rather than half planes. We give an application of these Möbius books and we give page bounds for complete graphs and bipartite graphs. We conclude with optimal Möbius book embeddings of some well-known graph families. -
DNA Self-assembly: Friendship Graphs
Leyda Almodóvar, Emily Brady, Michaela Fitzgerald, Hsin-Hao Su, Heiko TodtThe chapter delves into the theoretical design of DNA tiles for constructing friendship and dumbbell-friendship graphs using the flexible-tile model. It explores three laboratory scenarios, each with different constraints on the realization of target graphs. The authors present detailed results for minimizing tile and bond-edge types, using graph theory to ensure optimal construction. The chapter also introduces the concept of pots, which are collections of tiles, and construction matrices to determine the smallest graph that can be constructed from a given pot. The authors provide examples and proofs for each scenario, highlighting the intricate balance between minimizing resources and preventing the formation of non-isomorphic graphs. This chapter is a valuable resource for researchers aiming to optimize DNA self-assembly processes.AI Generated
This summary of the content was generated with the help of AI.
AbstractBased on the flexible tile method for DNA self-assembly, we find a collection of tiles that will construct a nanostructure shaped like a friendship graph or a dumbbell-friendship graph. We find the minimum number of tile and bond-edge types required to construct these graphs in three different scenarios representing distinct levels of laboratory constraints. -
The Pansophy of Semi Directed Graphs
Jeffe Boats, Lazaros KikasThe chapter delves into the pansophy of semi-directed graphs, reintroducing the k-disjoint path property and its motivation. It studies how the direction of edges affects the pansophy of various graphs, including cycle and path graphs. Notably, it shows that the direction of a single edge is irrelevant, but multiple directed edges significantly impact pansophy. The chapter concludes with open questions for future research, highlighting the need for further exploration in this area.AI Generated
This summary of the content was generated with the help of AI.
AbstractGiven an ordered list of randomly-selected pairs of vertices in a graph, how many of these pairs can be connected with disjoint paths? The pansophy of a graph G is the expected number of possible disjoint paths—this has been calculated and studied for many classes of undirected graphs. In this chapter we study the pansophy of various graphs where an edge or a select collection of edges have been directed. By doing this, how is the pansophy of G affected? Do specific selections of edges affect pansophy differently from other selections? These and other questions are addressed in this chapter. -
Signed Magic Arrays with Certain Property
Abdollah Khodkar, David LeachThe chapter delves into the intricate world of signed magic arrays (SMAs), focusing on the existence of shiftable arrays with specific properties. Building on the foundation of integer Heffter arrays, the text introduces the notion of SMAs and their tightness. It presents constructive proofs for the existence of shiftable SMAs with even dimensions, employing strong induction and detailed constructions. The chapter also explores the relationship between SMAs and integer Heffter arrays, offering new insights and methods for array construction. The main theorem provides a comprehensive condition for the existence of such arrays, making this chapter a valuable resource for researchers in combinatorial mathematics.AI Generated
This summary of the content was generated with the help of AI.
AbstractA signed magic array, \(SMA(m, n;s,t)\), is an \(m \times n\) array with the same number of filled cells s in each row and the same number of filled cells t in each column, filled with a certain set of numbers that is symmetric about the number zero, such that every row and column has a zero sum. We use the notation \(SMA(m, n)\) if \(m=t\) and \(n=s\).In this chapter, we prove that for every even number \(n\geq 2\) there exists an \(SMA(m,n)\) such that the entries \(\pm x\) appear in the same row for every \(x\in \{1, 2, 3,\ldots , mn/2\}\) if and only if (a) \(n=2\) and \(m\equiv 0, 3\pmod 4\), or (b) \(n\geq 4\) and \(m\geq 3\). -
The Buratti-Horak-Rosa Conjecture Holds for Some Underlying Sets of Size Three
Pranit Chand, M. A. OllisThe Buratti-Horak-Rosa (BHR) Conjecture, a significant problem in combinatorial mathematics, is the focus of this chapter. The BHR Conjecture posits conditions under which a multiset is realizable in a complete graph. The chapter introduces the concept of growable realizations and explores methods to determine which multisets are realizable for specific underlying sets. It discusses various approaches to prove the conjecture for different underlying sets, including the use of algorithms and theoretical constructions. The chapter also highlights the relevance of the conjecture to related problems in graph decompositions and provides insights into the structure and complexity of the problem. The detailed exploration and innovative methods presented make this chapter a valuable resource for specialists in combinatorial mathematics and graph theory.AI Generated
This summary of the content was generated with the help of AI.
AbstractThe Buratti-Horak-Rosa Conjecture concerns the possible multisets of edge-labels of a Hamiltonian path in the complete graph with vertex labels \(0, 1, \ldots , {v-1}\) under a particular induced edge-labeling. The conjecture has been shown to hold when the underlying set of the multiset has size at most 2, is a subset of \(\{1,2,3,4\}\) or \(\{1,2,3,5\}\), or is \(\{1,2,6\}\), \(\{1,2,8\}\) or \(\{1,4,5\}\), as well as partial results for many other underlying sets. We use the method of growable realizations to show that the conjecture holds for each underlying set \(U = \{ x,y,z \}\) when \(\max (U) \leq 7\) or when \(xyz \leq 24\), with the possible exception of \(U = \{1,2,11\}\). We also show that for any even x the validity of the conjecture for the underlying set \(\{ 1,2,x \}\) follows from the validity of the conjecture for finitely many multisets with this underlying set. -
Publisher Correction to: Nordhaus-Gaddum Theorems for Multifactor Decompositions
Allan BickleThe chapter addresses a critical correction in the publication of a significant mathematical work, replacing an erroneous manuscript with the correct one. This correction is pivotal for researchers and scholars who rely on accurate and precise mathematical foundations. The focus is on the Nordhaus-Gaddum theorems and their application to multifactor decompositions, a topic that bridges combinatorial theory and advanced mathematical analysis. The detailed examination of these theorems provides a deeper understanding of how multifactor decompositions can be applied to solve complex problems in graph theory and combinatorics. The chapter's meticulous approach ensures that readers gain valuable insights into the intricate relationships between different mathematical structures, making it an indispensable resource for those seeking to advance their knowledge in this field.AI Generated
This summary of the content was generated with the help of AI.
- Title
- Combinatorics, Graph Theory and Computing
- Editors
-
Sarah Heuss
Richard Low
John C. Wierman
- Copyright Year
- 2024
- Publisher
- Springer Nature Switzerland
- Electronic ISBN
- 978-3-031-62166-6
- Print ISBN
- 978-3-031-62165-9
- DOI
- https://doi.org/10.1007/978-3-031-62166-6
PDF files of this book don't fully comply with PDF/UA standards, but do feature limited screen reader support, described non-text content (images, graphs), bookmarks for easy navigation and searchable, selectable text. Users of assistive technologies may experience difficulty navigating or interpreting content in this document. We recognize the importance of accessibility, and we welcome queries about accessibility for any of our products. If you have a question or an access need, please get in touch with us at accessibilitysupport@springernature.com
