Search

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]

A proper conflict-free c -coloring of a graph is a proper c -coloring such that each non-isolated vertex has a color appearing exactly once on its neighborhood. This notion was formally introduced by Fabrici et al., who proved that planar graphs have a proper conflict-free 8-coloring and constructed a planar graph with no proper conflict-free 5-coloring. Caro, Petruševski, and Škrekovski investigated this coloring concept further, and in particular studied upper bounds on the maximum average degree that guarantees a proper conflict-free c -coloring for c ∈ { 4 , 5 , 6 }. Along these lines, we completely determine the threshold on the maximum average degree of a graph G , denoted mad (G) , that guarantees a proper conflict-free c -coloring for all c and also provide tightness examples. Namely, for c ≥ 5 we prove that a graph G with mad (G) ≤ 4 c c + 2 has a proper conflict-free c -coloring, unless G contains a 1-subdivision of the complete graph on c + 1 vertices. When c = 4 , we show that a graph G with mad (G) < 12 5 has a proper conflict-free 4-coloring, unless G contains an induced 5-cycle. In addition, we show that a planar graph with girth at least 5 has a proper conflict-free 7-coloring. [ABSTRACT FROM AUTHOR]

Consider a (p,q) graph G = (V,E). Define ϱ = p 2 pis even,p − 1 2 pis odd, and Υ = {±1,±2,…,±ϱ} referred to as the label set. Let us consider a mapping φ : V → Υ, where, for every even p, distinct labels are assigned to the various elements of V in Υ, and for every odd p, distinct labels are assigned to the p − 1 elements of V in Υ, with a repeating label for the lone vertex. After that, φ is referred to as a pair mean cordial labeling (PMC-labeling) if for every edge μν within G, there is a label for φ(μ)+φ(ν) 2 if φ(μ) + φ(ν) is even and φ(μ)+φ(ν)+1 2 if φ(μ) + φ(ν) is odd such that |핊̄φ1 −핊̄φ1c|≤ 1 in which 핊̄φ1 and 핊̄φ1c denote the number of edges labeled with 1 and the number of edges not labeled with 1 in that order. A pair mean cordial graph (PMC-graph) is defined as a graph G with PMC-labeling. In this paper, we discuss the PMC-labeling characteristics of a few unique graphs like windmill graph, planar grid, quasi-flower snark graph, complete flower graph, triple wheel graph, alternate triangular belt and lotus inside of a circle. [ABSTRACT FROM AUTHOR]

We consider a statistical problem to estimate variables (effects) that are associated with the edges of a complete bipartite graph K v 1 , v 2 = (V 1 , V 2 ; E) . Each data is obtained as a sum of selected effects, a subset of E. To estimate efficiently, we propose a design called Spanning Bipartite Block Design (SBBD). For SBBDs such that the effects are estimable, we proved that the estimators have the same variance (variance balanced). If each block (a subgraph of K v 1 , v 2 ) of SBBD is a semi-regular or a regular bipartite graph, we show that the design is A-optimum. We also show a construction of SBBD using an ( r , λ )-design and an ordered design. A BIBD with prime power blocks gives an A-optimum semi-regular or regular SBBD. [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 Kn ${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))nlog n/2 $(1+o(1))n\mathrm{log}\unicode{x0200A}n/2$ rounds by accepting (1+o(1))dn/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 H be a graph possibly with loops and G be a multigraph without loops. An H-coloring of G is a function c : E (G) → V (H) . We will say that G is an H-colored multigraph, whenever we are taking a fixed H-coloring of G. The set of all the edges with end vertices u and v will be denoted by E uv . We will say that W = (v 0 , e 0 1 , ... , e 0 k 0 , v 1 , e 1 1 , ... , e 1 k 1 , v 2 , ... , v n - 1 , e n - 1 1 , ... , e n - 1 k n - 1 , v n) , where for each i in { 0 , ... , n - 1 } , k i ≥ 1 and e i j ∈ E v i v i + 1 for every j ∈ { 1 , ... , k i } , is a dynamic H-walk iff c (e i k i) c (e i + 1 1) is an edge in H, for each i ∈ { 0 , ... , n - 2 } . We will say that a dynamic H-walk is a closed dynamic H-walk whenever v 0 = v n and c (e n - 1 k n - 1 ) c (e 0 1) is an edge in H. Moreover, a closed dynamic H-walk is called dynamic H-cycle whenever v i ≠ v j , for every { i , j } ⊆ { 0 , ... , v n - 1 } . In particular, a dynamic H-walk is an H-walk whenever k i = 1 , for every i ∈ { 0 , ... , n - 1 } , and when H is a complete graph without loops, an H-walk is well known as a properly colored walk. In this work, we study the existence and length of dynamic H-cycles, dynamic H-trails and dynamic H-paths in H-colored multigraphs. To accomplish this, we introduce a new concept of color degree, namely, the dynamic degree, which allows us to extend some classic results, as Ore's Theorem, for H-colored multigraphs. Also, we give sufficient conditions for the existence of hamiltonian dynamic H-cycles in H-colored multigraphs, and as a consequence, we obtain sufficient conditions for the existence of properly colored hamiltonian cycle in edge-colored multigraphs, with at least c ≥ 3 colors. [ABSTRACT FROM AUTHOR]

The graph K1 is a trivial graph consisting of a single vertex with no edges. In contrast, the graph K1,λ is a complete bipartite graph with one internal node and λ leaf vertices. The join of two graphs K1 and K1,λ (with central vertex ρ0), represented as K1 + K1,λ, is a graph including vertices V (K1 + K1,λ) = V (K1) ∪ V (K1,λ) and edges V (K1 + K1,λ) = V (K1) ∪ V (K1,λ) ∪{σ1ρ0 : σ1 ∈ V (K1),ρ0 ∈ V (K1,λ)}. When two graphs, K1 and K1,λ are joined, the result is a graph in which vertex in graph K1 is linked to every vertex in graph K1,λ. Modular multiplicative divisor (MMD) labeling is a vertex and edge labeling scheme with the following key features: Vertex labeling: MMD labeling establishes a bijection between the vertices of the graph T and the natural numbers from 1 to |v|. This bijection ensures a one-to-one correspondence, providing a unique label for each vertex. Edge labeling: The labeling of edges follows a specific rule, the edge’s label is determined by calculating the result of multiplying the labels assigned to its connected vertices, with the outcome adjusted by modulo n. We demonstrate the modular multiplication labeling when combining two graphs through their join (assuming λ is even) and also on the even arbitrary super subdivision (EASS) of the join of two graphs. Additionally, we explore a related research question that arises in this particular context. The findings have potential applications in network topology design and optimization. [ABSTRACT FROM AUTHOR]

An edge-colored graph G is called rainbow if no two edges of G have the same color. For a graph G and a subgraph H ⊆ G , the anti-Ramsey number A R (G , H) is the maximum number of colors in an edge-coloring of G such that G contains no rainbow copy of H. Recently, the anti-Ramsey problem for disjoint union of graphs received much attention. In particular, several researchers focused on the problem for graphs consisting of small components. In this paper, we continue the work in this direction. We refine the bound and obtain the precise value of A R (K n , P 3 ∪ t P 2) for all n ≥ 2 t + 3. Additionally, we determine the value of A R (K n , 2 P 3 ∪ t P 2) for any integers t ≥ 1 and n ≥ 2 t + 7. [ABSTRACT FROM AUTHOR]

Let i be a positive integer, an i -star denoted by S i is a complete bipartite graph K 1 , i. An { S 2 , S 3 } -packing of a graph G is a collection of vertex-disjoint subgraphs of G in which each subgraph is a 2-star or a 3-star. The maximum { S 2 , S 3 } -packing problem is to find an { S 2 , S 3 } -packing of a given graph containing the maximum number of vertices. The { S 2 , S 3 } -factor problem is to answer whether there is an { S 2 , S 3 } -packing containing all vertices of the given graph. The { S 2 , S 3 } -factor problem is NP-complete in cubic graphs. In this paper we design a quadratic-time algorithm for finding an { S 2 , S 3 } -packing of G that covers at least thirteen-sixteenths of its vertices with only a few exceptions. We also present some (2 , 3) -regular graphs with their maximum { S 2 , S 3 } -packings covering exactly thirteen-sixteenths of their vertices. [ABSTRACT FROM AUTHOR]

In a digraph, a quasi-kernel is a subset of vertices that is independent and such that the shortest path from every vertex to this subset is of length at most two. The "small quasi-kernel conjecture", proposed by Erdős and Székely in 1976, postulates that every sink-free digraph has a quasi-kernel whose size is within a fraction of the total number of vertices. The conjecture is even more precise with a 1 / 2 ratio, but even with larger ratio, this property is known to hold only for few classes of graphs. The focus here is on small quasi-kernels in split graphs. This family of graphs has played a special role in the study of the conjecture since it was used to disprove a strengthening that postulated the existence of two disjoint quasi-kernels. The paper proves that every sink-free split digraph D has a quasi-kernel of size at most 2 3 | V (D) | , and even of size at most two when the graph is an orientation of a complete split graph. It is also shown that computing a quasi-kernel of minimal size in a split digraph is W[2]-hard. [ABSTRACT FROM AUTHOR]

Effectiveness represents a fundamental performance metric in network communication systems and is intricately tied to the routing made within the network. Since the vertex forwarding index is primarily employed to measure the load-bearing capacity of network nodes, it has become a crucial parameter for evaluating the quality of network routing. By investigating the topological parameters and properties of the Strong product network K k ⊗ C c and its factor networks (The undirected cycle networks C c with c ≥ 3 vertices and the complete networks K k with k ≥ 2 vertices), we have determined the exact vertex forwarding index of Strong product graph K k ⊗ C c , which depends solely on the number of vertices in the factor networks. [ABSTRACT FROM AUTHOR]

AbstractIn this paper, we compare the regularities of symbolic and ordinary powers of edge ideals of weighted oriented graphs. For any weighted oriented complete graph Kn, we show that reg(I(Kn)(k))≤reg(I(Kn)k) for all k≥1. Also, we give explicit formulas for reg(I(Kn)(k)) and reg(I(Kn)k), for any k≥1. As a consequence, we show that reg(I(Kn)(k)) is eventually a linear function of k. For any weighted oriented graph D, if V+ are sink vertices, then we show that reg(I(D)(k))≤reg(I(D)k) with k = 2, 3 and equality cases studied. Furthermore, we give formula for reg(I(D)2) in terms of reg(I(D)(2)) and regularity of certain induced subgraphs of D. Finally, we compare the regularity of symbolic powers of weighted oriented graphs D and D′, where D′ is obtained from D by adding a pendant. [ABSTRACT FROM AUTHOR]

Background: Repetitive intramuscular injections of botulinum neurotoxin (BoNT) have become the treatment of choice for a variety of disease entities. But with the onset of BoNT therapy, the natural course of a disease is obscured. Nevertheless, the present study tries to analyze patients' "suspected" course of disease severity under the assumption that no BoNT therapy had been performed and compares that with the "experienced" improvement during BoNT treatment. Methods: For this cross-sectional study, all 112 BoNT long-term treated patients in a botulinum toxin out-patient department were recruited who did not interrupt their BoNT/A therapy for more than two injection cycles during the last ten years. Patients had to assess the remaining severity of their disease as a percentage of the severity at onset of BoNT therapy and to draw three different graphs: (i) the CoDB-graph showing the course of severity of patient's disease from onset of symptoms to onset of BoNT/A therapy, (ii) the CoDA-graph illustrating the course of severity from onset of BoNT/A therapy until recruitment, and (iii) the CoDS-graph visualizing the suspected development of disease severity from onset of BoNT/A therapy until recruitment under the assumption that no BoNT/A therapy had been performed. Three different types of graphs were distinguished: the R-type indicated a rapid manifestation or improvement, the C-type a continuous worsening or improvement, and the D-type a delayed manifestation or response to BoNT therapy. Four patient subgroups (cervical dystonia, other cranial dystonia, hemifacial spasm, and the migraine subgroup) comprised 91 patients who produced a complete set of graphs which were further analyzed. The "experienced" improvement and "suspected" worsening of disease severity since the onset of BoNT/A therapy were compared and correlated with demographical and treatment related data. Results: Improvement was significant (p < 0.05) and varied between 45 and 70% in all four patient subgroups, the "suspected" worsening was also significantly (p < 0.05) larger than 0, except in the migraine patients and varied between 10 and 70%. The "total benefit" (sum of improvement and prevented "suspected" worsening) was the highest in the other cranial dystonia group and the lowest in the migraine subgroup. The distributions of R-,C-,D-type graphs across CoDB-, CoDS-, and CoDB-graphs and across the four patient subgroups were significantly different. Conclusions: (i) Most BoNT long-term treated patients have the opinion that their disease would have further progressed and worsened if no BoNT/A therapy had been performed, (ii) The type of response to BoNT/A is different across different subgroups of BoNT/A long-term treated patients. [ABSTRACT FROM AUTHOR]

The category of directed graphs is isomorphic to a particular category whose objects are labeled undirected bipartite graphs and whose morphisms are undirected graph morphisms that respect the labeling. Based on this isomorphism, we begin by showing that the class of all directed graphs is a Graph Isomorphism Complete class. Afterwards, by extending this categorical framework to weighted prime graphs, we prove that the categories of multidirected graphs with and without self-loops are each isomorphic to a particular category of weighted prime graphs. Consequently, we prove that these classes of multidirected graphs are also Graph Isomorphism Complete. [ABSTRACT FROM AUTHOR]

The actors are placed at nodes of the complete weighted graph. They are endowed with densities of contact with the other actors and with positions in a social hierarchy. These characteristics evolve in time according to the homophily principle and the Matthew effect. The result is that an actor with minimal status is excluded, and all other actors get the same high position. As for examples, the results allow us to make reference to racial criteria of promotion in the London Metropolitan Police, and to the scapegoating phenomenon, described in the literature. [ABSTRACT FROM AUTHOR]

We study an exactly solvable random walk model with long-range memory on arbitrary networks. The walker performs unbiased random steps to nearest-neighbor nodes and intermittently resets to previously visited nodes in a preferential way such that the most visited nodes have proportionally a higher probability to be chosen for revisit. The occupation probability can be expressed as a sum over the eigenmodes of the standard random walk matrix of the network, where the amplitudes slowly decay as power-laws at large times, instead of exponentially. The stationary state is the same as in the absence of memory, and detailed balance is fulfilled. However, the relaxation of the transient part becomes critically self-organized at late times, as it is dominated by a single power-law whose exponent depends on the second largest eigenvalue and on the resetting probability. We apply our findings to finite networks, such as rings, complete graphs, Watts–Strogatz, and Barabási–Albert networks, and to Barbell and comb-like graphs. Our study could be of interest for modeling complex transport phenomena, such as human mobility, epidemic spreading, or animal foraging. [ABSTRACT FROM AUTHOR]

Let G be a finite simple graph and let A (G) be its adjacency matrix. Then, G is singular if A (G) is singular. The singularity of graphs is of certain interest in graph theory and algebraic combinatorics. For positive integers a i ≥ 2 , i = 1 , 2 , ... , 6 . Insert a 1 − 2 , a 2 − 2 , a 3 − 2 , a 4 − 2 , a 5 − 2 and a 6 − 2 vertices in the six edges of the complete graph K 4 , respectively, then the resulting graph is called the K 4 homeomorphic graph, denoted by K (a 1 , a 2 , a 3 , a 4 , a 5 , a 6) . In this paper, we give the necessary and sufficient condition for the singularity of K (a 1 , a 2 , a 3 , a 4 , a 5 , a 6) , and we also show that the probability of a K 4 homeomorphic graph K (a 1 , a 2 , a 3 , a 4 , a 5 , a 6) being a singular graph is equal to 193 512 . [ABSTRACT FROM AUTHOR]

If G is a graph and X ⊆ V (G), then X is a total mutual-visibility set if every pair of vertices x and y of G admits the shortest x, y-path P with V (P) ∩ X ⊆ {x, y}. The cardinality of the largest total mutual-visibility set of G is the total mutual-visibility number µt(G) of G. In this paper the total mutual-visibility number is studied on Hamming graphs, that is, Cartesian products of complete graphs. Different equivalent formulations for the problem are derived. The values µt(...) are determined. It is proved that µt(...) = O(Nr--2), where N = n1 + ⋯ + nr, and that µt(Ks□, r) = Θ(sr--2) for every r ≥ 3, where Ks□,r denotes the Cartesian product of r copies of Ks. The main theorems are also reformulated as Turán-type results on hypergraphs. [ABSTRACT FROM AUTHOR]

In this paper, we first give some sufficient criteria for normality of monomial ideals. As applications, we show that closed neighborhood ideals of complete bipartite graphs are normal, and hence satisfy the (strong) persistence property. We also prove that dominating ideals of complete bipartite graphs are nearly normally torsion-free. In addition, we show that dominating ideals of h -wheel graphs, under certain condition, are normal. [ABSTRACT FROM AUTHOR]

We show that every complete n-vertex simple topological graph contains a topological subgraph on at least (log n) 1 / 4 - o (1) vertices that is weakly isomorphic to the complete convex geometric graph or the complete twisted graph. This is the first improvement on the bound Ω (log 1 / 8 n) obtained in 2003 by Pach, Solymosi, and Tóth. We also show that every complete n-vertex simple topological graph contains a plane path of length at least (log n) 1 - o (1) . [ABSTRACT FROM AUTHOR]

Let G be a simple undirected graph, and let S (G) be its Seidel matrix. The Seidel energy of G is defined as E S (G) = ∑ i = 1 n | λ Si (G) |, where λ S1 (G), λ S2 (G), …, λ Sn (G) are Seidel eigenvalues of G . Recently, researchers have studied the effect of embedded edges on the distance energy of complete bipartite graphs. In this paper, the effect of perturbed edges on the Seidel energy of complete bipartite graphs and complete split graphs is studied. Finally, these graphs are ordered according to their Seidal energies. [ABSTRACT FROM AUTHOR]

To address the issue of existing knowledge graph completion methods limited capability in capturing structural information within knowledge graphs, this paper proposed a novel model that leveraged bipartite graphs and an attention mechanism to acquire global structural insights and facilitate automatic knowledge graph completion. This model firstly constructed two subgraphs centered on entities and relationships to capture potential useful information about entity neighborhood and relationship structures, and inputted the information formed by the two subgraphs into the encoder to better update entity and relationship structure information. Then, it used attention mechanisms to adaptively learn important interaction features between updated entities and relationships. Finally, it inputted the feature vectors containing global structural information into the decoder, and it actively employed a scoring function to assess and predict scores for the input feature edges, ultimately utilizing the predicted outcomes to accomplish the task of knowledge graph completion. Comparing the performance of the proposed method with the baseline method on the FB15K-237 and NELL995 datasets, the MRR and hits @ 10 evaluation indicators achieved significant improvements of 5.1, 8.8, and 3.4, 2. 2 percentage points, respectively. At the same time, on the WN18RR dataset, these two indicators also were improved by 0.1 and 1.9 percentage points, respectively. The experimental results show that established model proactively adopts a structure that effectively captures the global structural information of the knowledge graph, thereby significantly enhancing the expression ability and predictive performance of the model. [ABSTRACT FROM AUTHOR]

To improve the performance of BP decoding for polar codes, researchers have developed a Belief Propagation List (BPL) decoding algorithm by executing multiple BP decoders in parallel. This algorithm outperforms traditional BP decoding based on single graph decoding, although it sacrifices some complexity and delay. Unlike this basic Polar-BPL decoding mentioned above, a low-density parity check like (LDPC-like) BPL decoding algorithm has been introduced into polar codes. This algorithm performs more efficient BP decoding iterations on sparse graphs. To further reduce the complexity and delay of LDPC-like BPL, and avoid analyzing all sparse graphs, this article proposes an improved LDPC-like BPL (ILDPC-like BPL) decoding algorithm based on selecting factor graphs. This algorithm analyzes differences in permuted factor graphs and selects these graphs with non-convergent decoding results to form a decoding list, allowing decoding to be completed with fewer graphs traversed and iterations, thereby reducing complexity and delay. On this basis, to improve the reliability of this algorithm, this article further adds a path metric (PM) mechanism, which can dynamically evaluate different sparse graphs' results in parallel decoding. The simulation results show that compared with LDPC-like BPL (random scheme), ILDPC-like BPL improves decoding performance while reducing decoding delay and complexity; Compared with basic Polar-BPL (cycle-shift scheme), this algorithm greatly reduces decoding delay and complexity while achieving similar performance. [ABSTRACT FROM AUTHOR]

For given positive integers $r\ge 3$ , $n$ and $e\le \binom{n}{2}$ , the famous Erdős–Rademacher problem asks for the minimum number of $r$ -cliques in a graph with $n$ vertices and $e$ edges. A conjecture of Lovász and Simonovits from the 1970s states that, for every $r\ge 3$ , if $n$ is sufficiently large then, for every $e\le \binom{n}{2}$ , at least one extremal graph can be obtained from a complete partite graph by adding a triangle-free graph into one part. In this note, we explicitly write the minimum number of $r$ -cliques predicted by the above conjecture. Also, we describe what we believe to be the set of extremal graphs for any $r\ge 4$ and all large $n$ , amending the previous conjecture of Pikhurko and Razborov. [ABSTRACT FROM AUTHOR]

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]

A graph G is Q-integral if its signless Laplacian has only integral eigenvalues. Suppose GH be the graph after adding a self-loop to every vertex of a subset H of V (G). In this paper, we prove that for a nonempty proper subset H of V (Kp,p), Kp,pH is Q-integral if and only if p = 4 and self-loops are added in exactly two vertices of each partite set, or p = 2 and self-loops are added to all the vertices of one partite set. Besides, we prove that if H is a nonempty proper subset of V (K1,p), then K1,pH is Q-integral if and only if p = 4 and self-loops are added to all the pendant vertices. Using these results, we also answer when the matrix M + 3D′ have only integral spectrum, where D′ is any (0, 1)-diagonal matrix and M is permutation similar to either Op J J Op or pJ JIp. [ABSTRACT FROM AUTHOR]

Social network extensions of Heider's balance theory have led to a plethora of adaptations, often inconsistent with Heider and each other. We present a general model that permits the description and testing of specific balance theoretic predictions as Heider had originally proposed them. We formulate balance statements as a comparison of two conditional probabilities of a tie: Ego-qAlter , conditioned on 2-path relations Ego-rX-sAlter vs. their counterfactual negation, ¬(Ego-rX-sAlter). Here q, r and s, are indices that identify elements in a set of mutually exclusive and exhaustive relations in a multigraph (their sum produces a complete graph). This relaxes the dichotomous assumption of a signed graph. We identify neutral ties distinctive from negative and positive ties and convert the underlying signed graph into a restricted multigraph. The point-biserial correlations of relation q with the count of 2-paths (through relations r and s) describe the difference in conditional probabilities, or the prevalence for any stipulated balance configuration. In total 18 such unique balance correlations are identified for any trichotomous multigraph, although 27 theoretical statements exist. Two major advantages of balance correlations are: direct comparison between any two correlations over time, even if network sizes and densities differ; and the evaluation of specific balanced and unbalanced behaviors and predictions. We apply the model to a large data set consisting of friendly vs hostile relations between countries from 1816 to 2007. We find strong evidence for one of the balance statements, and virtually no evidence for unbalanced predictions. However, there is ample stable evidence that "neutral" ties are important in balancing the relations among nations. Results suggest that prevalence of balance-driven behavior varies over time. Indeed, other behaviors may prevail in certain eras. [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 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]

The threshold protocol game is a graphical game that models the adoption of an idea or product through a population. There are two states players may take in the game, and the goal of the game is to motivate the state that begins in the minority to spread to every player. Here, the threshold protocol game is defined, and existence results are studied on infinite graphs. Many generalizations are proposed and applied. This work explores the impact of graph topology on the outcome of the threshold protocol game and consequently considers finite graphs. By exploiting the well-known topologies of complete and complete bipartite graphs, the outcome of the threshold protocol game can be fully characterized on these graphs. These characterizations are ideal, as they are given in terms of the game parameters. More generally, initial conditions in terms of game parameters that cause the preferred game outcome to occur are identified. It is shown that the necessary conditions differ between non-bipartite and bipartite graphs because non-bipartite graphs contain odd cycles while bipartite graphs do not. These results motivate the primary result of this work, which is an exhaustive list of achievable game outcomes on bipartite graphs. While possible outcomes are identified, it is noted that a complete characterization of when game outcomes occur is not possible on general bipartite graphs. [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]

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]

Cheating Robot games are two-player, perfect information games which formalize ideas present in two different areas of combinatorial games. The games are based on simultaneous-play but where one player (Right=Robot) has reflexes fast enough both to see where the opponent will play and to respond. This changes a simultaneous game into a sequential game but which is not covered by the theory of normal-play games. A position in a Cheating Robot game is a finite, complete bipartite graph where the edges are labeled. The vertices represent moves, and the edge labels are the subsequent positions resulting from the choice of vertices. In a position, Left chooses a vertex first, Right second, and then play moves to the new position corresponding to the edge label. This is a 'round'. This paper will only consider games in which, from any position, every sequence of moves terminates after a finite number of rounds. In a terminal game, the player with a move is the winner, if there are no moves the game is a draw. The basic theory and properties are developed, including showing that there is an equivalence relation and partial order on the games. Whilst there are no inverses in the class of all games, we show that there is a sub-class, simple hot games, in which the integers have inverses. In this sub-class, the optimal strategies are obtained by the solutions to a minimum-weight matching problem on a graph whose number of vertices equals the number of summands in the disjunctive sum. [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]

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]

In this work, we present a new model of the Discrete-Time Open Quantum Walk (DTOQW) applicable to an arbitrary graph, thereby going beyond the case of quantum walks on regular graphs. We study the impact of noise in the dynamics of quantum walk by applying Kraus operators of different dimensions which are constructed using the Weyl operators. The DTOQW employs these Kraus operators as its coin operators. The walker dynamics are studied under the impact of non-Markovian amplitude damping, dephasing and depolarizing noise channels. We also implement the walk on various graphs, including path graphs, cycle graphs, star graphs, complete graphs, complete bipartite graphs, etc. We gauge the dynamics by computing coherence and fidelity at different time steps, taking into account the influence of noise. Furthermore, we compute the probability distribution at different time-steps for the above noises, which represents the availability of the quantum walker at different vertices of the graph. [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]

Copyright of Operations Research Transactions / Yunchouxue Xuebao is the property of Editorial office of Operations Research Transactions and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

In this paper we present some geometrical representations of F 21 , the Frobenius group of order 21. The main focus is on investigating the group of common automorphisms of two orthogonal Fano planes and the automorphism group of a suitably oriented Fano plane. We show that both groups are isomorphic to F 21 , independently of the choice of the two orthogonal Fano planes and of the orientation. Moreover, since any triangular embedding of the complete graph K 7 into a surface is isomorphic, as is well known, to the classical (face 2 -colorable) toroidal biembedding, and since the two color classes define a pair of orthogonal Fano planes, we deduce, as an application of our previous result, that the group of the embedding automorphisms that preserve the color classes is the Frobenius group of order 21. In this way, we provide three geometrical representations of F 21 . Also, we apply once more the representation in terms of two orthogonal Fano planes to give an alternative proof that F 21 is the automorphism group of the Kirkman triple system of order 15 that is usually denoted as #61, thereby confirming again the potential of our Fano-plane approach. Although some of the results in this paper may be (partially) known, we include direct and independent proofs in order to make the paper self-contained and offer a unified view on the subject. [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]

We propose a Ramsey-theory-based approach for the analysis of the behavior of isolated mechanical systems containing interacting particles. The total momentum of the system in the frame of the center of masses is zero. The mechanical system is described by a Ramsey-theory-based, bi-colored, complete graph. Vectors of momenta of the particles p → i   serve as the vertices of the graph. We start from the graph representing the system in the frame of the center of masses, where the momenta of the particles in this system are p → c m i. If (p → c m i (t) · p → c m j (t)) ≥ 0 is true, the vectors of momenta of the particles numbered i and j are connected with a red link; if (p → c m i (t) · p → c m j (t)) < 0 takes place, the vectors of momenta are connected with a green link. Thus, the complete, bi-colored graph emerges. Considering an isolated system built of six interacting particles, according to the Ramsey theorem, the graph inevitably comprises at least one monochromatic triangle. The coloring procedure is invariant relative to the rotations/translations of frames; thus, the graph representing the system contains at least one monochromatic triangle in any of the frames emerging from the rotation/translation of the original frame. This gives rise to a novel kind of mechanical invariant. Similar coloring is introduced for the angular momenta of the particles. However, the coloring procedure is sensitive to Galilean/Lorenz transformations. Extensions of the suggested approach are discussed. [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]