Search

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 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]

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]

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]

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]

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]

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]

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]

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]

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]

In this short note, we consider a graph process recently introduced by Frieze, Krivelevich and Michaeli. In their model, the edges of the complete graph K n ${K}_{n}$ are ordered uniformly at random and are then revealed consecutively to a player called Builder. At every round, Builder must decide if they accept the edge proposed at this round or not. We prove that, for every d ≥ 2 $d\ge 2$, Builder can construct a spanning d $d$‐connected graph after ( 1 + o ( 1 ) ) n log   n / 2 $(1+o(1))n\mathrm{log}\unicode{x0200A}n/2$ rounds by accepting ( 1 + o ( 1 ) ) d n / 2 $(1+o(1))dn/2$ edges with probability converging to 1 as n → ∞ $n\to \infty $. This settles a conjecture of Frieze, Krivelevich and Michaeli. [ABSTRACT FROM AUTHOR]

Let Kn denote a complete graph on n vertices and Sk denote a complete bipartite graph K1,k. A Bowtie Bl is a graph formed by the union of two cycles Cn and Cm intersecting at a common vertex. A decomposition of a graph G is a collection of edge-disjoint subgraphs H, such that every edge of G belongs to exactly one H. Given non-isomorphic subgraphs H1 and H2 of G, a (H1,H2) — multi-decomposition of G is the decomposition of G into a copies of H1 and b copies of H2, such that aH1 ⊕ bH2 = G, for some integers a,b ≥ 0. In this paper, the multi-decomposition of Kn into Sk and Bl has been investigated and obtained a necessary and sufficient condition when k = l = 6. It is proved that for a given positive integer n, Kn can be decomposed into a copies of S6 and b copies of B6 for some pair of non-negative integers (a,b) if and only if 6(a + b) = n 2, for all n ≥ 9. [ABSTRACT FROM AUTHOR]

Let R be a commutative ring with identity and I be an ideal of R. The zero-divisor graph of R with respect to I, denoted by ΓI(R), is the graph whose vertices are the set {x ∈ R∖I|xy ∈ I for some y ∈ R∖I} with distinct vertices x and y are adjacent if and only if xy ∈ I. The cozero-divisor graph Γ′(R) of R is the graph whose vertices are precisely the non-zero, non-unit elements of R and two distinct vertices x and y are adjacent if and only if x∉yR and y∉xR. In this paper, we introduced and investigated a new generalization of the cozero-divisor graph Γ′(R) of R denoted by ΓI″(R). In fact, ΓI″(R) is a dual notion of ΓI(R). [ABSTRACT FROM AUTHOR]

For a graph G, a subset D of V(G) is said to be a restrained dominating set(RDS) of G if D is a dominating set and every vertex not in D has a neighbor in V - D. A RDS is said to be an isolate restrained perfect dominating set(IRPDS) if < D > has at least one isolated vertex and D is a perfect dominating set. The minimum cardinality of a minimal IRPDS of G is called the isolate restrained perfect domination number(IRDN), denoted by 7,-.0 p (G). This paper contains basic properties of IRPDS and gives the IRDPN for the families of graphs such as paths, cycles, complete k-partite graphs and some other graphs. [ABSTRACT FROM AUTHOR]

We give an integer linear program formulation for the star bicolouring of bipartite graphs. We develop a column generation method to solve the linear programming relaxation to obtain a lower bound for the minimum number of colours needed. We determine the star bicolouring using the iterative rounding method. We give computational results on arrowhead matrices, sparse random matrices, complete bipartite graphs, and matrices from the Harwell–Boeing collection. The findings demonstrate that the proposed method effectively establishes lower and upper bounds for the minimum number of colours needed for a star bicolouring of bipartite graphs, particularly for sparse bipartite graphs. [ABSTRACT FROM AUTHOR]

Given a set P of m ⩾ 3 points in general position in the plane, we want to find the smallest possible number of convex polygons with vertices in P such that the edges of all these polygons contain all the m 2 straight line segments determined by the points of P. We show that if m is odd, the answer is (m 2 - 1) / 8 regardless of the choice of P. In this case there is even a partitioning of the edges of the complete geometric graph on m vertices into (m 2 - 1) / 8 convex polygons. The answer in the case where m is even depends on the choice of P and not only on m. Nearly tight lower and upper bounds follow in the case where m is even. [ABSTRACT FROM AUTHOR]

Genome-scale metabolic models (GEMs) are powerful tools for predicting cellular metabolic and physiological states. However, there are still missing reactions in GEMs due to incomplete knowledge. Recent gaps filling methods suggest directly predicting missing responses without relying on phenotypic data. However, they do not differentiate between substrates and products when constructing the prediction models, which affects the predictive performance of the models. In this paper, we propose a hyperedge prediction model that distinguishes substrates and products based on dual-scale fused hypergraph convolution, DSHCNet, for inferring the missing reactions to effectively fill gaps in the GEM. First, we model each hyperedge as a heterogeneous complete graph and then decompose it into three subgraphs at both homogeneous and heterogeneous scales. Then we design two graph convolution-based models to, respectively, extract features of the vertices in two scales, which are then fused via the attention mechanism. Finally, the features of all vertices are further pooled to generate the representative feature of the hyperedge. The strategy of graph decomposition in DSHCNet enables the vertices to engage in message passing independently at both scales, thereby enhancing the capability of information propagation and making the obtained product and substrate features more distinguishable. The experimental results show that the average recovery rate of missing reactions obtained by DSHCNet is at least 11.7% higher than that of the state-of-the-art methods, and that the gap-filled GEMs based on our DSHCNet model achieve the best prediction performance, demonstrating the superiority of our method. [ABSTRACT FROM AUTHOR]

In 2011, Beeler and Hoilman generalized the game of peg solitaire to arbitrary connected graphs. Since then peg solitaire and related games have been considered on many graph classes. One of the main goals is the characterization of solvable graphs. To this end, different graph operations, such as joins and Cartesian products, have been considered in the past. In this article, we continue this venue of research by investigating line graphs. Instead of playing peg solitaire on the line graph L(G) of a graph G, we introduce a related game called stick solitaire and play it on G. This game is examined on several well-known graph classes, for example complete graphs and windmills. In particular, we prove that most of them are stick-solvable. We also present a family of graphs which contains unsolvable graphs in stick solitaire. Naturally, the fool's stick solitaire number is an object of interest, which we compute for the previously considered graph classes. [ABSTRACT FROM AUTHOR]

In this paper, we use semidefinite programming and representation theory to compute new lower bounds on the crossing number of the complete bipartite graph K m , n , extending a method from de Klerk et al. (SIAM J Discrete Math 20:189–202, 2006) and the subsequent reduction by De Klerk, Pasechnik and Schrijver (Math Prog Ser A and B 109:613–624, 2007). We exploit the full symmetry of the problem using a novel decomposition technique. This results in a full block-diagonalization of the underlying matrix algebra, which we use to improve bounds on several concrete instances. Our results imply that cr (K 10 , n) ≥ 4.87057 n 2 - 10 n , cr (K 11 , n) ≥ 5.99939 n 2 - 12.5 n , cr (K 12 , n) ≥ 7.25579 n 2 - 15 n , cr (K 13 , n) ≥ 8.65675 n 2 - 18 n for all n. The latter three bounds are computed using a new and well-performing relaxation of the original semidefinite programming bound. This new relaxation is obtained by only requiring one small matrix block to be positive semidefinite. [ABSTRACT FROM AUTHOR]

Given a graph L $L$, the Turán number ex(n,L) $\text{ex}(n,L)$ is the maximum possible number of edges in an n $n$‐vertex L $L$‐free graph. The study of Turán number of graphs is a central topic in extremal graph theory. Although the celebrated Erdős‐Stone‐Simonovits theorem gives the asymptotic value of ex(n,L) $\text{ex}(n,L)$ for nonbipartite L $L$, it is challenging in general to determine the exact value of ex(n,L) $\text{ex}(n,L)$ for χ(L)≥3 $\chi (L)\ge 3$. The odd‐ballooning of H $H$ is a graph such that each edge of H $H$ is replaced by an odd cycle and all new vertices of odd cycles are distinct. Here the length of odd cycles is not necessarily equal. The exact value of Turán number of the odd‐ballooning of H $H$ is previously known for H $H$ being a cycle, a path, a tree with assumptions, and K2,3 ${K}_{2,3}$. In this paper, we manage to obtain the exact value of Turán number of the odd‐ballooning of Ks,t ${K}_{s,t}$ with 2≤s≤t $2\le s\le t$, where (s,t)∉{(2,2),(2,3)} $(s,t)\notin \{(2,2),(2,3)\}$ and each odd cycle has length at least five. [ABSTRACT FROM AUTHOR]

A λ $\lambda $‐backbone coloring of a graph G $G$ with its subgraph (also called a backbone) H $H$ is a function c:V(G)→{1,...,k} $c:V(G)\to \{1,\ldots ,k\}$ ensuring that c $c$ is a proper coloring of G $G$ and for each {u,v}∈E(H) $\{u,v\}\in E(H)$ it holds that |c(u)−c(v)|≥λ $|c(u)-c(v)|\ge \lambda $. In this paper we propose a way to color cliques with tree and forest backbones in linear time that the largest color does not exceed max{n,2λ}+Δ(H)2⌈logn⌉ $\max \{n,2\lambda \}+{\rm{\Delta }}{(H)}^{2}\lceil \mathrm{log}n\rceil $. This result improves on the previously existing approximation algorithms as it is (Δ(H)2⌈logn⌉) $({\rm{\Delta }}{(H)}^{2}\lceil \mathrm{log}n\rceil)$‐absolutely approximate, that is, with an additive error over the optimum. We also present an infinite family of trees T $T$ with Δ(T)=3 ${\rm{\Delta }}(T)=3$ for which the coloring of cliques with backbones T $T$ requires at least max{n,2λ}+Ω(logn) $\max \{n,2\lambda \}+{\rm{\Omega }}(\mathrm{log}n)$ colors for λ $\lambda $ close to n2 $\frac{n}{2}$. The construction draws on the theory of Fibonacci numbers, particularly on Zeckendorf representations. [ABSTRACT FROM AUTHOR]

We deduce a new property exhibited by the resistance matrices of connected graphs. Specifically, we show that if R=(rij) is the resistance matrix of a connected graph on n vertices, then every off-diagonal entry in the Moore-Penrose inverse of ... is negative. Thus, we establish that the Moore-Penrose inverse of the resistance Laplacian matrices are M-matrices. [ABSTRACT FROM AUTHOR]

In [Trans. Am. Math. Soc. 375 (2022), no. 1, 627–668], Kahn gave the strongest possible, affirmative, answer to Shamir's problem, which had been open since the late 1970s: Let r⩾3$$ r\geqslant 3 $$ and let n$$ n $$ be divisible by r$$ r $$. Then, in the random r$$ r $$‐uniform hypergraph process on n$$ n $$ vertices, as soon as the last isolated vertex disappears, a perfect matching emerges. In the present work, we prove the analogue of this result for clique factors in the random graph process: at the time that the last vertex joins a copy of the complete graph Kr$$ {K}_r $$, the random graph process contains a Kr$$ {K}_r $$‐factor. Our proof draws on a novel sequence of couplings which embeds the random hypergraph process into the cliques of the random graph process. An analogous result is proved for clique factors in the s$$ s $$‐uniform hypergraph process (s⩾3$$ s\geqslant 3 $$). [ABSTRACT FROM AUTHOR]

We study relaxations for linear programs with complementarity constraints, especially instances whose complementary pairs of variables are not independent. Our formulation is based on identifying vertex covers of the conflict graph of the instance and contains the extended formulation obtained from the ERLT introduced by Nguyen, Richard, and Tawarmalani as a special case. We demonstrate how to obtain strong cutting planes for our formulation from both the stable set polytope and the boolean quadric polytope associated with a complete bipartite graph. Through an extensive computational study for three types of practical problems, we assess the performance of our proposed linear relaxation and new cutting-planes in terms of the optimality gap closed. [ABSTRACT FROM AUTHOR]

Let G be a connected graph with adjacency matrix A(G) and distance matrix D(G). Let dist (u , v) denote the distance between the pair of vertices u , v ∈ V (G) , then the transmission trs (u) of vertex u is defined as ∑ v ∈ V (G) dist (u , v) . Let trs (G) be the diagonal matrix whose diagonal elements are the transmissions of the vertices of G. And, let deg (G) be the diagonal matrix whose diagonal elements are the degrees of the vertices of G. In this paper we investigate the Smith normal form (SNF) and the spectrum of the matrices D + deg (G) : = deg (G) + D (G) , D deg (G) : = deg (G) - D (G) , A + trs (G) : = trs (G) + A (G) and A trs (G) : = trs (G) - A (G) . In particular, we explore how good the SNF and the spectrum of these matrices are for determining graphs up to isomorphism. We found that the SNF of A trs has an interesting behaviour when compared with other classical matrices. We note that the SNF of A trs can be used to compute the structure of the sandpile group of certain graphs. We compute the SNF of D + deg , D deg , A + trs and A trs for several graph families. We prove that the SNF of D + deg , D deg , A + trs and A trs determine complete graphs. Finally, we derive some results about the spectrum of D deg and A trs . [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]

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]

In this paper, we introduce the unit-Jacobson graph, which is defined by the unit elements and the elements of the Jacobson radical of a commutative ring R with nonzero identity. We give relationships between this new graph concept and some special rings such as j-clean rings, UJ-rings, local rings, and cartesian rings. Moreover, we investigate the concepts of the dominating set, diameter, and girth on the unit-Jacobson graph. [ABSTRACT FROM AUTHOR]

The population structure often impacts evolutionary dynamics. In constant-selection evolutionary dynamics between two types, amplifiers of selection are networks that promote the fitter mutant to take over the entire population, and suppressors of selection do the opposite. It has been shown that most undirected and unweighted networks are amplifiers of selection under a common updating rule and initial condition. Here, we extensively investigate how edge weights influence selection on undirected networks. We show that random edge weights make small networks less amplifying than the corresponding unweighted networks in a majority of cases and also make them suppressors of selection (i.e. less amplifying than the complete graph, or equivalently, the Moran process) in many cases. Qualitatively, the same result holds true for larger empirical networks. These results suggest that amplifiers of selection are not as common for weighted networks as for unweighted counterparts. [ABSTRACT FROM AUTHOR]

Haemers' conjecture on the Seidel energy of graphs, states that the energy of the Seidel matrix of any graph of order n is at least 2 n − 2 , where the equality holds for the complete graph. In this paper, we give a short simple proof of this conjecture. [ABSTRACT FROM AUTHOR]

The conditional fractional matching preclusion number (CFMP number for short) fmp1(G) of a graph G is the minimum number of edges whose deletion results in a graph without isolated vertices and without fractional perfect matchings. In this paper, we study the CFMP number of complete graphs, complete bipartite graphs and twisted cubes. Also, we give Nordhaus–Gaddum-type results for the CFMP numbers of general graphs. [ABSTRACT FROM AUTHOR]

A signed graph Σ = (G , σ) consists of an underlying graph G = (V , E) with a sign function σ : E → { − 1 , 1 } . Let A (Σ) be the adjacency matrix of Σ and λ 1 (Σ) denote the largest eigenvalue (index) of Σ. Define (K n , H −) as a signed complete graph whose negative edges induce a subgraph H. In this paper, we focus on the following question: which spanning tree T with a given number of pendant vertices makes the λ 1 (A (Σ)) of the unbalanced (K n , T −) as large as possible? To answer the question, we characterize the extremal signed graph with maximum λ 1 (A (Σ)) among graphs of type (K n , T −) . [ABSTRACT FROM AUTHOR]

Cliques are maximal complete subgraphs of a graph. A vertex v is said to vc-cover a clique C if v is in the clique C. A set S of vertices of a graph G is called a vccovering set of G if every clique of G is vc-covered by some vertex in S. The cardinality of the smallest vc-covering set of G is called the vc-covering number, denoted as αvc(G). In this paper, we define new parameters such as strong (weak) vccovering number and strong (weak) clique-free number, and we establish a relationship between them. We present an algorithm to find these numbers and obtain some bounds for the newly defined parameters. In addition, we define a partial order on the vertex set of a graph using clique degree conditions and study some of its properties. [ABSTRACT FROM AUTHOR]

We consider the Grover walk on the infinite graph in which an internal finite subgraph receives the inflow from the outside with some frequency and also radiates the outflow to the outside. To characterize the stationary state of this system, which is represented by a function on the arcs of the graph, we introduce a kind of discrete gradient operator twisted by the frequency. Then, we obtain a circuit equation which shows that (i) the stationary state is described by the twisted gradient of a potential function which is a function on the vertices; (ii) the potential function satisfies the Poisson equation with respect to a generalized Laplacian matrix. Consequently, we characterize the scattering on the surface of the internal graph and the energy penetrating inside it. Moreover, for the complete graph as the internal graph, we illustrate the relationship of the scattering and the internal energy to the frequency and the number of tails. [ABSTRACT FROM AUTHOR]

It is well known that the famous Ramsey number R (K 3 , K 3) = 6 . That is, the minimum positive integer n for which every red-blue coloring of the edges of the complete graph K n results in a monochromatic triangle K 3 is 6. It is also known that every red-blue coloring of K 6 results in at least two monochromatic triangles, which need not be vertex-disjoint or edge-disjoint. This fact led to an extension of Ramsey numbers. For a graph F and a positive integer t, the vertex-disjoint Ramsey number V R t (F) is the minimum positive integer n such that every red-blue coloring of the edges of the complete graph K n of order n results in t pairwise vertex-disjoint monochromatic copies of subgraphs isomorphic to F, while the edge-disjoint Ramsey number E R t (F) is the corresponding number for edge-disjoint subgraphs. Since V R 1 (F) and E R 1 (F) are the well-known Ramsey numbers of F, these new Ramsey concepts generalize the Ramsey numbers and provide a new perspective for this classical topic in graph theory. These numbers have been investigated for the two connected graphs K 3 and the path P 3 of order 3. Here, we study these numbers for the remaining connected graphs, namely, the path P 4 and the star K 1 , 3 of size 3. We show that V R t (P 4) = 4 t + 1 for every positive integer t and V R t (K 1 , 3) = 4 t for every integer t ≥ 2 . For t ≤ 4 , the numbers E R t (K 1 , 3) and E R t (P 4) are determined. These numbers provide information towards the goal of determining how the numbers V R t (F) and E R t (F) increase as t increases for each graph F ∈ { K 1 , 3 , P 4 } . [ABSTRACT FROM AUTHOR]

A mathematical procedure enabling the transformation of an arbitrary tessellation of a surface into a bi-colored, complete graph is introduced. Polygons constituting the tessellation are represented by vertices of the graphs. Vertices of the graphs are connected by two kinds of links/edges, namely, by a green link, when polygons have the same number of sides, and by a red link, when the polygons have a different number of sides. This procedure gives rise to a semi-transitive, complete, bi-colored Ramsey graph. The Ramsey semi-transitive number was established as R t r a n s (3 , 3) = 5 Shannon entropies of the tessellation and graphs are introduced. Ramsey graphs emerging from random Voronoi and Poisson Line tessellations were investigated. The limits ζ = lim N → ∞ N g N r , where N is the total number of green and red seeds, N g and N r , were found ζ = 0.272 ± 0.001 (Voronoi) and ζ = 0.47 ± 0.02 (Poisson Line). The Shannon Entropy for the random Voronoi tessellation was calculated as S = 1.690 ± 0.001 and for the Poisson line tessellation as S = 1.265 ± 0.015. The main contribution of the paper is the calculation of the Shannon entropy of the random point process and the establishment of the new bi-colored Ramsey graph on top of the tessellations. [ABSTRACT FROM AUTHOR]