Search

Let T n denote the path-tree of the complete graph K n , we show that the matching polynomial μ (T n , x) of T n is equal to μ (K n , x) ∏ i = 2 n − 1 μ (K i , x) ∏ j = i − 1 , j ≠ i n − 1 j. This result has a number of consequences. It follows that the roots of μ (T n , x) (or the eigenvalues of T n), the (matching) energy of T n , and the Hosoya index of T n can all be obtained directly from that of complete graphs K i (1 ≤ i ≤ n). [ABSTRACT FROM AUTHOR]

This paper makes progress towards settling the long standing conjecture that the total chromatic number χ ′ ′ of the complete p -partite graph K = K (r 1 , ... , r p) is Δ (K) + 1 if and only if K ≠ K r , r and if K has an even number of vertices then Σ v ∈ V (K) (Δ (K) − d K (v)) is at least the number of parts of odd size. The conjecture has been verified by Chew and Yap (1992) when r 1 < r 2 (with parts arranged in non-decreasing order). Using the amalgamation technique, the authors in 2016 verified the conjecture when r 2 < r 3 . Graphs of even order that are fairly close to being regular are the ones for which χ ′ ′ remains in doubt, where the traditional proof techniques have limitations. In this paper, we use the amalgamation technique to provide sufficient condition for K with sizes of the parts differing by at most 1 (closest to being regular) to have χ ′ ′ (K) = Δ (K) + 1. Using this result, we prove that the conjecture holds when r 3 < r 4 . [ABSTRACT FROM AUTHOR]

In 1964, Moon extended Cayley's formula to a nice expression of the number of spanning trees in complete graphs containing any fixed spanning forest. After nearly 60 years, Dong and the first author discovered the second Moon-type formula: an explicit formula of the number of spanning trees in complete bipartite graphs containing any fixed spanning forest. Followed this direction, Li, Chen and Yan found the Moon-type formula for complete 3- and 4-partite graphs. These are the only families of graphs that have the corresponding Moon-type formulas. In this paper, we first determine resistance distances in the vertex-weighted complete split graph S m , n ω. Then we obtain the Moon-type formula for the vertex-weighted complete split graph S m , n ω , that is, the weighted spanning tree enumerator of S m , n ω containing any fixed spanning forest. [ABSTRACT FROM AUTHOR]

Let V be a set of points in the plane, and T the edge set of a minimum spanning tree of the complete graph induced by V. We prove that partitioning every edge of T into k equal parts, under Mahalanobis-norm, yields a Minimum Spanning Tree on the new set of points. We also prove that partitioning every edge of T in any symmetric way, under the Euclidean norm in 2-dimension space, yields a Minimum Spanning Tree on the new set of points. However, these properties break down under the ℓ 1 or ℓ ∞ norms. [ABSTRACT FROM AUTHOR]

Based on work presented in [S. R. Lippold, M. D. Staic and A. Stancu, Edge partitions of the complete graph and a determinant-like function, Monatsh. Math. 198 (2022) 819–858], we define S2-Upper Triangular Matrices and S2-Lower Triangular Matrices, two special types of d × d(2d − 1) matrices generalizing Upper and Lower Triangular Matrices, respectively. Then, we show that the property that the determinant of an Upper Triangular Matrix is the product of its diagonal entries is generalized under our construction. Further, we construct the algebra of S2-Upper Triangular Matrices and give conditions for an LU-Decomposition with S2-Lower Triangular and S2-Upper Triangular Matrices, respectively. [ABSTRACT FROM AUTHOR]

ABSTRACT The anti‐Ramsey number ar ( n , F ) $\text{ar}(n,F)$ of an r $r$ ‐graph F $F$ is the minimum number of colors needed to color the complete n $n$ ‐vertex r $r$ ‐graph to ensure the existence of a rainbow copy of F $F$ . We establish a removal‐type result for the anti‐Ramsey problem of F $F$ when F $F$ is the expansion of a hypergraph with a smaller uniformity. We present two applications of this result. First, we refine the general bound ar ( n , F ) = ex ( n , F − ) + o ( n r ) $\text{ar}(n,F)=\text{ex}(n,{F}_{-})+o({n}^{r})$ proved by Erdős–Simonovits–Sós, where F − ${F}_{-}$ denotes the family of r $r$ ‐graphs obtained from F $F$ by removing one edge. Second, we determine the exact value of ar ( n , F ) $\text{ar}(n,F)$ for large n $n$ in cases where F $F$ is the expansion of a specific class of graphs. This extends results of Erdős–Simonovits–Sós on complete graphs to the realm of hypergraphs. [ABSTRACT FROM AUTHOR]

In 1977, Erdős asked the following question: for any integers t,n∈N$t,n \in \mathbb {N}$, if G1,⋯,Gn$G_1, \dots, G_n$ are complete graphs such that each Gi$G_i$ has at most n$n$ vertices and every pair of them shares at most t$t$ vertices, what is the largest possible chromatic number of the union ⋃i=1nGi$\bigcup _{i=1}^{n} G_i$? The equivalent dual formulation of this question asks for the largest chromatic index of an n$n$‐vertex hypergraph with maximum degree at most n$n$ and maximum codegree at most t$t$. For the case t=1$t = 1$, Erdős, Faber and Lovász famously conjectured that the answer is n$n$, which was recently proved by the authors for all sufficiently large n$n$. In this paper, we answer this question of Erdős for t⩾2$t \geqslant 2$ in a strong sense, by proving that every n$n$‐vertex hypergraph with maximum degree at most (1−o(1))tn$(1-o(1))tn$ and maximum codegree at most t$t$ has chromatic index at most tn$tn$ for any t,n∈N$t,n \in \mathbb {N}$. Moreover, equality holds if and only if the hypergraph is a t$t$‐fold projective plane of order k$k$, where n=k2+k+1$n = k^2 + k + 1$. Thus, for every t∈N$t \in \mathbb {N}$, this bound is best possible for infinitely many integers n$n$. This result also holds for the list chromatic index. [ABSTRACT FROM AUTHOR]

An orientable vertex primitive complete map is a two-cell embedding of a complete graph into an orientable surface such that the automorphism group of this map acts primitively on its vertex set. The paper is devoted to the problem of enumerating orientable vertex primitive complete maps. For a given integer n, we derive the number of different such maps with n vertices. Furthermore, we obtain explicit formulas for the numbers of non-isomorphic orientable vertex primitive complete maps with n vertices. [ABSTRACT FROM AUTHOR]

The { K 1 , 1 , K 1 , 2 , ... , K 1 , k , (2 k + 1) } -factor and { K 1 , 2 , K 1 , 3 , K 5 } -factor of a graph are a spanning subgraph whose each component is an element of { K 1 , 1 , K 1 , 2 , ... , K 1 , k , (2 k + 1) } and { K 1 , 2 , K 1 , 3 , K 5 } , respectively, where (2 k + 1) is a special family of trees. In this paper, we obtain a sufficient condition in terms of tight toughness, isolated toughness and binding number bounds to guarantee the existence of a { K 1 , 1 , K 1 , 2 , ... , K 1 , k , (2 k + 1) } -factor and { K 1 , 2 , K 1 , 3 , K 5 } -factor for any graph. [ABSTRACT FROM AUTHOR]

Given graphs H $H$ and F $F$, ex(n,H,F) $\text{ex}(n,H,F)$ denotes the largest number of copies of H $H$ in F $F$‐free n $n$‐vertex graphs. Let χ(H)<χ(F)=r+1 $\chi (H)\lt \chi (F)=r+1$. We say that H $H$ is F‐Turán‐stable if the following holds. For any ε>0 $\varepsilon \gt 0$ there exists δ>0 $\delta \gt 0$ such that if an n $n$‐vertex F $F$‐free graph G $G$ contains at least ex(n,H,F)−δn∣V(H)∣ $\text{ex}(n,H,F)-\delta {n}^{| V(H)| }$ copies of H $H$, then the edit distance of G $G$ and the r $r$‐partite Turán graph is at most εn2 $\varepsilon {n}^{2}$. We say that H $H$ is weakly F‐Turán‐stable if the same holds with the Turán graph replaced by any complete r $r$‐partite graph T $T$. It is known that such stability implies exact results in several cases. We show that complete multipartite graphs with chromatic number at most r $r$ are weakly Kr+1 ${K}_{r+1}$‐Turán‐stable. Partly answering a question of Morrison, Nir, Norin, Rzażewski, and Wesolek positively, we show that for every graph H $H$, if r $r$ is large enough, then H $H$ is Kr+1 ${K}_{r+1}$‐Turán‐stable. Finally, we prove that if H $H$ is bipartite, then it is weakly C2k+1 ${C}_{2k+1}$‐Turán‐stable for k $k$ large enough. [ABSTRACT FROM AUTHOR]

In 1992, Godsil and Hensel published a ground-breaking study of distance-regular antipodal covers of the complete graph that, among other things, introduced an important connection with equi-isoclinic subspaces. This connection seems to have been overlooked, as many of its immediate consequences have never been detailed in the literature. To correct this situation, we first describe how Godsil and Hensel's machine uses representation theory to construct equi-isoclinic tight fusion frames. Applying this machine to Mathon's construction produces q + 1 equi-isoclinic planes in R q + 1 for any even prime power q > 2. Despite being an application of the 30-year-old Godsil–Hensel result, infinitely many of these parameters have never been enunciated in the literature. Following ideas from Et-Taoui, we then investigate a fruitful interplay with complex symmetric conference matrices. [ABSTRACT FROM AUTHOR]

Large‐scale geological storage of carbon dioxide (CO2) is indispensable for mitigating climate change but faces significant challenges, especially in the accurate quantitative assessment of leakage risks to ensure long‐term security. Given these circumstances, this paper proposes an innovative approach for quantitatively assessing CO2 leakage risk to address the previous limitations of limited accuracy and insufficient data. We construct a fault tree and transform it into a Bayesian network–directed acyclic graph, and then use judgment sets along with fuzzy set theory to obtain prior probabilities of root nodes. The feature, event, and process method was utilized to identify key components and subsequently determine the conditional probability table (CPT) of the leaf node. The subjective experience assessments from experts are defuzzified to obtain the CPTs of intermediate nodes. The obtained basic probability parameters are input into the directed acyclic graph to complete the model construction. After calculating the leakage probability using this model, it is combined with the severity of impacts to conduct a comprehensive risk assessment. Furthermore, critical CO2 risk sources can be determined through posterior probability calculations when intermediate nodes are designated as deterministic risk events. The gradual implementation process of the proposed model is demonstrated via a typical case study. The results indicate an overall CO2 leakage probability of 29%, with probabilities of leakage along faults/fractures, caprock, and well identified as 32%, 28%, and 19%, respectively. The project is categorized as a medium‐low risk level. When leakage is confirmed, tectonic movement, thickness, and delamination at interface connections/the presence of cracks are the critical risk sources, and measures to mitigate key risks are outlined. The identified key risk factors conform to empirical evidence and previous research, validating the accuracy of the model. This study is instrumental in CO2 geological storage risk assessment and scalable development program design. © 2024 Society of Chemical Industry and John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Given an input graph Gin=(V,Ein) , we consider the problem of designing a sparse subgraph G=(V,E) with E⊆Ein that supports a large matching after some nodes in V are randomly deleted. We study four families of sparse graph designs (namely, clusters, rings, chains, and Erdős–Rényi graphs) and show both theoretically and numerically that their performance is close to the optimal one achieved by a complete graph. Our interest in the stochastic sparse graph design problem is primarily motivated by a collaboration with a leading e-commerce retailer in the context of its middle-mile delivery operations. We test our theoretical results using real data from our industry partner and conclude that adding a little flexibility to the routing network can significantly reduce transportation costs. This paper was accepted by David Simchi-Levi, optimization. Funding: This work was supported by the University of Chicago Booth School of Business, an Alibaba Cainiao Research Grant, and the Singapore Ministry of Education [NUS Startup Grant WBS A-0003856-00-00]. Supplemental Material: Data and the online appendix are available at https://doi.org/10.1287/mnsc.2022.01588. [ABSTRACT FROM AUTHOR]

An H-decomposition of a graph Γ is a partition of its edge set into subgraphs isomorphic to H. A transitive decomposition is a special kind of H-decomposition that is highly symmetrical in the sense that the subgraphs (copies of H) are preserved and transitively permuted by a group of automorphisms of Γ . This paper concerns transitive H-decompositions of the graph K n □ K n where H is a path. When n is an odd prime, we present a construction for a transitive path decomposition where the paths in the decomposition are considerably large compared to the number of vertices. Our main result supports well-known Gallai's conjecture and an extended version of Ringel's conjecture. [ABSTRACT FROM AUTHOR]

A (v, k, t) packing of size b is a system of b subsets (blocks) of a v-element underlying set such that each block has k elements and every t-set is contained in at most one block. P(v, k, t) stands for the maximum possible b. A packing is called abundant if b > v . We give new estimates for P(v, k, t) around the critical range, slightly improving the Johnson bound and asymptotically determine the minimum v = v 0 (k , t) when abundant packings exist. For a graph G and a positive integer c, let χ ℓ (G , c) be the minimum value of k such that one can properly color the vertices of G from any assignment of lists L(v) such that | L (v) | = k for all v ∈ V (G) and | L (u) ∩ L (v) | ≤ c for all u v ∈ E (G) . Kratochvíl, Tuza and Voigt in 1998 asked to determine lim n → ∞ χ ℓ (K n , c) / cn (if it exists). Using our bound on v 0 (k , t) , we prove that the limit exists and equals 1. Given c, we find the exact value of χ ℓ (K n , c) for infinitely many n. [ABSTRACT FROM AUTHOR]

Intelligent detection of the apparent defects of tunnel linings on the basis of deep learning has become a mainstream trend, and how to objectively diagnose the hazard level of tunnel defects via semantic segmentation images is the key to intelligent control of tunnel health. In this study, a tunnel lining defect image diagnosis method that uses graph neural networks is proposed. First, the binary images obtained by semantic segmentation are used as the data set, and quantitative parameters, such as crack length, maximum width, box dimension, and area density, are calculated according to the crack orientation and employed as graph node attributes. Second, the construction of graph data is based on the similarity of defect attributes. Third, clustering is completed using graph neural networks and K-means, and the number of clusters and danger levels of crack defects are reasonably determined. Last, a tunnel crack risk index is developed via partial least squares regression analysis, and the grading criteria for defect levels are established. Results show that the method is effective in extracting the key attributes of crack images and clustering them into different hazard levels, which is important for maintaining tunnel health. [ABSTRACT FROM AUTHOR]

The extremal problem of two types of high order spectra for graphs are considered, which are called r -adjacency spectrum and t -clique spectrum, respectively. In this paper, we obtain the maximum r -adjacency spectral radius of a K r + 1 minor-free graph of order n in the case 1 ≤ r ≤ 3 , which implies the Hadwiger's conjecture is true for 1 ≤ r ≤ 3. Moreover, an upper bound of the 3-clique spectral radius of a B k -free and K 2 , l -free graph G of order n is given, where B k is the graph consisting of k triangles sharing an edge. As a corollary of this result, we obtain an upper bound of the number of the triangles for G which improves a result of Alon and Shikhelman (2016). [ABSTRACT FROM AUTHOR]

An s-pair state in a graph is a quantum state of the form e u + s e v , where u and v are vertices in the graph and s is a nonzero complex number. If s = - 1 (resp., s = 1 ), then such a state is called a pair state (resp. plus state). In this paper, we develop the theory of perfect s-pair state transfer in continuous quantum walks, where the Hamiltonian is taken to be the adjacency, Laplacian or signless Laplacian matrix of the graph. We characterize perfect s-pair state transfer in complete graphs, cycles and antipodal distance-regular graphs admitting vertex perfect state transfer. We construct infinite families of graphs with perfect s-pair state transfer using quotient graphs and graphs that admit fractional revival. We provide necessary and sufficient conditions such that perfect state transfer between vertices in the line graph relative to the adjacency matrix is equivalent to perfect state transfer between the plus states formed by corresponding edges in the graph relative to the signless Laplacian matrix. Finally, we characterize perfect state transfer between vertices in the line graphs of Cartesian products relative to the adjacency matrix. [ABSTRACT FROM AUTHOR]

It is well known that networks are dynamic graphs, and the topology of a network can be described by a graph. Thus, the reliability of a network under edge failure is defined as the probability that its corresponding topological graph remains connected under the condition that the edges fail with independent probabilities. In this paper, the reliability of a class of two-layer networks is considered, where each layer is a complete graph and the edges joining different layers are one-to-one correspondingly connected. The edge failure probability is uniform in the same layer and distinct in different layers and between layers. The recursive formula for the reliability (reliability polynomial) of the two-layer network is obtained, and the corresponding algorithm is also given. Furthermore, the reliability of several networks is computed by Python, which verifies the correctness of the algorithm. [ABSTRACT FROM AUTHOR]

Given two graphs G,H $G,H$ and a positive integer q $q$, an (H,q) $(H,q)$‐coloring of G $G$ is an edge‐coloring of G $G$ such that every copy of H $H$ in G $G$ receives at least q $q$ distinct colors. The bipartite Erdős–Gyárfás function r(Kn,n,Ks,t,q) $r({K}_{n,n},{K}_{s,t},q)$ is defined to be the minimum number of colors needed for Kn,n ${K}_{n,n}$ to have a (Ks,t,q) $({K}_{s,t},q)$‐coloring. For balanced complete bipartite graphs Kp,p ${K}_{p,p}$, the function r(Kn,n,Kp,p,q) $r({K}_{n,n},{K}_{p,p},q)$ was studied systematically in Axenovich et al. In this paper, we study the asymptotic behavior of this function for complete bipartite graphs Ks,t ${K}_{s,t}$ that are not necessarily balanced. Our main results deal with thresholds and lower and upper bounds for the growth rate of this function, in particular for (sub)linear and (sub)quadratic growth. We also obtain new lower bounds for the balanced bipartite case, and improve several results given by Axenovich, Füredi and Mubayi. Our proof techniques are based on an extension to bipartite graphs of the recently developed Color Energy Method by Pohoata and Sheffer and its refinements, and a generalization of an old result due to Corrádi. [ABSTRACT FROM AUTHOR]

We prove that for every path H $H$, and every integer d $d$, there is a polynomial f $f$ such that every graph G $G$ with chromatic number greater than f(t) $f(t)$ either contains H $H$ as an induced subgraph, or contains as a subgraph the complete d $d$‐partite graph with parts of cardinality t $t$. For t=1 $t=1$ and general d $d$ this is a classical theorem of Gyárfás, and for d=2 $d=2$ and general t $t$ this is a theorem of Bonamy et al. [ABSTRACT FROM AUTHOR]

An ideal I of Q [ x 1 , ⋯ , x n ] is said to be m-absorbing if any monomial of total degree p > m belongs to I and if there is a monomial M of total degree m such that M ∉ I. Inspired by the fundamental work of Lechuga and Murillo (Topology 39:89–94, 2000) who established a connection between graph theory and rational homotopy theory, these paper aims to characterise the m-absorbing ideals of Q [ x 1 , ⋯ , x n ] generated by a family of complete homogeneous symmetric polynomials of the form P rs (k) = ∑ t = 1 k x r k - t x s t - 1 , where k ≥ 3. [ABSTRACT FROM AUTHOR]

The projective norm graphs are central objects to extremal combinatorics. They appear in a variety of contexts, most importantly they provide tight constructions for the Turán number of complete bipartite graphs K t , s with s > (t - 1) ! . In this note we deepen their understanding further by determining their automorphism group. [ABSTRACT FROM AUTHOR]

Evolutionary graph theory has considerably advanced the process of modelling the evolution of structured populations, which models the interactions between individuals as pairwise contests. In recent years, these classical evolution models have been extended to incorporate more realistic features, e.g. multiplayer games. A recent series of papers have developed a new evolutionary framework including structure, multiplayer interactions, evolutionary dynamics, and movement. However, so far, the developed models have mainly considered independent movement without coordinated behaviour. Although the theory underlying the framework has been developed and explored in various directions, several movement mechanisms have been produced which characterise coordinated movement, for example, herding. By embedding these newly constructed movement distributions, within the evolutionary setting of the framework, we demonstrate that certain levels of aggregation and dispersal benefit specific types of individuals. Moreover, by extending existing parameters within the framework, we are not only able to develop a general process of embedding any of the considered movement distributions into the evolutionary setting on complete graphs but also analytically produce the probability of fixation of a mutant on a complete N-sized network, for the multiplayer Public Goods and Hawk–Dove games. Also, by applying weak selection methods, we extended existing previous analyses on the pairwise Hawk–Dove Game to encompass the multiplayer version considered in this paper. By producing neutrality and equilibrium conditions, we show that hawks generally do worse in our models due to the multiplayer nature of the interactions. [ABSTRACT FROM AUTHOR]

A graph G is called perfect if ω (H) = χ (H) for every induced subgraph H of G , where ω (H) is the clique number of H and χ (H) its chromatic number. The Weak Perfect Graph Theorem of Lovász states that a graph G is perfect if and only if its complement G ‾ is perfect. This does not hold for box-perfect graphs, which are the perfect graphs whose stable set polytope is box-totally dual integral. We prove that both G and G ‾ are box-perfect if and only if G ‾ + is box-perfect, where G + is obtained by adding a universal vertex to G. Consequently, G + is box-perfect if and only if G ‾ + is box-perfect. As a corollary, we characterize when the complete join of two graphs is box-perfect. [ABSTRACT FROM AUTHOR]

The sum of absolute values of eigenvalues of a graph G is defined as energy of graph. If the energies of two non-isomorphic graphs are same then they are called equienergetic. The energy of complete graph with n vertices is 2(n - 1) and the graphs whose energy is equal to 2(n - 1) are called borderenergetic graphs. It has been revealed that the graphs upto 12 vertices are borderenergetic. It is very challenging and interesting as well to search for borderenergetic graphs with more than 14 vertices. The present work is leap ahead in this direction as we have found a family of borderenergetic graphs of arbitrarily large order. We have also obtained three pairs of equienergetic graphs. [ABSTRACT FROM AUTHOR]

We study the fashion game, a classical network coordination/anti-coordination game employed to model social dynamics in decision-making processes, especially in fashion choices. In this game, individuals, represented as vertices in a graph, make decisions based on their neighbors’ choices. Some individuals are positively influenced by their neighbors while others are negatively affected. Analyzing the game’s outcome aids in understanding fashion trends and flux within the population. In an instance of the fashion game, an action profile is formed when all individuals have made their choices. The utility of an individual under an action profile is defined according to the choices he and his neighbors made. A pure Nash equilibria is an action profile under which each individual has a nonnegative utility. To further study the existence of pure Nash equilibria, we investigate an associated optimization problem aimed at maximizing the minimal individual utility, referred to as the utility of a fashion game instance. The fashion game with two different but symmetric actions (choices) has been studied extensively in the literature. This paper seeks to extend the fashion game analysis to scenarios with more than two available actions, thereby enhancing comprehension of social dynamics in decision-making processes. We determine the utilities of all instances on paths, cycles and complete graphs. For instances where each individual likes to anti-coordinate, graph is planar and three actions are available, we illustrate the time complexity of determining the utility of such instances. Additionally, for instances containing both coordinating and anti-coordinating individuals, we extend the results on the time complexity of determining the utility of instances with two available actions to cases with more than two actions. [ABSTRACT FROM AUTHOR]

The modeling and analysis of epidemic processes in networks have attracted much attention over the past few decades. A major underlying assumption is that the recovery process and infection process are homogeneous, allowing the associated theoretical studies to be conducted in a convenient manner. However, the recovery and infection processes usually exhibit heterogeneous rates in the real world, which makes it difficult to characterize the general relations between the dynamics and the underlying network structure. In this work, we focus on the susceptible–infected–susceptible (SIS) epidemic process with heterogeneous recovery rates in a finite-size complete graph. Specifically, we study the metastable-state statistical properties of SIS epidemic dynamics with two different nodal recovery rates in complete graphs. We propose approximate solutions to the metastable-state expectation and the variance in the number of infected nodes within the framework of the mean-field approximation method. We also derive several upper and lower bounds of the steady-state probability that a node is in the infected state. We verify the proposed approximate solutions of the mean and variance via simulations. This work provides insights into the fluctuations in the statistical properties of epidemic processes with complex dynamical behaviors in networks. [ABSTRACT FROM AUTHOR]

This paper introduces an algorithm to construct a bidirectional causal graph using an augmented graph. The algorithm decomposes the augmented graph, significantly reducing the size of the variable set required for conditional independence testing. Simultaneously, it preserves the fundamental structure of the augmented graph after decomposition, saving time and cost in constructing a global skeleton graph. Through experiments on discrete and continuous datasets, the algorithm demonstrates a clear advantage in runtime compared to traditional methods. In large-scale sparse networks, the training time is only about one-tenth of traditional methods. Additionally, the algorithm shows improvement in terms of construction error. Since the input to the algorithm is an augmented graph, this paper also discusses the impact on construction error when using both real and generated augmented graphs as input. Furthermore, the concept of markov blanket is extended to multivariate regression chain graphs, providing a method for rapidly constructing augmented graphs given certain prior knowledge. [ABSTRACT FROM AUTHOR]

For each surface besides the sphere, projective plane, and Klein bottle, we construct a face‐simple minimal quadrangulation, that is, a simple quadrangulation on the fewest number of vertices possible, whose dual is also a simple graph. Our result answers a question of Liu, Ellingham, and Ye while providing a simpler proof of their main result. The inductive construction is based on an earlier idea for finding near‐quadrangular embeddings of the complete graphs using the diamond sum operation. [ABSTRACT FROM AUTHOR]

We applied the Ramsey analysis to the sets of points belonging to Riemannian manifolds. The points are connected with two kinds of lines: geodesic and non-geodesic. This interconnection between the points is mapped into the bi-colored, complete Ramsey graph. The selected points correspond to the vertices of the graph, which are connected with the bi-colored links. The complete bi-colored graph containing six vertices inevitably contains at least one mono-colored triangle; hence, a mono-colored triangle, built of the green or red links, i.e., non-geodesic or geodesic lines, consequently appears in the graph. We also considered the bi-colored, complete Ramsey graphs emerging from the intersection of two Riemannian manifolds. Two Riemannian manifolds, namely (M 1 , g 1) and (M 2 , g 2) , represented by the Riemann surfaces which intersect along the curve (M 1 , g 1) ∩ (M 2 , g 2) = ℒ were addressed. Curve ℒ does not contain geodesic lines in either of the manifolds   (M 1 , g 1) and (M 2 , g 2) . Consider six points located on the ℒ :   { 1 , ... 6 } ⊂ ℒ . The points { 1 , ... 6 } ⊂ ℒ are connected with two distinguishable kinds of the geodesic lines, namely with the geodesic lines belonging to the Riemannian manifold (M 1 , g 1) /red links, and, alternatively, with the geodesic lines belonging to the manifold (M 2 , g 2) /green links. Points { 1 , ... 6 } ⊂ ℒ form the vertices of the complete graph, connected with two kinds of links. The emerging graph contains at least one closed geodesic line. The extension of the theorem to the Riemann surfaces of various Euler characteristics is presented. [ABSTRACT FROM AUTHOR]

This paper investigates the significance of employing random subgraphs and analyzing the expected values of Zagreb ndices within chemical graphs. By examining smaller, representative subsets, we uncover valuable insights into the properties and characteristics of complex networks. The expected values of Zagreb indices serve as critical mathematical measures for quantifying the structural complexity of chemical graphs, providing essential information about connectivity and branching patterns within molecules. Our primary contribution includes deriving theoretical expressions for these indices and validating them through extensive computational experiments on fullerene graphs C 20 and C 60 . The results demonstrate that our theoretical predictions closely align with experimental findings, affirming the robustness of Zagreb indices in characterizing molecular structures. Additionally, our analysis of specific cases, such as complete graphs and complete bipartite graphs, is consistent with previous studies, further reinforcing our methodology. This research emphasizes the relevance of random subgraphs and expected values of Zagreb indices in advancing our understanding of molecular behavior and stability, with important implications for materials science and drug design. [ABSTRACT FROM AUTHOR]

Topological indices are numeric quantities that describes the topology of molecular structure in mathematical chemistry. One of these indices is the neighborhood version of the hyper Zagreb index, HMN. The neighborhood version of the hyper Zagreb index is expressed as the sum over all pairs of adjacent vertices a and b of the terms [δG(a) + δG(b)]2, where δG(a) is the neighborhood degree sum of the vertex a which is the sum of degrees of all of its neighboring vertices. In this paper, we show that over all simple connected graphs, the path graph Pn has the minimum value of HMN and the complete graph Kn has the maximum value of HMN. Also, we give the minimum value of this index within the set of trees with given vertices number and maximum vertex degree and specify the minimal trees. [ABSTRACT FROM AUTHOR]

In this paper, based on the Diophantine equation technique, we first prove the circulant graph C (Z n , { k 1 , k 2 }) is isomorphic to the disjoint union of gcd (n , k 1 , k 2) identical graphs, which belong to one of the three types of graphs: (i) C (Z n { 1 , k }) ; (i i) the Cartesian graph bundle C s □ φ C t over cycles; (i i i) the Cartesian product of the complete graph K 2 and a cycle. Naturally, to study the dispersability of C (Z n , { k 1 , k 2 }) can be reduced to study that of the above three types. Next, we solve the dispersability of the circulant graph C (Z n , { 1 , k }). Specifically, C (Z n , { 1 , k }) is dispersable if it is a bipartite; otherwise, it is nearly dispersable. In addition, we prove that bipartite circulant graphs are dispersable. [ABSTRACT FROM AUTHOR]

This research is focused on evolutionary algorithms, with genetic and memetic algorithms discussed in more detail. A graph theory problem related to finding a minimal Hamiltonian cycle in a complete undirected graph (Travelling Salesman Problem—TSP) is considered. The implementations of two approximate algorithms for solving this problem, genetic and memetic, are presented. The main objective of this study is to determine the influence of the local search method versus the influence of the genetic crossover operator on the quality of the solutions generated by the memetic algorithm for the same input data. The results show that when the number of possible Hamiltonian cycles in a graph is increased, the memetic algorithm finds better solutions. The execution time of both algorithms is comparable. Also, the number of solutions that mutated during the execution of the genetic algorithm exceeds 50% of the total number of all solutions generated by the crossover operator. In the memetic algorithm, the number of solutions that mutate does not exceed 10% of the total number of all solutions generated by the crossover operator, summed with those of the local search method. [ABSTRACT FROM AUTHOR]

The paper introduces the concept of graph decomposition. That is orthogonal decompositions. Orthogonal decompositions of a graph H are a partitioning H into subgraphs of H such that any two subgraphs intersect in at most one edge. These decompositions are called G-orthogonal decompositions of H if and only if every subgraph in such decompositions is isomorphic to the graph G. Such decomposition appears in a lot of applications; statistics, information theory, in the theory of experimental design, and many others. An approach of constructing orthogonal decompositions of regular graphs is introduced here. Application to this approach for constructing tree - orthogonal decompositions of complete bipartite graphs is considered. Further, the use of orthogonal decompositions for designing tree hamming codes is also discussed along with examples. The study shows that such codes have efficient properties when used to detect and correct the errors that may occur during the transmission of data through a network. Furthermore, we present a method for the recursive construction of orthogonal decompositions. [ABSTRACT FROM AUTHOR]

In graph theory, graph labeling is an essential area of study because labeled graphs offer useful mathematical models for coding theory, cryptography, astronomy, radar, database administration and communication networks. Consider a bijection for a graph G of order n, f : V (G) → {1, 2, ..., n}. The weight of a vertex z of G, expressed as w(z), is defined as the sum of labels assigned to all vertices adjacent to vertex z in G. If the weights are distinct for every unique pair of vertices y, z in V (G), then the labeling f is referred to as distance antimagic. A distance antimagic graph is any graph G that accepts such a labeling. Distance antimagic labeling on various basic graph products are discussed in this paper. We explore results on (a, d)-distance antimagic labeling for the lexicographic product G * H and distance antimagic labeling for the cartesian product G * H, tensor product G x H and strong product G x H in this work, where the graphs G and H are cycle related graphs, paths or complete graphs. Also, computer-aided algorithms are designed to verify that vertex weights are distinct. [ABSTRACT FROM AUTHOR]

Low-rank approximation has emerged as a promising technique for recovering five-dimensional (5D) seismic data, yet the quest for higher accuracy and stronger rank robustness remains a critical pursuit. We introduce a low-rank approximation method by leveraging the complete graph tensor network (CGTN) decomposition and the learnable transform (LT), referred to as the LRA-LTCGTN method, to simultaneously denoise and reconstruct 5D seismic data. In the LRA-LTCGTN framework, the LT is employed to project the frequency tensor of the original 5D data onto a small-scale latent space. Subsequently, the CGTN decomposition is executed on this latent space. We adopt the proximal alternating minimization algorithm to optimize each variable. Both 5D synthetic data and field data examples indicate that the LRA-LTCGTN method exhibits notable advantages and superior efficiency compared to the damped rank-reduction (DRR), parallel matrix factorization (PMF), and LRA-CGTN methods. Moreover, a sensitivity analysis underscores the remarkably stronger robustness of the LRA-LTCGTN method in terms of rank without any optimization procedure with respect to rank, compared to the LRA-CGTN method. [ABSTRACT FROM AUTHOR]

In this paper, we prove necessary conditions for Hibi rings to satisfy Green–Lazarsfeld property N p for p = 2 and 3. We also show that if a Hibi ring satisfies property N 4 , then it is a polynomial ring or it has a linear resolution. Therefore, it satisfies property N p for all p ≥ 4 as well. As a consequence, we characterize distributive lattices whose comparability graph is chordal in terms of the subposet of join-irreducibles of the distributive lattice. Moreover, we characterize complete intersection Hibi rings. [ABSTRACT FROM AUTHOR]

This paper presents three novel encryption and decryption schemes based on graph theory that aim to improve security and error resistance in communication networks. The novelty of this work lies in the application of complete bipartite graphs in two of the schemes and the Cartesian product of graphs in the third, representing a unique approach to cryptographic algorithm development. Unlike traditional cryptographic methods, these graph-based schemes use structural properties of graphs to achieve robust encryption, providing greater resistance to attacks and corruption. Each scheme is illustrated with detailed examples that show how the algorithms can be successfully implemented. The algorithms are written in standard mathematical notation, making them adaptable for machine implementation and scalable for real-world use. The schemes are also rigorously analyzed and compared in terms of their temporal and spatial complexities, using Big O notation. This comprehensive evaluation focuses on their effectiveness, providing valuable insights into their potential for secure communication in modern networks. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the phenomena of order-disorder phase transition and the universality of the majority-rule model defined on three complex networks, namely the Barabási–Albert, Watts–Strogatz and Erdős–Rényi networks. Assume each agent holds two possible opinions randomly distributed across the networks' nodes. Agents adopt anticonformity and independence behaviors, represented by the probability p, where with a probability p, agents adopt anticonformity or independence behavior. Based on our numerical simulation results and finite-size scaling analysis, it is found that the model undergoes a continuous phase transition for all networks, with critical points for the independence model greater than those for the anticonformity model in all three networks. We obtain critical exponents identical to the opinion dynamics model defined on a complete graph, indicating that the model exhibits the same universality class as the mean-field Ising model. [ABSTRACT FROM AUTHOR]

Given positive integers k ≤ d and a finite field F , a set S ⊂ F d is (k, c)-subspace evasive if every k-dimensional affine subspace contains at most c elements of S. By a simple averaging argument, the maximum size of a (k, c)-subspace evasive set is at most c | F | d - k . When k and d are fixed, and c is sufficiently large, the matching lower bound Ω (| F | d - k) is proved by Dvir and Lovett. We provide an alternative proof of this result using the random algebraic method. We also prove sharp upper bounds on the size of (k, c)-evasive sets in case d is large, extending results of Ben-Aroya and Shinkar. The existence of optimal evasive sets has several interesting consequences in combinatorial geometry. We show that the minimum number of k-dimensional linear hyperplanes needed to cover the grid [ n ] d ⊂ R d is Ω d (n d (d - k) d - 1 ) , which matches the upper bound proved by Balko et al., and settles a problem proposed by Brass et al. Furthermore, we improve the best known lower bound on the maximum number of incidences between points and hyperplanes in R d assuming their incidence graph avoids the complete bipartite graph K c , c for some large constant c = c (d) . [ABSTRACT FROM AUTHOR]

The concept of Roman domination has been a subject of intrigue for more than two decades, with the fundamental Roman domination problem standing out as one of the most significant challenges in this field. This article studies a practically motivated generalization of this problem, known as the k-strong Roman domination. In this problem variant, defenders within a network are tasked with safeguarding any k vertices simultaneously, under multiple attacks. The aim is to find a feasible mapping that assigns a (integer) weight to each vertex of the input graph with a minimum sum of weights across all vertices. A function is considered feasible if any non-defended vertex, i.e. one labeled by zero, is protected by at least one of its neighboring vertices labeled by at least two. Furthermore, each defender ensures the safety of a non-defended vertex by imparting a value of one to it while retaining a one for themselves. To the best of our knowledge, this paper represents the first theoretical study on this problem. The study presents results for general graphs, establishes connections between the problem at hand and other domination problems, and provides exact values and bounds for specific graph classes, including complete graphs, paths, cycles, complete bipartite graphs, grids, and a few selected classes of convex polytopes. Additionally, an attainable lower bound for general cubic graphs is provided. [ABSTRACT FROM AUTHOR]

Rainbow antimagic coloring is the combination of antimagic labeling and rainbow coloring. The smallest number of colors induced from all edge weights of antimagic labeling is the rainbow antimagic connection number of G , denoted by rac (G). Given a graph G with vertex set V (G) and edge set E (G) , the function f from V (G) to { 1 , 2 , ... , | V (G) | } is a bijective function. The associated weight of an edge y z ∈ E (G) under f is w (y z) = f (y) + f (z). A path R in the vertex-labeled graph G is said to be a rainbow y − z path if for any two edges y z , y ′ z ′ ∈ E (R) it satisfies w (y z) ≠ w (y ′ z ′). The function f is called a rainbow antimagic labeling of G if there exists a rainbow y − z path for every two vertices y , z ∈ V (G). When we assign each edge y z with the color of the edge weight w (y z) , we say the graph G admits a rainbow antimagic coloring. In this paper, we show the new lower bound and exact value of the rainbow antimagic connection number of comb product of any tree and complete bipartite graph. [ABSTRACT FROM AUTHOR]

In this paper we study invasion probabilities and invasion times of cooperative parasites spreading in spatially structured host populations. The spatial structure of the host population is given by a random geometric graph on [ 0 , 1 ] n , n ∈ N , with a Poisson (N) -distributed number of vertices and in which vertices are connected over an edge when they have a distance of at most r N with r N of order N (β − 1) / n for some 0 < β < 1. At a host infection many parasites are generated and parasites move along edges to neighbouring hosts. We assume that parasites have to cooperate to infect hosts, in the sense that at least two parasites need to attack a host simultaneously. We find lower and upper bounds on the invasion probability of the parasites in terms of survival probabilities of branching processes with cooperation. Furthermore, we characterize the asymptotic invasion time. An important ingredient of the proofs is a comparison with infection dynamics of cooperative parasites in host populations structured according to a complete graph, i.e. in well-mixed host populations. For these infection processes we can show that invasion probabilities are asymptotically equal to survival probabilities of branching processes with cooperation. Furthermore, we build on proof techniques developed in Brouard and Pokalyuk (2022), where an analogous invasion process has been studied for host populations structured according to a configuration model. We substantiate our results with simulations. [ABSTRACT FROM AUTHOR]

In these crucial times of COVID-19, cryptographic and nature inspired innovations help to communicate confidential data in the wireless telemedicine. The novel corona virus had entirely shattered all segments of life in the entire world. In the medical sciences, patients are more advised to take telemedicine supports. Cardiac patients are very much prone to corona virus. They need to transmit confidential medical data for their online treatments. Such heterogeneous cardiac information is to be protected with patients' confidentiality. It is very noteworthy to impose high security features on the COVID-19 "New Normal" telecardiology. In this paper, we have designed a cryptographic system based on metaheuristic Harmony search algorithm and tree parity machines. It has been proposed to counter attack against different security hazards in online medical transactions during this tremendous flooded COVID-19 time. The proposed method has been modularized into four modules. These are: Neuro-Metaheuristic Session Key (NMSK) generation, Cryptographic Engineering, Frame format generation, and authentication and decryption phase. Harmony search with tree parity machines were used to generate the key i.e. NMSK. A new state-of-art sharing was proposed to dilute the information contents inside the telemedicine networks against the intruders. Moreover, the proposed state-of-art sharing exhibits the complete bi-partite graph property. A rigorous frame format has been placed before the encrypted message inside the COVID-19 telecardiology. Different types of statistical and mathematical tests were carried out on the proposed technique to prove its efficacy. Thus, the proposed cryptographic system acts as a reinforcement of security mechanism in COVID-19 telecardiology. [ABSTRACT FROM AUTHOR]

The Single-Source Shortest Paths (SSSP) graph problem is a fundamental computation. This study attempted to characterize concretely the energy behaviors of the two primary methods to solve it, the Bellman–Ford and Dijkstra algorithms. The very different interactions of the algorithms with the hardware may have significant implications for energy. The study was motivated by the multidisciplinary nature of the problem. Gaining better insights should help vital applications in many domains. The work used reliable embedded sensors in an HPC-class CPU to collect empirical data for a wide range of sizes for two graph cases: complete as an upper-bound case and moderately dense. The findings confirmed that Dijkstra's algorithm is drastically more energy efficient, as expected from its decisive time complexity advantage. In terms of power draw, however, Bellman–Ford had an advantage for sizes that fit in the upper parts of the memory hierarchy (up to 2.36 W on average), with a region of near parity in both power draw and total energy budgets. This result correlated with the interaction of lighter logic and graph footprint in memory with the Level 2 cache. It should be significant for applications that rely on solving a lot of small instances since Bellman–Ford is more general and is easier to implement. It also suggests implications for the design and parallelization of the algorithms when efficiency in power draw is in mind. [ABSTRACT FROM AUTHOR]

A total vertex irregular k-labeling of a graph G = (V,E), @: V ∪ E → {1, 2, 3...,k} is a labeling of vertices and edges of G in such a way that the weights of all vertices are distinct. A total vertex irregularity strength of graph G, denoted by tvs(G) is defined as the minimum k for which a graph G has a totally irregular total k-labeling. In this paper, we investigate the no-hole total vertex irregularity strength for corona product of cyclic graphs and complete graphs. [ABSTRACT FROM AUTHOR]

The concepts of domination and topological index hold great significance within the realm of graph theory. Therefore, it is pertinent to merge these concepts to derive the domination index of a graph. A novel concept of the domination index is introduced, which utilizes the domination degree of a vertex. The domination degree of a vertex a is defined as the minimum cardinality of a minimal dominating set (MDS) that includes a. Methods to find a MDS containing a particular vertex is also discussed in the study. The notion of domination degree and domination index are studied for graphs like complete graphs, complete bipartite, r − partite graphs, cycles, wheels, paths, book graphs, windmill graphs, Kragujevac trees. The study is extended to operation in graphs. Inequalities involving domination degree and already established graph parameters are discussed. An application of domination degree is discussed in facility allocation in a city. [ABSTRACT FROM AUTHOR]

The cross-view matching of local image features is a fundamental task in visual localization and 3D reconstruction. This study proposes FilterGNN, a transformer-based graph neural network (GNN), aiming to improve the matching efficiency and accuracy of visual descriptors. Based on high matching sparseness and coarse-to-fine covisible area detection, FilterGNN utilizes cascaded optimal graph-matching filter modules to dynamically reject outlier matches. Moreover, we successfully adapted linear attention in FilterGNN with post-instance normalization support, which significantly reduces the complexity of complete graph learning from O(N2) to O(N). Experiments show that FilterGNN requires only 6% of the time cost and 33.3% of the memory cost compared with SuperGlue under a large-scale input size and achieves a competitive performance in various tasks, such as pose estimation, visual localization, and sparse 3D reconstruction. [ABSTRACT FROM AUTHOR]