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]

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]

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]

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]

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]

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]

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]

We prove that for any r∈N$r\in \mathbb {N}$, there exists a constant Cr$C_r$ such that the following is true. Let F={F1,F2,⋯}$\mathcal {F}=\lbrace F_1,F_2,\dots \rbrace$ be an infinite sequence of bipartite graphs such that |V(Fi)|=i$|V(F_i)|=i$ and Δ(Fi)⩽Δ$\Delta (F_i)\leqslant \Delta$ hold for all i$i$. Then, in any r$r$‐edge‐coloured complete graph Kn$K_n$, there is a collection of at most exp(CrΔ)$\exp (C_r\Delta)$ monochromatic subgraphs, each of which is isomorphic to an element of F$\mathcal {F}$, whose vertex sets partition V(Kn)$V(K_n)$. This proves a conjecture of Corsten and Mendonça in a strong form and generalises results on the multi‐colour Ramsey numbers of bounded‐degree bipartite graphs. It also settles the bipartite case of a general conjecture of Grinshpun and Sárközy. [ABSTRACT FROM AUTHOR]

Let C be a class of finite groups closed under taking subgroups, quotients, and extensions with abelian kernel. The right-angled Artin pro- C group G Γ (pro- C RAAG for short) is the pro- C completion of the right-angled Artin group G (Γ) associated with the finite simplicial graph Γ. In the first part, we describe structural properties of pro- C RAAGs. Among others, we describe the centraliser of an element and show that pro- C RAAGs satisfy the Tits' alternative, that standard subgroups are isolated, and that 2-generated pro- p subgroups of pro- C RAAGs are either free pro- p or free abelian pro- p. In the second part, we characterise splittings of pro- C RAAGs in terms of the defining graph. More precisely, we prove that a pro- C RAAG G Γ splits as a non-trivial direct product if and only if Γ is a join and it splits over an abelian pro- C group if and only if a connected component of Γ is a complete graph or it has a complete disconnecting subgraph. We then use this characterisation to describe an abelian JSJ decomposition of a pro- C RAAG, in the sense of Guirardel and Levitt [9]. [ABSTRACT FROM AUTHOR]

The Industrial Internet of Things (IIoT) provides a foundation for the development of emerging digital servitization paradigm in smart manufacturing. The deep integration of massive heterogeneous IIOT data plays a critical role in realising manufacturing digital servitization. However, there is a knowledge gap between different manufacturing fields, which brings a challenge for efficient integration and leverage of industrial big data. For this purpose, a Framework of Manufacturing Knowledge Graph (FMKG) is proposed, which is used to extracts industry knowledge triples from multi-source heterogeneous data to integrate domain knowledge. Also, an attention-based graph embedding model (ABGE) is proposed to discover and complement the implicit missing relationships in the knowledge graph to obtain a complete industrial knowledge graph. The effectiveness of the ABGE model has been verified on several knowledge graph data sets. And an aerospace enterprise production process was taken as an example to establish a product quality knowledge graph, which proved the feasibility of the proposed method. [ABSTRACT FROM AUTHOR]

In this paper, we present a variant of our previous research on multi-goal path finding problem, focusing on finding a feasible and closed path to visit a sequence of goals in an environment with obstacles. The newly proposed method, Segmentation & Regression v2 (S&Reg v2), employs multi-task learning networks to generate regions and estimates of lengths of local paths between pairwise goals. Importantly, the estimates are performed as weights for a complete graph to compute the visiting sequence. Subsequently, the path-finding process is executed following the sequence, and the predicted region works as a sampling domain to enhance the search speed. A hybrid sampler is designed by combining a uniform domain with the region domain, ensuring successful samples, even if the region is disconnected. Besides, a selection rule is introduced to balance the sampling domain during different searching stages. A proof of probabilistic completeness of the S&Reg v2 method is given. Simulations verify the superior performance of the S&Reg v2 method, demonstrating a reduction in calculation time ranging from 3.9% to 13.0%. Furthermore, a practical scenario validates the reliability of S&Reg v2, achieving a 15.0% improvement in success rate and a 9.7% reduction in calculation time. [ABSTRACT FROM AUTHOR]

Taking into account the most recent improvements in graph theory and algebra, we can associate graphs of some mathematical structures with certifiable, widely known applications. This paper seeks to explore the connections established through edge labeling among Latin squares derived from Moufang quasigroups, which are constructed using additive abelian and multiplicative groups, along with their substructures and complete bipartite graphs. The algebraic characteristics of quasigroups exhibiting the antiautomorphic inverse property have been extensively examined in this study. These characteristics encompass identities associated with fixed element maps. To analyze the behavior of these groups under holomorphism, we utilize similar conditions. [ABSTRACT FROM AUTHOR]