Combinatorics, Graph Theory and Computing
SEICCGTC 2022, Boca Raton, USA, March 7–11
- 2024
- Buch
- Herausgegeben von
- Sarah Heuss
- Richard Low
- John C. Wierman
- Verlag
- Springer Nature Switzerland
Über dieses Buch
Dieser Band versammelt ausgewählte, überarbeitete Aufsätze, die auf der 53. Internationalen Konferenz für Kombinatorik, Graphentheorie und Datenverarbeitung (SEICCGTC 2022) präsentiert wurden, die vom 7. bis 11. März 2022 an der Florida Atlantic University in Boca Raton, USA, stattfand. Der SEICCGTC gilt weltweit als Trendsetter für andere Konferenzen. Viele Ideen und Themen, die hier ursprünglich diskutiert wurden, wurden später in anderen Konferenzen und Symposien erforscht. Seit 1970 wird die Konferenz jährlich in Baton Rouge, Louisiana, und Boca Raton, Florida, abgehalten. Im Laufe der Jahre hat sie sich zur wichtigsten jährlichen Konferenz in ihren Bereichen entwickelt und spielt eine entscheidende Rolle bei der Verbreitung von Ergebnissen und der Förderung der Zusammenarbeit. Dieser Band ist auf die Gemeinschaft reiner und angewandter Mathematiker in Wissenschaft, Industrie und Verwaltung zugeschnitten, die in Kombinatorik und Graphentheorie sowie verwandten Bereichen der Informatik und den Schnittpunkten zwischen diesen Bereichen arbeiten.
Mit KI übersetzt
Über dieses Buch
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.
Anzeige
Inhaltsverzeichnis
-
Frontmatter
-
Additive Combinatorics in Groups and Geometric Combinatorics on Spheres
Béla BajnokDieses Kapitel vertieft sich in die faszinierende Schnittmenge additiver Kombinatorik in endlichen abelschen Gruppen und geometrischer Kombinatorik auf Kugeln. Es stellt die Konzepte der Unabhängigkeit und des Überspannens in Gruppen vor und untersucht ihre Entsprechungen im euklidischen Raum: Designs und Distanzsets. Der Autor stellt starke Parallelen zwischen diesen scheinbar disparaten Themen fest und zeigt auf, wie Ergebnisse aus einem Bereich gewinnbringend auf den anderen angewendet werden können. Das Kapitel stellt auch faszinierende Probleme und Vermutungen vor, wie etwa die Größe der größten t-unabhängigen Menge in einer abelschen Gruppe und die Klassifizierung sphärischer t-Designs und s-Distanzmengen. Durch detaillierte Definitionen und Beispiele bietet der Text eine reichhaltige und ansprechende Erforschung dieser fortgeschrittenen mathematischen Themen, was ihn zu einer wertvollen Ressource für Spezialisten in der Kombinatorik und verwandten Bereichen macht.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractWe embark on a tour that takes us through four closely related topics: the dual concepts of independence and spanning in finite abelian groups and the analogous dual concepts of designs and distance sets on spheres. We review some of the main known results in each area, mention several open questions, and discuss some connections among these four interesting topics. -
A Walk Through Some Newer Parts of Additive Combinatorics
Béla BajnokDas Kapitel vertieft sich in die komplexe Welt der additiven Kombinatorik und konzentriert sich auf das Studium von Zusammenfassungen innerhalb endlicher abeler Gruppen. Es werden verschiedene Arten von Sumsets eingeführt, darunter h-fach unterzeichnete Sumsets, h-fach beschränkte Sumsets, h-fach unterzeichnete Sumsets und h-fach beschränkte Sumsets. Der Autor diskutiert aktuelle Ergebnisse und offene Fragen in Bezug auf minimale Summengröße, perfekte Basen und übergreifende, k-sumfreie Sets und Nonbasen maximaler Größe, wobei er die Komplexität und Schönheit dieser mathematischen Konzepte hervorhebt. Das Kapitel zeichnet sich vor allem durch seine umfassende Behandlung dieser Themen aus. Es bietet sowohl historische Perspektiven als auch neueste Forschungsergebnisse und ist daher eine unschätzbare Ressource für Spezialisten auf diesem Gebiet.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractIn this survey chapter we discuss some recent results and related open questions in additive combinatorics, in particular, questions about sumsets in finite abelian groups. -
Passing Drops and Descents
Cailyn Bass, Steve ButlerDas Kapitel "Passing Drops and Descents" beschäftigt sich mit der mathematischen Modellierung von Jongliermustern, insbesondere mit der kombinatorischen Zählung von Passmustern unter mehreren Jongleuren. Aufbauend auf früheren Arbeiten von Bühler et al. und Ehrenborg and Readdy führen die Autoren einen neuen Ansatz ein, um diese Muster anhand einer Verallgemeinerung der Eulerschen Zahlen zu beschreiben und zu zählen. Dieser Ansatz führt zu einem kombinatorischen Nachweis einer verallgemeinerten Worpitzky-Identität, die ein Sonderfall einer von Pita-Ruiz gegebenen algebraischen Identität ist. Das Kapitel geht mit der Einführung dieser Verallgemeinerung und der Festlegung grundlegender Eigenschaften weiter und beschreibt dann anhand von Karten und Turmplatzierungen Passmuster. Das Hauptergebnis ist eine kombinatorische Interpretation und der Nachweis der verallgemeinerten Identität Worpitzkys, die die einzigartigen Aspekte der tropfenfokussierten Methode im Vergleich zu traditionellen abstammungsfokussierten Ansätzen hervorheben. Das Kapitel schließt mit einer Diskussion über die Herausforderungen und Grenzen der Aufnahme von Nullpunkten in das Modell.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractWe consider generalizations of drops and descents from permutations to arrangements of sets with repetition. We also establish a generalization of Worpitzky’s identity in the special case when all elements in the set repeat equally often by way of counting passing patterns among jugglers in two different ways. -
Group Divisible Designs with Three Groups and Block Size 4
Dinesh G. Sarvate, Dinkayehu M. Woldemariam, Li ZhangDas Kapitel behandelt die komplexe Welt der Group Divisible Designs (GDDs) mit einem Schwerpunkt auf Gruppen mit drei Gruppen und einer Blockgröße von vier. Es beginnt mit der Definition von Balanced Incomplete Block Designs (BIBDs) und ihrer Bedeutung und führt dann GDDs als Verallgemeinerung von BIBDs ein. Der Text untersucht verschiedene Arten von Blöcken innerhalb der GDD und die notwendigen Bedingungen für ihre Existenz. Sie vertieft sich in die Konstruktion von GDDs und zeigt die Herausforderungen und Grenzen auf, insbesondere wenn die Anzahl der Gruppen kleiner ist als die Blockgröße. Das Kapitel bietet auch eine detaillierte Analyse spezifischer Fälle, wie GDDs mit Blockgröße vier und zwei Gruppen, und bietet Konstruktionen für bestimmte Familien von GDDs. Dabei wird die praktische Anwendung und theoretische Bedeutung von GDDs in der Statistik und im kombinatorischen Design hervorgehoben.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractGroup divisible designs are classical combinatorial designs studied for their applications as well as for their own sake. They provide an ample opportunity of developing techniques to study combinatorial design constructions. GDDs are inherently hard to construct, especially when the number of groups is less than the block size and group sizes are different. The subject matter for this chapter is GDDs of block size four with three groups of different sizes. A previous study of the problem addressed the cases when the first group size, say \(n_1\) is 1 or 2, the second group size \(n_2=n\) greater than or equal to \(n_1\) and the third group size is \(n + 1\). The first part of the present paper tackles again the case of the first group having size one and the third group having size \(n + 2\). We also obtain several non-existence results when restrictions on block configurations are placed. The second part of the chapter deals with group sizes 3, n \( (n \ge 3)\) and \(n + 1\), respectively. We hope that these constructions of specific families will help to develop a more unified approach to construct such GDDs. -
A New Absolute Irreducibility Criterion for Multivariate Polynomials over Finite Fields
Carlos Agrinsoni, Heeralal Janwa, Moises DelgadoDas Kapitel führt ein neues Kriterium zur Prüfung der absoluten Irreduzibilität multivariater Polynome über endliche Felder ein, ein grundlegendes Problem in der Algebra und der algebraischen Geometrie. Traditionelle Methoden wie das Eisenstein-Kriterium und Newton-Polygone erfordern oft komplexe Berechnungen über Feldausdehnungen. Das neue Kriterium vereinfacht den Prozess jedoch, indem es GCD-Berechnungen und Quadrat-Freiheitstests heranzieht. Dieser Ansatz ist besonders effektiv für bivariate Polynome, wodurch sich die Zeitkomplexität deutlich verringert. Das Kapitel stellt auch einen Algorithmus zur absoluten Irreduzibilitätsprüfung vor, der seine Effizienz und praktische Anwendbarkeit demonstriert. Die Ergebnisse haben weitreichende Implikationen in verschiedenen Bereichen, darunter Verschlüsselungstheorie, Kryptographie und algebraische Geometrie, wo die absolute Irreduzibilität von Polynomen für den Nachweis von Theoremen und die Entwicklung sicherer Systeme von entscheidender Bedeutung ist.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractOne of the key problems in algebraic geometry and its applications in coding theory, cryptography, and other disciplines is to determine whether a variety defined by a set of polynomials is absolutely irreducible; i.e., it remains irreducible in the algebraic closure of the defining field. The famous Eisenstein criterion for irreducibility works only over the defining fields. One important place where this is needed is when one applies the Riemann-Roch theorem. Another important application is in bounding the number of rational points or exponential sums through the Weil conjectures. In this chapter, we consider the hypersurfaces defined by generalized trinomials. We present a new absolute irreducibility criterion for generalized trinomials over finite fields. Our criterion does not require testing for irreducibility in the ground field or in any extension field. We just require multivariate GCD computations and the square-free property. Since almost all polynomials are known to be square-free, our absolute irreducibility criterion proves the absolute irreducibility of almost all generalized trinomials. -
On Combinatorial Interpretations of Some Elements of the Riordan Group
Melkamu Zeleke, Mahendra JaniDas Kapitel beginnt mit der Einführung der Riordan Group und ihrer grundlegenden Konzepte, einschließlich Riordan-Arrays und ihrer Erzeugungsfunktionen. Es diskutiert die Bedeutung von Ruggs Sequenzcharakterisierung von Riordan-Array-Einträgen und untersucht generalisierte geordnete Bäume, die als K-Bäume bekannt sind. Der Text vertieft sich dann in die Beziehung zwischen K-Bäumen und Dyck-Wegen und stellt eine natürliche Gegenüberstellung zwischen beiden dar. Es untersucht auch die Verwendung von Riordan-Arrays, um k-Dyck-Pfade und Gitterwege zu zählen, und unterstreicht die kombinatorische Bedeutung dieser Strukturen. Darüber hinaus untersucht das Kapitel die Inversen von Elementen innerhalb der Bell-Untergruppe der Riordan-Gruppe und liefert sowohl algebraische als auch kombinatorische Einsichten. Der gesamte Text bietet eine detaillierte und fesselnde Erforschung der mathematischen Konzepte, was ihn zu einer wertvollen Ressource für Spezialisten auf diesem Gebiet macht.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractRiordan arrays, equipped with Shapiro’s multiplication rule, form a group and this group provides an interesting algebraic framework to solve combinatorial problems. In this chapter, we provide combinatorial interpretations for Riordan arrays of the form \(R = (g(z), zg(z))\), where \(g(z)\) is a generating function satisfying a functional equation \(g(z) = 1 + z*{g(z)}^k\), where k is a positive integer greater than or equal to 2. The combinatorial interpretations are then used to obtain the inverses of these elements of the Bell subgroup of the Riordan group explicitly in terms of powers of \(g(z)\). -
Production Matrices of Double Riordan Arrays
Dennis Davenport, Fatima Fall, Julian Francis, Trinity LeeDas Kapitel beginnt mit einer Einführung in Riordan-Arrays, die durch zwei Potenzreihen g und f und deren Gruppeneigenschaften definiert sind. Es erweitert diese Konzepte dann auf doppelte Riordan-Arrays, die nach abwechselnden Regeln aufgebaut sind und unterschiedliche Untergruppen wie die Schachbrettuntergruppe haben. Das Kapitel stellt Produktionsmatrizen als Werkzeug zur Konstruktion und Analyse dieser Arrays vor, wobei ihre einzigartigen Eigenschaften und Anwendungen hervorgehoben werden. Es enthält auch ein kombinatorisches Beispiel mit Schröder-Pfaden, das die praktische Relevanz doppelter Riordan-Arrays in der Kombinatorik aufzeigt.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractA double Riordan array is an infinite lower triangular matrix, denoted by \( (g; f_1, f_2)\), where g, \(f_1\), and \(f_2\) are generating functions. The coefficients of the generating function g gives the first column of the matrix, and the remaining columns are found by multiplying the previous column by alternating \(f_1\) and \(f_2\). In other words,This is the columns construction of a double Riordan array. We can determine the elements of a double Riordan array using A- and Z-sequences which gives a row construction of a double Riordan array, see ([2] and [5]). In this chapter we define the production matrix of a double Riordan array, and show how it can be used to determine the A- and Z-sequences.$$\displaystyle (g; f_1, f_2)=(g, gf_1, gf_1f_2,g{f_1}^2f_2, gf_1^2f_2^2,\dots ). $$ -
The Existence of a Knight’s Tour on the Surface of Rectangular Boxes
Shengwei Lu, Carl YergerDas Kapitel vertieft sich in das faszinierende Problem, geschlossene Rittertouren auf der Oberfläche rechteckiger Schachteln zu finden, und erweitert das klassische Schachbrettproblem auf 3D-Geometrie. Es beginnt mit der Definition des Ritterzuges und der Bedingungen für eine geschlossene Tour und untersucht dann verschiedene Algorithmen und Methoden, um solche Touren auf verschiedenen Oberflächen zu konstruieren, einschließlich zylindrischer und toroider Strukturen. Das Kapitel behandelt auch das Vorhandensein geschlossener Führungen auf Brettern mit merkwürdigen Dimensionen und bietet explizite Konstruktionen für spezielle Fälle. Darüber hinaus werden offene Probleme und potenzielle zukünftige Forschungsrichtungen aufgezeigt, wie etwa die Untersuchung generalisierter Ritter und höherdimensionaler Bretter.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractA knight’s tour is a sequence of knight’s moves such that each square on the board is visited exactly once. In this chapter, we show that a closed knight’s tour exists on the surface of a rectangular box of any size. Our general algorithm is to concatenate the top and bottom faces of a box with its side faces. When general criteria are not satisfied, especially when the dimensions of the rectangular box are small, we devise some special techniques to cover these cases. -
A New Upper Bound for the Site Percolation Threshold of the Square Lattice
John C. Wierman, Samuel P. OberlyDas Kapitel konzentriert sich auf das Site-Perkolation-Modell auf dem quadratischen Gitter, ein gut untersuchtes, aber herausforderndes Problem in der Perkolationstheorie. Sie führt eine neue Obergrenze für die Durchsickerungsgrenze ein und verringert die Kluft zwischen den bestehenden Grenzen erheblich. Die Ableitung dieser Bindung umfasst die Verwendung von Self-Matching-Gittern und die Substitutionsmethode, die für Site-Perkolation-Modelle angepasst ist. Das Kapitel diskutiert auch die Schwierigkeiten und Innovationen bei der Anwendung dieser Methoden auf die Versickerung von Standorten, wobei die Berechnungstechniken und Symmetrieüberlegungen hervorgehoben werden, die die Berechnungen ermöglichen. Darüber hinaus bietet es Einblicke in laufende Forschungen, die darauf abzielen, die Obergrenze für die Versickerungsschwelle der quadratischen Gitterstandorte weiter zu verbessern. Das Kapitel ist ein bedeutender Beitrag auf diesem Gebiet und bietet neue Erkenntnisse und Methoden, die auf andere Gitter und Perkolationsmodelle angewendet werden könnten.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractThe upper bound for the site percolation threshold of the square lattice is reduced from 0.679492 to 0.666894, providing the first improvement since 1995. The bound is obtained by using the substitution method with new computational reductions which make calculations for site models more efficient. The substitution method is applied, comparing the site percolation model on a self-matching lattice to the square lattice site percolation model in a two-stage process. -
Prime, Composite and Fundamental Kirchhoff Graphs
Jessica Wang, Joseph D. FehribachDas Kapitel taucht ein in die komplizierte Welt der Kirchhoff-Graphen, Vektorgrafien mit Kanten, die die Orthogonalitätsbedingungen zwischen Zyklen und Scheitelpunkten erfüllen. Es stellt die Konzepte der Prim-, Komposit- und fundamentalen Kirchhoff-Graphen vor und diskutiert ihre Konstruktion anhand eines umfassenden Backtracking-Algorithmus. Der Text hebt die Eigenschaften von Chiralität und Gleichförmigkeit in Kirchhoff-Diagrammen hervor und untersucht das Konzept der Kachelung, das die Erzeugung neuer Kirchhoff-Diagramme durch Addition und Subtraktion bestehender ermöglicht. Das Kapitel wirft auch mehrere offene Fragen über die Struktur und Existenz dieser Grafiken auf, die zu weiterer Forschung und Erforschung einladen.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractA Kirchhoff graph is a vector graph with orthogonal cycles and vertex cuts. An algorithm has been developed that constructs all the Kirchhoff graphs up to a fixed edge multiplicity. This algorithm is used to explore the structure of prime Kirchhoff graph tilings. The existence of infinitely many prime Kirchhoff graphs for a given set of fundamental Kirchhoff graphs is established, as is the existence of a minimal multiplicity for Kirchhoff graphs to exist. -
On the Minimum Locating Number of Graphs with a Given Order
Sul-young Choi, Puhua GuanDas Kapitel vertieft sich in das Konzept der Lokalisierung von Mengen in Diagrammen, wobei der Schwerpunkt auf der minimalen Lokalisierungszahl liegt, die die Größe der kleinsten Menge von Eckpunkten ist, die benötigt werden, um den Standort eines Eindringlings eindeutig zu identifizieren. Es beginnt mit der Definition von Lokalisierungsmengen und ihren Eigenschaften und untersucht dann die Lokalisierung von Zahlen bestimmter Graphentypen wie Zyklen und Pfade. Das Kapitel stellt Vorschläge und Lemmata vor, um die minimalen Ortungszahlen für diese Graphenstrukturen festzulegen. Es diskutiert auch die streng lokalisierende Zahl und liefert ein Theorem und eine logische Folge für die minimale lokalisierende Anzahl von Graphen mit einer gegebenen Reihenfolge. Das Kapitel schließt mit Vorschlägen für mögliche Wege zur weiteren Erforschung der Lokalisierung von Zahlen komplexerer Graphenstrukturen wie Gitter und Hyperkuben.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractA locating set S in a connected graph is a set of vertices satisfying that \(N(u)\cap S\) is unique for each vertex u not in S. A locating set can be considered as a set of sensors which can determine the exact location of an intruder. The size of a smallest locating set of a graph G is called the locating number of the graph and denoted by \(ln(G)\). We show that \(min\, \{ln(G): G \) is a connected graph with n vertices \(\} = s\) when \(2^{s-1}+(s-1) < n \leq 2^s+s\). -
j-Multiple, k-Component Order Neighbor Connectivity
Alexis Doucette, Charles SuffelIn diesem Kapitel wird der Parameter j-multiple, k-Komponenten-Ordnung Nachbar-Konnektivität eingeführt, der die Verbindungen j-Dominanz und k-Komponenten-Ordnung Nachbar-Konnektivität zusammenführt. Er vergleicht diesen neuen Parameter mit seinen Vorgängern, setzt Grenzen und schafft die notwendigen Voraussetzungen für seine Minimalität. Der Text hebt auch Anwendungen bei der Bewertung der Anfälligkeit von Netzwerken und der Platzierungsplanung hervor, was ihn zu einer wertvollen Ressource für Spezialisten in Graphentheorie und Netzwerkanalyse macht.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractConsider a network modeled by a graph G on n nodes and e edges. There exist several parameters to determine the vulnerability of G. One such parameter is the domination number, which measures the minimum number of nodes necessary in a set so that its closed neighborhood is the entire graph. Multiple domination, sometimes referred to as j-domination, is a variety of domination that requires every node to either be in the set or adjacent to at least j nodes from it. The vulnerability parameter k-component order neighbor connectivity is an extension of domination and is defined as the minimum number of nodes that when removed along with their neighbors leave only components of order less than k. The new parameter, j-multiple, k-component order neighbor connectivity, denoted \(\kappa _{nc,j}^{(k)}\), extends both concepts and is defined as the minimum number of nodes that need to be removed, along with their neighbors, such that the surviving subgraph contains only components of order at most k and every node outside of the set that is adjacent to it is adjacent to at least j nodes from it. The complexity of computing the value for this parameter is NP-hard since it coincides with j-domination when k is 1. Here we introduce this new parameter, establish its bounds, and compare it to several other previously established parameters. We also establish formulas for \(\kappa _{nc,j}^{(k)}\) for several classes of graphs, including complete and complete bipartite graphs as well as paths, cycles, wheels, and complete grid graphs. -
Graphic Approximation of Integer Sequences
Brian CloteauxDas Kapitel vertieft sich in den entscheidenden Bereich der Modellierung komplexer Netzwerke in der realen Welt anhand von Graphenmodellen. Sie konzentriert sich auf den ersten Schritt der Konstruktion von Graphen mit vorgegebenen Gradfolgen, ein Problem, das häufig den Umgang mit nichtgrafischen Ganzzahlsequenzen umfasst. Die Autoren stellen zwei innovative Ansätze zur Annäherung dieser Sequenzen vor: einen, der die Diskrepanz durch Einheitstransformationen innerhalb des Majorisierungsgitters minimiert, und einen anderen, der den Wahrscheinlichkeitsverteilungsabstand minimiert. Beide Algorithmen sind so konzipiert, dass sie effizient und einfach zu implementieren sind und nur linearen Speicher erfordern. Das Kapitel stellt auch das Konzept der Majorisierung und ihre Beziehung zu grafischen Sequenzen vor und bietet eine solide Grundlage für das Verständnis der Algorithmen. Die Forschungsergebnisse unterstreichen die praktischen Vorteile dieser Methoden, insbesondere für große Sequenzen, und schlagen zukünftige Richtungen für die Erforschung anderer Entfernungsmessgrößen wie der Jensen-Shannon-Divergenz vor.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractA variety of network modeling problems begin by generating a degree sequence drawn from a given probability distribution. If the randomly generated sequence is not graphic, we give two new approaches for generating a graphic approximation of the sequence. These schemes are fast, simple to implement, and only require a linear amount of memory. This allows approximation to be performed on very large integer sequences. -
Changing the Uniform Spectrum by Deleting Edges
Drake Olejniczak, Robert VandellDas Kapitel "Changing the Uniform Spectrum by Deleting Edges" geht auf die komplizierte Beziehung zwischen der Konnektivität von Graphen und dem einheitlichen Spektrum ein, ein Konzept, das die Menge aller möglichen Pfadlängen zwischen Eckpunkten in einem Graphen beschreibt. Der Autor beginnt mit der Definition des einheitlichen Spektrums und der Untersuchung seiner Eigenschaften in verschiedenen Arten von Diagrammen, einschließlich kompletter Diagramme und Räder. Ein Schwerpunkt liegt auf den Auswirkungen der Randentfernung auf das einheitliche Spektrum, wobei ein besonderer Schwerpunkt auf Extremfällen liegt, in denen das einheitliche Spektrum maximiert oder minimiert wird. Das Kapitel stellt neuartige Techniken zur Analyse des einheitlichen Spektrums unter Kantenlöschung vor und bietet Einblicke, die das umfassendere Verständnis der Graphentheorie und ihrer Anwendungen in der Informatik und Datenwissenschaft fördern könnten. Anhand rigoroser Beweise und Beispiele zeigt der Autor, wie selbst die Entfernung einer einzelnen Kante das einheitliche Spektrum drastisch verändern kann, wobei er das empfindliche Gleichgewicht zwischen Graphenstruktur und Konnektivität hervorhebt. Das Kapitel schließt mit einer Diskussion offener Probleme und potenzieller zukünftiger Forschungsrichtungen und ermutigt die Leser, das komplexe Zusammenspiel zwischen Graphenkonnektivität und dem einheitlichen Spektrum weiter zu erforschen.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractA graph is said to be k-uniformly connected if there exists a path of length k between each pair of vertices. This generalizes the well-known concept of a Hamiltonian-connected graph—a graph, order n, in which there exits a Hamiltonian path (path of length \(n-1\)) between each pair of vertices. That is, a graph is Hamiltonian-connected if and only if it is \((n-1)\)-uniformly connected. One can also say a graph is complete if and only if it is 1-uniformly connected. The uniform spectrum of a graph G is the set of all k for which G is k-uniformly connected. In this chapter, we investigate the impact of adding or deleting vertices or edges on the uniform spectrum of a graph. Some general results are presented as well as analyses of specific classes of graphs such as bipartite graphs and wheels. -
Strongly Regular Multigraphs
Leah H. Meissner, John T. SaccomanDas Kapitel beginnt mit der Definition stark regelmäßiger Graphen und ihrer Parameter, wobei die Bedeutung ihrer benachbarten Eigenwerte hervorgehoben wird. Anschließend wird das Konzept der Multigraphen vorgestellt und untersucht, wie das gleichmäßige Aufblasen der Kanten eines stark regelmäßigen Graphen zu Multigraphen mit unterschiedlichen Eigenwerten führt. Das Kapitel behandelt auch T-Designs und ausgewogene unvollständige Blockdesigns (BIBDs), wobei ihre Beziehung zu stark regelmäßigen Diagrammen hervorgehoben wird. Sie liefert Konstruktionen für den Petersen-Graphen aus Entwürfen und erklärt, wie quasisymmetrische Entwürfe zu stark regelmäßigen Graphen führen. Das Kapitel schließt mit der Vorstellung von Methoden zur Erzeugung stark regelmäßiger Multigraphen aus Entwürfen und skizziert mögliche zukünftige Forschungsrichtungen in diesem Bereich.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractA family of regular graphs which have a direct connection to structures in algebraic combinatorics are strongly regular graphs. These graphs are defined by 4 parameters, n, k, a, and c, where n is the number of nodes, k is the degree of each node, a is the number of common neighbors for every adjacent pair of nodes, and c is the number of common neighbors for every nonadjacent pair of nodes. A multigraph is a graph that has no self-loops, but may have multiple edges and is formally defined by specifying a graph G and assigning a multiplicity to each edge of G. We examine underlying strongly regular multigraphs in order to further clarify their properties, specifically with regard to combinatorial configurations. -
Geodesic Leech Graphs
Seena Varghese, Aparna Lakshmannan S., S. ArumugamDas Kapitel vertieft sich in das Konzept der geodätischen Blutegel-Diagramme, einer Verallgemeinerung der Blutegelbäume auf alle Diagramme. Es definiert die geodätische Egelmarkierung und untersucht die geodätische Pfadzahl verschiedener Graphenklassen. Die Autoren identifizieren vier unendliche Familien geodätischer Blutegelgraphen und beweisen, dass bestimmte Zyklen, wie das Fünfeck, keine geodätischen Blutegelgraphen sind. Das Kapitel stellt auch das Konzept nahezu geodätischer Blutegelgraphen vor und wirft mehrere offene Probleme für die weitere Forschung auf.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractLet \(f:E\rightarrow \{1,2,3,\dots \}\) be an edge labeling of G. The weight of a path P is the sum of the labels assigned to the edges of P. The edge labeling f is called a geodesic Leech labeling, if the set of weights of the geodesic paths in G is \(\{1,2,3,\dots ,t_{gp}(G)\}\), where \(t_{gp}(G)\), the geodesic path number of G, is the number of geodesic paths in G. A graph which admits a geodesic Leech labeling is called a geodesic Leech graph. In this chapter, we prove the existence of infinite families of geodesic Leech graphs. It is also proved that \(C_5\) is not a geodesic Leech graph. Some open problems in this area are also included. -
Characterizing s-Strongly Chordal Graphs Using 2-Paths and k-Chords
Terry A. McKeeDas Kapitel vertieft sich in die Charakterisierung von s-stark-Akkordgraphen, einer speziellen Klasse von Graphen mit starken Konnektivitätseigenschaften. Es beginnt mit der Definition von Schlüsselbegriffen wie k-Akkorde und 2-Pfade und baut dann auf historischen Charakterisierungen auf, um eine neue, allgemeine Charakterisierung von s-stark-Akkordgraphen einzuführen. Das Kapitel untersucht die Beziehung zwischen diesen Graphen und 2-Pfad-Subgraphen und bietet Einblicke in ihre Struktur und Eigenschaften. Sie stellt auch eine logische Konsequenz dar, die unterschiedliche historische Motivationen vereint und eine neue Perspektive auf das Thema bietet. Das Kapitel ist ein Pflichtlektüre für alle, die sich für die neuesten Entwicklungen in der Graphentheorie und Kombinatorik interessieren.KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
AbstractA well-known 1961 characterization of chordal graphs by G. A. Dirac in terms of simplicial vertices, was extended by Chvátal, Rusu, and Sritharan (Discrete Math., 2002) to a natural sequence of “weakly chordal graphs.” Somewhat similarly, we will start from the same place and characterize a natural sequence of “chordal, strongly chordal, …, s-strongly chordal, …” graphs, except now in terms of 2-path graphs (meaning graphs that are either \(K_3\) or a 2-tree graph with exactly two degree-2 vertices—equivalently, “paths of triangles” that are the 2-connected outerplanar strongly chordal graphs).
- Titel
- Combinatorics, Graph Theory and Computing
- Herausgegeben von
-
Sarah Heuss
Richard Low
John C. Wierman
- Copyright-Jahr
- 2024
- Verlag
- 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
Die PDF-Dateien dieses Buches entsprechen nicht vollständig den PDF/UA-Standards, bieten jedoch eingeschränkte Bildschirmleseunterstützung, beschriebene nicht-textuelle Inhalte (Bilder, Grafiken), Lesezeichen zur einfachen Navigation sowie durchsuchbaren und auswählbaren Text. Nutzer von unterstützenden Technologien können Schwierigkeiten bei der Navigation oder Interpretation der Inhalte in diesem Dokument haben. Wir sind uns der Bedeutung von Barrierefreiheit bewusst und freuen uns über Anfragen zur Barrierefreiheit unserer Produkte. Bei Fragen oder Bedarf an Barrierefreiheit kontaktieren Sie uns bitte unter accessibilitysupport@springernature.com
