Search

We consider the balanced two-way mixed effects design with some empty cells. A test procedure for the hypothesis of no main fixed effects is developed under violation of the assumption of variance homogeneity and symmetry. The asymptotic null distribution of the test statistics is studied under the condition that the number of levels of the random effects tends to infinity as both the number of complete and incomplete observations tend to infinity. An illustrative example is given. [ABSTRACT FROM AUTHOR]

In this manuscript we study how the vertex energy of a tree is affected when joined with a bipartite graph. We find an alternating pattern with respect to the coalescence vertex: the energy decreases for vertices located at odd distances and increases for those located at even distances. [ABSTRACT FROM AUTHOR]

We fill a gap in the proofs in the previous works (Wu X, Mu, X. Int J. Robust Nonlin Control. 2020;30:3753Ű3772; Zhang Z, Lunze J, Wang L. Int J Control. 2020;93:1005‐1014; Zhang Z, Wang L. J Robust Nonlin Control. 2018;28:4175Ű4187; Dai, M‐Z, Zhang C, Leung H, Dong P, Li B. IEEE Trans Syst, Man, Cybern: Syst. doi:10.1109/TSMC.2021.3119670) for the consensus using the integral‐based event‐triggered controls. More precisely, it was inferred for a Lyapunov function V:[0,∞)→ℝ+$$ V:\left[0,\infty \right)\to {\mathbb{R}}_{+} $$ that V˙(t)$$ \dot{V}(t) $$ is uniformly bounded by showing that V(t)$$ V(t) $$ is uniformly bounded for t≥0$$ t\ge 0 $$. However, this argument may fail without further information while the boundedness of V˙(t)$$ \dot{V}(t) $$ is crucially used for applying Barbalat's lemma. The consequence of Barbalat's lemma is that limt→∞V(t)$$ {\lim}_{t\to \infty }V(t) $$ which corresponds to the desired consensus result. To overcome this gap, Ma and Zhao (Inform Sci. 2018;457‐458:208‐221) put an extra condition about the boundedness of measurement error functions inside the proposed integral‐based event‐triggering protocol. In this article, we propose a new integral‐based event‐triggering protocol for bipartite consensus problems of the multi‐agent systems whose dynamics are described by general linear systems without adding the uniform boundedness of measurement error functions as (Ma Y, Zhao J. Inform Sci. 2018;457‐458:208‐221) did. Via our new integral‐based integral control strategy, we prove that the system achieves the bipartite consensus in asymptotic regime, and provide a complete solution of the freeness of both chattering and genuinely Zeno behaviors. Numerical results are provided supporting the effectiveness of the proposed controller. [ABSTRACT FROM AUTHOR]

Let G be a simple graph with the adjacency matrix A (G) , and let τ (G) denote the smallest positive eigenvalue of A (G). Let G n be the class of all connected bipartite graphs on n = 2 k vertices with a unique perfect matching. In this article, we characterize the graphs G in G n such that τ (G) does not exceed 1 2. Using the above characterization, we obtain the unique graphs in G n with the maximum and the second maximum τ , respectively. Further, we prove that the largest and the second largest limit points of the smallest positive eigenvalues of bipartite graphs with a unique perfect matching are 1 2 and the reciprocal of α 3 1 2 + α 3 − 1 2 , respectively, where α 3 is the largest root of x 3 − x − 1. [ABSTRACT FROM AUTHOR]

For graphs G and H , let G ⟶ k H signify that any k -edge coloring of G contains a monochromatic H as a subgraph. Let G (K 2 (N) , p) be random graph spaces with edge probability p , where K 2 (N) is the complete N × N bipartite graph. Let C 2 n be a cycle of length 2 n and let k = 2 , 3. It is shown for any ϵ > 0 , there exists T = T (ϵ) > 0 such that if n p > T , then Pr [ G (K 2 ((k + ϵ) n) , p) ⟶ k C 2 n ] → 1 as n → ∞ , for which the proof relies heavily on the sparse regularity lemma for multipartite graphs. [ABSTRACT FROM AUTHOR]

A graph G is said to be k -extendable if every matching of size k in G can be extended to a perfect matching of G , where k is a positive integer. We say G is 1-excludable if for every edge e of G , there exists a perfect matching excluding e. In this paper, we first establish a lower bound on the size (resp. the spectral radius) of G to guarantee that G is k -extendable. Then we determine a lower bound on the size (resp. the spectral radius) of G to guarantee that G is 1-excludable. All the corresponding extremal graphs are characterized. [ABSTRACT FROM AUTHOR]

Most animal pollination results from plant–insect interactions, but how we perceive these interactions may differ with the sampling method adopted. The two most common methods are observations of visits by pollinators to plants and observations of pollen loads carried by insects. Each method could favour the detection of different species and interactions, and pollen load observations typically reveal more interactions per individual insect than visit observations. Moreover, while observations concern plant and insect individuals, networks are frequently analysed at the level of species. Although networks constructed using visitation and pollen‐load data have occasionally been compared in relatively specialised, bee‐dominated systems, it is not known how sampling methodology will affect our perception of how species (and individuals within species) interact in a more generalist system. Here we use a Diptera‐dominated high‐Arctic plant–insect community to explore how sampling approach shapes several measures of species' interactions (focusing on specialisation), and what we can learn about how the interactions of individuals relate to those of species. We found that species degrees, interaction strengths, and species motif roles were significantly correlated across the two method‐specific versions of the network. However, absolute differences in degrees and motif roles were greater than could be explained by the greater number of interactions per individual provided by the pollen‐load data. Thus, despite the correlations between species roles in networks built using visitation and pollen‐load data, we infer that these two perspectives yield fundamentally different summaries of the ways species fit into their communities. Further, individuals' roles generally predicted the species' overall role, but high variability among individuals means that species' roles cannot be used to predict those of particular individuals. These findings emphasize the importance of adopting a dual perspective on bipartite networks, as based on the different information inherent in insect visits and pollen loads. [ABSTRACT FROM AUTHOR]

We investigate the minimum cost of a wide class of combinatorial optimization problems over random bipartite geometric graphs in R d where the edge cost between two points is given by a pth power of their Euclidean distance. This includes e.g. the travelling salesperson problem and the bounded degree minimum spanning tree. We establish in particular almost sure convergence, as n grows, of a suitable renormalization of the random minimum cost, if the points are uniformly distributed and d ≥ 3 , 1 ≤ p < d . Previous results were limited to the range p < d / 2 . Our proofs are based on subadditivity methods and build upon new bounds for random instances of the Euclidean bipartite matching problem, obtained through its optimal transport relaxation and functional analytic techniques. [ABSTRACT FROM AUTHOR]

Given a bipartite graph H = (V = VA ∪ VB, E) in which any vertex in VA (resp., VB) has degree at most DA (resp., DB), suppose there is a partition of V that is a refinement of the bipartition VA ∪ VB such that the parts in VA (resp., VB) have size at least KA (resp., kB). We prove that the condition DA/kB + DB/kA ≤ 1 is sufficient for the existence of an independent set of vertices of H that is simultaneously transversal to the partition and show, moreover, that this condition is sharp. This result is a bipartite refinement of two well-known results on independent transversals, one due to the second author and the other due to Szabó and Tardos. [ABSTRACT FROM AUTHOR]

We completely characterize the triangulations of the projective plane that admit a spanning bipartite quadrangulation subgraph. This is an affirmative answer to a question by Kündgen and Ramamurthi [J. Combin. Theory Ser. B, 85 (2002), pp. 307-337] for the projective planar case. [ABSTRACT FROM AUTHOR]

A graph G is called C2k+1-free if it does not contain any cycle of length 2k + 1. In 1962, Erdös (together with Gallai), and independently Andrásfai, proved that every n-vertex triangle-free graph with more than (n-1)²/4 + 1 edges is bipartite. In this paper, we extend their result and show that for 1 ≤ t 2k - 2 and 2 ≥ 318²k, every n-vertex C2k+1-free graph with more than (n-t-1)²/4 + (t+2) edges can be made bipartite by either deleting at most t - 1 vertices or deleting at most (⌊t-2⌋/2) + (⌈t+2⌉/2) - 1 edges. The construction shows that this is best possible. [ABSTRACT FROM AUTHOR]

Let G = (A ∪ B, E) be a bipartite graph where every node has a strict ranking of its neighbors. For any node, its preferences over neighbors extend naturally to preferences over matchings. A maximum matching M in G is a popular max-matching if there is no maximum matching more popular than M. In other words, for any maximum matching N, the number of nodes that prefer M to N is at least the number of nodes that prefer N to M. It is known that popular max-matchings always exist in G and one such matching can be efficiently computed. In this paper we are in the weighted setting, i.e., there is a cost function c : E → R, and our goal is to find a min-cost popular max-matching. We prove that such a matching can be computed in polynomial time by showing a compact extended formulation for the popular max-matching polytope. By contrast, it is known that the popular matching polytope has near-exponential extension complexity and finding a min-cost popular matching is NP-hard. We also consider Pareto-optimality. Though it is easy to find a Pareto-optimal matching/max-matching, we show that it is NP-hard to find a min-cost Pareto-optimal matching/max-matching. [ABSTRACT FROM AUTHOR]

A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. A graph, together with a 1-planar drawing is called 1-plane. A graph is said to be k(≥ 1)-extendable if every matching of size k can be extended to a perfect matching. It is known that the vertex connectivity of a 1-plane graph is at most 7. In this paper, we characterize the k-extendability of 7-connected maximal 1-plane graphs. We show that every 7-connected maximal 1-plane graph with even order is k-extendable for 1 ≤ k ≤ 3. And any 7-connected maximal 1-plane graph is not k-extendable for 4 ≤ k ≤ 11. As for k ≥ 12, any 7-connected maximal 1-plane graph with n vertices is not k-extendable unless n = 2k. [ABSTRACT FROM AUTHOR]

We adopt the recently introduced concept of the bipartite-hole-number due to McDiarmid and Yolov, and extend their result on Hamiltonicity to other Hamiltonian properties of graphs with a large minimum degree in terms of this concept. An (s, t)-bipartite-hole in a graph G consists of two disjoint sets of vertices S and T with |S| = s and |T| = t such that E(S, T) = ∅. The bipartite-hole-numbere ᾶ(G) is the maximum integer r such that G contains an (s, t)-bipartite-hole for every pair of nonnegative integers s and t with s + t = r. Our main results are that a graph G is traceable if δ(G) ≥ e ᾶ(G) - 1, and Hamilton-connected if δ(G) ≥ e ᾶ(G) + 1, both improving the analogues of Dirac's Theorem for traceable and Hamilton-connected graphs. [ABSTRACT FROM AUTHOR]

In this paper, we study the L(2, 1)-labeling of the Mycielski graph and the iterated Mycielski graph of graphs in general. For a graph G and all t ≥ 1, we give sharp bounds for λ(Mt(G)) the L(2, 1)-labeling number of the t-th iterated Mycielski graph in terms of the number of iterations t, the order n of G, the maximum degree △, and λ(G) the L(2, 1)-labeling number of G. For t = 1, we present necessary and sufficient conditions between the 4-star matching number of the complement graph and λ(M(G)) the L(2, 1)-labeling number of the Mycielski graph of a graph, with some applications to special graphs. For all t ≥ 2, we prove that for any graph G of order n, we have 2t-1(n + 2) - 2 ≤ λ(Mt(G)) ≤ 2t(n + 1) - 2. Thereafter, we characterize the graphs achieving the upper bound 2t(n+1)-2, then by using the Marriage Theorem and Tutte's characterization of graphs with a perfect 2-matching, we characterize all graphs without isolated vertices achieving the lower bound 2t-1(n+2)-2. We determine the L(2, 1)-labeling number for the Mycielski graph and the iterated Mycielski graph of some graph classes. [ABSTRACT FROM AUTHOR]

This work examines the time complexity of quantum search algorithms on combinatorial t-designs with multiple marked elements using the continuous-time quantum walk. Through a detailed exploration of t-designs and their incidence matrices, we identify a subset of bipartite graphs that are conducive to success compared to random-walk-based search algorithms. These graphs have adjacency matrices with eigenvalues and eigenvectors that can be determined algebraically and are also suitable for analysis in the multiple-marked vertex scenario. We show that the continuous-time quantum walk on certain symmetric t-designs achieves an optimal running time of O n , where n is the number of points and blocks, even when accounting for an arbitrary number of marked elements. Upon examining two primary configurations of marked elements distributions, we observe that the success probability is consistently o(1), but it approaches 1 asymptotically in certain scenarios. [ABSTRACT FROM AUTHOR]

We focus on characterising entanglement of high-dimensional bipartite states using various statistical correlators for two-qudit mixed states. The salient results obtained are as follows: (a) A scheme for determining the entanglement measure given by negativity is explored by analytically relating it to the widely used statistical correlators, viz. mutual predictability, mutual information and Pearson correlation coefficient, for different types of bipartite arbitrary-dimensional mixed states. Importantly, this is demonstrated using only a pair of complementary observables pertaining to the mutually unbiased bases. (b) The relations thus derived provide the separability bounds for detecting entanglement obtained for a fixed choice of the complementary observables, while the bounds per se are state-dependent. Such bounds are compared with the earlier suggested separability bounds. (c) We also show how these statistical correlators can enable distinguishing between the separable, distillable and bound entanglement domains of the one-parameter Horodecki two-qutrit states. Further, the relations linking negativity with the statistical correlators have been derived for such Horodecki states in the domain of distillable entanglement. Thus, this entanglement characterisation scheme based on statistical correlators and harnessing complementarity of the observables opens up a potentially rich direction of study which is applicable for both distillable and bound entangled states. [ABSTRACT FROM AUTHOR]

In this paper, the properties of many-body localization (MBL) in one-dimensional disordered Heisenberg XXX spin-1 chains are studied theoretically by using the methods of exact matrix diagonalization. We compare it with the MBL properties of the Heisenberg spin-1/2 chains. We first study properties of the eigenstates of the model through the excited-state fidelity. By analyzing the inflection point of excited-state fidelity curves, we can roughly determine the critical point of MBL phase transition. Moreover, for the case of random disorder, we calculated the bipartite entanglement entropy, and the critical points obtained from the intersection of curves for different systems sizes were basically consistent with those obtained from excited-state fidelity. Then we study the dynamical properties of the model by the dynamical behavior of diagonal entropy (DE), local magnetization and the time evolution of fidelity to further prove the occurrence of MBL phase transition in the disordered Heisenberg XXX spin-1 chain and distinguish the ergodic phase (thermal phase) and the many-body localized phase. We can illustrate that in the localized phase, the information of the initial state can be well protected if the disorder strength of the system is large enough. There are various forms of disorder, and we compare the effects of different forms of quasi-disorder and random disorder on MBL in this article. We also investigate the effect of non-uniform disorder external field on MBL. Our results reveal that disorder can cause the occurrence of MBL in the one-dimensional disordered Heisenberg XXX spin-1 chains. Furthermore, the form of disorder, the properties of the spin, and the size of the system all affect the critical point of the MBL phase transition. [ABSTRACT FROM AUTHOR]

The canonical decomposition of a bipartite graph is a new decomposition method that involves three operators: parallel, series, and K ⨁   S . The class of weak-bisplit graphs is the class of totally decomposable graphs with respect to these operators, and the class of bicographs is the class of totally decomposable graphs with respect to parallel and series operators. We prove in this paper that the class of bipartite (P 6 , C 6) -free graphs is the class of bipartite graphs that are totally decomposable with respect to parallel and K ⨁ S operators. We present a linear time recognition algorithm for (P 6 , C 6) -free graphs that is symmetrical to the linear recognition algorithms of weak-bisplit graphs and s t a r 1,2 , 3 -free bipartite graphs. As a result of this algorithm, we present efficient solutions in this class of graphs for two optimization graph problems: the maximum balanced biclique problem and the maximum independent set problem. [ABSTRACT FROM AUTHOR]

The second largest eigenvalue of a graph is an important algebraic parameter which is related with the expansion, connectivity and randomness properties of a graph. Expanders are highly connected sparse graphs. In coding theory, Expander codes are Error Correcting codes made up of bipartite expander graphs. In this paper, first we prove the interlacing of the eigenvalues of the adjacency matrix of the bipartite graph with the eigenvalues of the bipartite quotient matrices of the corresponding graph matrices. Then we obtain bounds for the second largest and second smallest eigenvalues. Since the graph is bipartite, the results for Laplacian will also hold for Signless Laplacian matrix. We then introduce a new method called vertex-split of a bipartite graph to construct asymptotically good expander codes with expansion factor D/2 < α < D and ϵ < 1/2 and prove a condition for the vertex-split of a bipartite graph to be k-connected with respect to λ2. Further, we prove that the vertex-split of G is a bipartite expander. Finally, we construct an asymptotically good expander code whose factor graph is a graph obtained by the vertex-split of a bipartite graph. [ABSTRACT FROM AUTHOR]

Given a class of graphs H , the problem ⊕ Sub (H) is defined as follows. The input is a graph H ∈ H together with an arbitrary graph G. The problem is to compute, modulo 2, the number of subgraphs of G that are isomorphic to H. The goal of this research is to determine for which classes H the problem ⊕ Sub (H) is fixed-parameter tractable (FPT), i.e., solvable in time f (| H |) · | G | O (1) . Curticapean, Dell, and Husfeldt (ESA 2021) conjectured that ⊕ Sub (H) is FPT if and only if the class of allowed patterns H is matching splittable, which means that for some fixed B, every H ∈ H can be turned into a matching (a graph in which every vertex has degree at most 1) by removing at most B vertices. Assuming the randomised Exponential Time Hypothesis, we prove their conjecture for (I) all hereditary pattern classes H , and (II) all tree pattern classes, i.e., all classes H such that every H ∈ H is a tree. We also establish almost tight fine-grained upper and lower bounds for the case of hereditary patterns (I). [ABSTRACT FROM AUTHOR]

Who interacts with whom is a key question in community and network ecology. The concept that these interactions may be driven by a match between the traits of consumer and resource species is known as trait‐matching. If trait‐matching would allow for general predictions of interaction structure based on sufficiently few and easily‐measurable traits, then this approach could replace the laborious description of each individual pairwise interaction. To resolve imprints of trait‐matching in a species‐rich tri‐trophic Salix–galler–parasitoid network, and to identify the most relevant traits, we applied five different methods, each approaching the same phenomenon from a different perspective. As traits, we used, body sizes, gall type (position on plant, structure of gall) and phenology, among others, as well as phylogenetic proxies. When jointly applied, the methods demonstrate distinctly different imprints of traits within the two bipartite network elements (Salix–galler versus galler–parasitoid interactions). Of the galler–parasitoid sub‐network's interactions, approximately half were explainable by the species traits used; of the Salix–galler sub‐network's interactions, traits explained at most two‐fifths. Gall type appeared to be the most important structuring trait in both networks. Phylogeny explained as much, or more than did our tested traits, suggesting that traits may be conserved and phylogeny therefore an effective proxy. Overall, the more specialized structure of the Salix–galler network versus the more nested structure of the galler–parasitoid network meant that different methods were more effective at capturing interactions and interaction structure in the different sub‐networks. Thus, our analysis reveals how structuring impacts may vary even between levels within the same multitrophic network, and calls for comparative analyses of trait matching across a wide set of systems and methods. [ABSTRACT FROM AUTHOR]

Antagonistic host–parasitoid interactions can be quantified using bipartite and metanetworks, which have the potential to reveal how habitat structural elements relate to this important ecosystem function.Here, we analysed the host–parasitoid interactions of cavity‐nesting bees and wasps, as well as their abundance, diversity and species richness with forest structural elements from 127 forest research plots in southwestern Germany.We found that parasitoid abundance, diversity and species richness all increase with host abundance, a potential mediator between parasitoids and forest structure. Both parasitoid abundance and diversity increased with stand structural complexity, possibly mediated by the abundance of hosts. In addition, parasitoid abundance increased with increasing standing deadwood and herb cover.The bipartite networks of host–parasitoid interactions showed higher connectance with increasing standing deadwood, herb cover and host abundance. Analyses of interactions within the host–parasitoid metanetwork revealed that increasing host abundance and decreasing canopy cover diversify the suites of interactions present at the plot level.These results demonstrate that forest structural elements can improve the stability and resilience of host–parasitoid networks by promoting parasitoids and diversifying interactions in ecological networks. [ABSTRACT FROM AUTHOR]

Ecological networks describe community structure by focusing on how nodes are connected by links (interactions). Related species have higher probabilities of sharing links if interactions depending on phylogeny and/or species are functionally similar; however, if and how this modularity impacts higher trophic levels is still an open question.We aimed to evaluate the effect of different structuring factors on an observed bipartite network of galling insects and associated parasitoids on a system with two closely related and recently diverged plants, where host‐tracking could be underway. We hypothesized that gall structure, galler taxonomy and host plant identity could contribute, from a higher to a lower degree respectively, to network modularity by generating a selective pressure on parasitoids.Samples were collected between May 2015 and June 2017 in the forest areas of Porto Alegre, southern Brazil. Overall, we found 4629 galls of three monophagous and four oligophagous galling species; 664 parasitoid individuals were obtained and classified into 37 morphospecies.We constructed four networks with the collected data by organising nodes according to the tested factors, that is, gall structure, galler taxonomy, host plant identity and gall–plant interaction. All networks were significantly modular, and for three out of four analysed factors (gall structure, galler taxonomy and gall–plant interaction), modularity levels were at least intermediate (at about Q = 0.4).Barriers to or preferences for certain interactions appear to be responses to multiple concomitant factors. However, galler taxonomy and host plant identity are somehow stronger determinants for the parasitoids in terms of attacked hosts. [ABSTRACT FROM AUTHOR]

In this paper, we introduced a new graph polynomial called the vertex geodetic closure polynomial of a graph and established results for paths, complete bipartite graphs, and graphs resulting from the join of two graphs. [ABSTRACT FROM AUTHOR]

The biclique partition number of a graph G, denoted by bp(G), is the minimum number of complete bipartite subgraphs are needed to be representing all edges of G. A graph G is called an eigensharp graph if it is satisfying bp(G) = max{i-(A(G)), i+(A(G))} where i-(A(G)) and i+(A(G)) are the number of negative and positive eigenvalues of the adjacency matrix of G, respectively. In this paper, we are interested in studying some special graphs in terms of having the property of eigensharp. We show that the barbell graph, the sun graph, the friendship graph and their complements have the property of eigensharp. [ABSTRACT FROM AUTHOR]

A matching M $M$ in a graph G $G$ is semistrong if every edge of M $M$ has an endvertex of degree one in the subgraph induced by the vertices of M $M$. A semistrong edge‐coloring of a graph G $G$ is a proper edge‐coloring in which every color class induces a semistrong matching. In this paper, we continue investigation of properties of semistrong edge‐colorings initiated by Gyárfás and Hubenko. We establish tight upper bounds for general graphs and for graphs with maximum degree 3. We also present bounds about semistrong edge‐coloring which follow from results regarding other, at first sight nonrelated, problems. We conclude the paper with several open problems. [ABSTRACT FROM AUTHOR]

What are the unavoidable induced subgraphs of graphs with large treewidth? It is well‐known that the answer must include a complete graph, a complete bipartite graph, all subdivisions of a wall and line graphs of all subdivisions of a wall (we refer to these graphs as the "basic treewidth obstructions"). So it is natural to ask whether graphs excluding the basic treewidth obstructions as induced subgraphs have bounded treewidth. Sintiari and Trotignon answered this question in the negative. Their counterexamples, the so‐called "layered wheels," contain wheels, where a wheel consists of a hole (i.e., an induced cycle of length at least four) along with a vertex with at least three neighbors in the hole. This leads one to ask whether graphs excluding wheels and the basic treewidth obstructions as induced subgraphs have bounded treewidth. This also turns out to be false due to Davies' recent example of graphs with large treewidth, no wheels and no basic treewidth obstructions as induced subgraphs. However, in Davies' example there exist holes and vertices (outside of the hole) with two neighbors in them. Here we prove that a hole with a vertex with at least two neighbors in it is inevitable in graphs with large treewidth and no basic obstruction. Our main result is that graphs in which every vertex has at most one neighbor in every hole (that does not contain it) and with the basic treewidth obstructions excluded as induced subgraphs have bounded treewidth. [ABSTRACT FROM AUTHOR]

Given a skew-symmetric matrix X, the Pfaffian of X is defined as the square root of the determinant of X. In this article, we give the explicit defining equations of the Rees algebra of a Pfaffian ideal I generated by the maximal order Pfaffians of a generic skew-symmetric matrix. We further prove that all diagonal subalgebras of the corresponding Rees algebra of I are Koszul. We also look at Rees algebras of Pfaffian ideals of linear type associated with certain sparse skew-symmetric matrices. In particular, we consider the tridiagonal matrices and identify the corresponding Pfaffian ideals to be of Gröbner linear type and as the vertex cover ideals of unmixed bipartite graphs. As an application of our results, we conclude that all their ordinary and symbolic powers have linear quotients. [ABSTRACT FROM AUTHOR]

The distance energy of a connected graph G is the sum of absolute values of the eigenvalues of the distance matrix of G. In this paper, we study how the distance energy of the complete split graph G S (m , n) = K m + K ¯ n changes when an edge is deleted from it. The complete split graph G S (m , n) consists of a clique on m vertices and an independent set on n vertices in which each vertex of the clique is adjacent to each vertex of the independent set. We prove that the distance energy of the complete split graph G S (m , n) always increases when an edge is deleted from it. [ABSTRACT FROM AUTHOR]

Graph protection using mobile guards has received a lot of attention in the literature. It has been considered in different forms, including Eternal Dominating set, Eternal Independent set and Eternal Vertex Cover set. In this paper, we introduce and study two new models of graph protection, namely Eternal Feedback Vertex Sets (EFVS) and m-Eternal Feedback Vertex Sets (m-EFVS). Both models are based on an initial selection of a feedback vertex set (FVS), where a vertex in FVS can be replaced with a neighboring vertex such that the resulting set is a FVS too. We prove bounds for both the eternal and m-eternal feedback vertex numbers on, mainly, distance graphs, circulant graphs and grids. Also, we deduce other inequalities for both parameters on cycles, complete graphs and complete bipartite graphs. [ABSTRACT FROM AUTHOR]

A chain graph is a bipartite graph in which the neighborhood of the vertices in each partite set forms a chain with respect to set inclusion. By extending the concept of nesting from a bipartite graph to a k partite graph, a k-nested graph is defined. A half graph is a chain graph having no pairs of duplicate vertices. Similarly, a 'k-half graph' is a class of knested graph with no pairs of duplicate vertices. The (first) Zagreb matrix or Z-matrix denoted by Z(G) = (zij)n×n of a graph G, whose vertex vi has degree di is defined by zij = di + dj if the vertices vi and vj are adjacent and zij = 0 otherwise. Let ζ1, ζ2, . . ., ζn be the Zagreb eigenvalues of Z(G) and the Zagreb energy is the sum of the absolute values of the Zagreb eigenvalues. We obtain the determinant, eigenvalues and inverse of a k-half graph with respect to the Z-matrix. Bounds for the Zagreb energy and spectral radius are discussed along with the main and non-main Zagreb eigenvalues of a k-half graph. [ABSTRACT FROM AUTHOR]

We construct an infinite family of bounded-degree bipartite unique neighbour expander graphs with arbitrarily unbalanced sides. Although weaker than the lossless expanders constructed by Capalbo et al., our construction is simpler and may be closer to being implementable in practice, due to the smaller constants. We construct these graphs by composing bipartite Ramanujan graphs with a fixed-size gadget in a way that generalises the construction of unique neighbour expanders by Alon and Capalbo. For the analysis of our construction, we prove a strong upper bound on average degrees in small induced subgraphs of bipartite Ramanujan graphs. Our bound generalises Kahale's average degree bound to bipartite Ramanujan graphs, and may be of independent interest. Surprisingly, our bound strongly relies on the exact Ramanujan-ness of the graph and is not known to hold for nearly-Ramanujan graphs. [ABSTRACT FROM AUTHOR]

This study introduces a novel movie recommender system utilizing a Semantic-Enhanced Variational Graph Autoencoder for Movie Recommendation (SeVGAER) architecture. The system harnesses additional information from movie plot summaries scraped from the internet, transformed into semantic vectors via a large language model. These vectors serve as supplementary features for movie nodes in the SeVGAER-based recommender. The system incorporates an encoder-decoder structure, operating on a user-movie bipartite graph, and employs GraphSAGE convolutional layers with modified aggregators as the encoder to extract latent representations of the nodes, and a Multi-Layer Perceptron (MLP) as the decoder to predict ratings with additional graph-based features. To address overfitting and improve model generalization, a novel training strategy is introduced. We employ a random data splitting approach, dividing the dataset into two halves for each training instance. The model then generates outputs on each half of the data, and a new loss function is introduced to ensure consistency between these two outputs, a strategy that can be seen as a form of contrastive learning. The model’s performance is optimized using a combination of this new contrastive loss, graph reconstruction loss, and KL divergence loss. Experiments conducted on the Movielens100k dataset demonstrate the effectiveness of this approach in enhancing movie recommendation performance. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Central China Normal University is the property of Huazhong Normal University 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.)

For 0 ≤ t ≤ r let m(t, r) be the maximum number s such that every t-edge-connected r-graph has s pairwise disjoint perfect matchings. There are only a few values of m(t, r) known, for instance m (3 , 3) = m (4 , r) = 1 , and m (t , r) ≤ r - 2 for all t ≠ 5 , and m (t , r) ≤ r - 3 if r is even. We prove that m (2 l , r) ≤ 3 l - 6 for every l ≥ 3 and r ≥ 2 l . [ABSTRACT FROM AUTHOR]

Soil salinization poses a global threat to terrestrial ecosystems. Soil microorganisms, crucial for maintaining ecosystem services, are sensitive to changes in soil structure and properties, particularly salinity. In this study, contrasting dynamics within the rhizosphere and bulk soil were focused on exploring the effects of heightened salinity on soil microbial communities, evaluating the influences shaping their composition in saline environments. This study observed a general decrease in bacterial alpha diversity with increasing salinity, along with shifts in community structure in terms of taxa relative abundance. The size and stability of bacterial co-occurrence networks declined under salt stress, indicating functional and resilience losses. An increased proportion of heterogeneous selection in bacterial community assembly suggested salinity's critical role in shaping bacterial communities. Stochasticity dominated fungal community assembly, suggesting their relatively lower sensitivity to soil salinity. However, bipartite network analysis revealed that fungi played a more significant role than bacteria in intensified microbial interactions in the rhizosphere under salinity stress compared to the bulk soil. Therefore, microbial cross-domain interactions might play a key role in bacterial resilience under salt stress in the rhizosphere. [ABSTRACT FROM AUTHOR]

As a popular graph learning technique, graph neural networks (GNN) show great advantages in the field of personalized recommendation. Existing GNN-based recommendation methods organized user-item interactions (e.g., click, purchase, review, etc.) as the bipartite graph and captured the higher-order collaborative signal with the aid of the GNN to achieve personalized recommendation. However, there exists two limitations in existing studies. First, core features activating user-item interactions were not be identified, which causes that user-item interactions fail to be accurately exploited at the feature level. Second, existing GNNs ignored the mutual association among neighbors in information propagation, which results in structural signal in the bipartite graph not being sufficiently captured. Towards this end, we developed the core features activated graph dual-attention network, namely C-GDN, for personalized recommendation. Specifically, C-GDN firstly identifies core user and item features activating user-item interactions and employs these core features to initialize the bipartite graph, which effectively optimizes the utilizing of user-item interactions at the feature level. Furthermore, C-GDN designs a novel graph dual-attention network to conduct information propagation, which captures more sufficient structural signal in the bipartite graph by considering information from neighbors as well as their mutual association. Extensive experiments on three benchmark datasets shows that C-GDN outperforms state-of-the-art baselines. [ABSTRACT FROM AUTHOR]

We studied radio labelings of graphs in response to the Channel Assignment Problem (CAP). In a graph G, the radio labeling is a mapping ϖ: V(G) → {0, 1, 2,..., }, such as |ϖ(μ') - ϖ(μ")| ≥ diam(G)+1-d(μ', μ"). The label of μ for under ϖ is defined by the integer ϖ(μ), and the span under is defined by span(ϖ) = max{|ϖ(μ') - ϖ(μ")|: μ', μ&" ∈ V(G)}. rn(G) = minϖspan(ϖ) is defined as the radio number of G when the minimum over all radio labeling ϖ of G is taken. G is said to be optimal if its radio labeling is span(ϖ) = rn(G). A graph H is said to be an m super subdivision if G is replaced by the complete bipartite graph Km,m with m = 2 in such a way that the end vertices of the edge are merged with any two vertices of the same partite set X or Y of Km,m after removal of the edge of G. Up to this point, many lower and upper bounds of rn(G) have been found for several kinds of graph families. This work presents a comprehensive analysis of the radio number rn(G) for a graph G, with particular emphasis on the m super subdivision of a path Pn with n(n ≥ 3) vertices, along with a complete bipartite graph Km,m consisting of m v/ertices, where m = 2. [ABSTRACT FROM AUTHOR]

We consider $ t $-Lee-error-correcting codes of length $ n $ over the residue ring $ \mathbb{Z}_{m} : = \mathbb{Z}/m\mathbb{Z} $ and determine upper and lower bounds on the number of $ t $-Lee-error-correcting codes. We use two different methods, namely estimating isolated nodes on bipartite graphs and the graph container method. The former gives density results for codes of fixed size and the latter for any size. This confirms some recent density results for linear Lee metric codes and provides new density results for nonlinear codes. To apply a variant of the graph container algorithm we also investigate some geometrical properties of the balls in the Lee metric. [ABSTRACT FROM AUTHOR]

The goal of this work is to give precise bounds on the counting complexity of a family of generalized coloring problems (list homomorphisms) on bounded-treewidth graphs. Given graphs G, H, and lists L (v) ⊆ V(H) for every v∈ V(G), a f:V(G)→ V(H) that preserves the edges (i.e., uv∈ E(G) implies f(u)f(v)∈ E(H)) and respects the lists (i.e., f(v)∈ L(v)). Standard techniques show that if G is given with a tree decomposition of width t, then the number of list homomorphisms can be counted in time |V(H)|t⋅ n(1). Our main result is determining, for every fixed graph H, how much the base |V(H)| in the running time can be improved. For a connected graph H, we define irr(H) in the following way: if H has a loop or is nonbipartite, then irr(H) is the maximum size of a set S⊆ V(H) where any two vertices have different neighborhoods; if H is bipartite, then irr(H) is the maximum size of such a set that is fully in one of the bipartition classes. For disconnected H, we define irr(H) as the maximum of irr(C) over every connected component C of H. It follows from earlier results that if irr(H)=1, then the problem of counting list homomorphisms to H is polynomial-time solvable, and otherwise it is #P-hard. We show that, for every fixed graph H, the number of list homomorphisms from (G,L) to H — can be counted in time \(\operatorname{irr}(H)^t\cdot n^{\mathcal {O}(1)}\) if a tree decomposition of G having width at most t is given in the input, and, — given that \(\operatorname{irr}(H)\ge 2\) , cannot be counted in time \((\operatorname{irr}(H)-\varepsilon)^t\cdot n^{\mathcal {O}(1)}\) for any \(\varepsilon \gt 0\) , even if a tree decomposition of G having width at most t is given in the input, unless the Counting Strong Exponential-Time Hypothesis (#SETH) fails. Thereby, we give a precise and complete complexity classification featuring matching upper and lower bounds for all target graphs with or without loops. [ABSTRACT FROM AUTHOR]

Motivated by bipartite Gallai–Ramsey type problems, we consider edge-colorings of complete bipartite graphs without rainbow tree and matching. Given two graphs G and H , and a positive integer k , define the bipartite Gallai–Ramsey number bgr k (G : H) as the minimum number of vertices n such that n 2 ≥ k and for every N ≥ n , any coloring (using all k colors) of the complete bipartite graph K N , N contains a rainbow copy of G or a monochromatic copy of H. In this paper, we first describe the structures of a complete bipartite graph K n , n without rainbow P 4 + and 3 K 2 , respectively, where P 4 + is the graph consisting of a P 4 with one extra edge incident with an interior vertex. Furthermore, we determine the exact values or upper and lower bounds on bgr k (G : H) when G is a 3-matching or a 4-path or P 4 + , and H is a bipartite graph. [ABSTRACT FROM AUTHOR]

Paintability of graphs, which is also called online choosability of graphs, was introduced by Schauz and by Zhu in 2009, and has been studied in point of the difference from choosability of graphs. Compared with the choice number and the chromatic number, it is much more difficult to determine the paint number of a given graph. For example, even the 3-paintable complete bipartite graphs have not been characterized yet. In this paper, we focus on the paintability of complete bipartite graphs, especially m -paintability of K m + 1 , r. Let r OL (m) denote the least integer r such that K m + 1 , r is not m -paintable. In this paper, we determine the order of r OL (m) as r OL (m) = Θ (m m − 1). Let r (m) denote the least r such that K m + 1 , r is not m -choosable, for which Hoffman and Johnson Jr. determined as r (m) = m m − (m − 1) m = Θ (m m). As a corollary, we can show that r OL (m) / r (m) tends to 0 when m goes to infinity. [ABSTRACT FROM AUTHOR]

Identifying the rank of species in a complex ecosystem is a difficult task, since the rank of each species invariably depends on the interactions stipulated with other species through the adjacency matrix of the network. A common ranking method in economic and ecological networks is to sort the nodes such that the layout of the reordered adjacency matrix looks maximally nested with all nonzero entries packed in the upper left corner, called Nestedness Maximization Problem (NMP). Here we solve this problem by defining a suitable cost-energy function for the NMP which reveals the equivalence between the NMP and the Quadratic Assignment Problem, one of the most important combinatorial optimization problems, and use statistical physics techniques to derive a set of self-consistent equations whose fixed point represents the optimal nodes' rankings in an arbitrary bipartite mutualistic network. Concurrently, we present an efficient algorithm to solve the NMP that outperforms state-of-the-art network-based metrics and genetic algorithms. Eventually, our theoretical framework may be easily generalized to study the relationship between ranking and network structure beyond pairwise interactions, e.g. in higher-order networks. Species forming complex ecological or economic ecosystems are organized in hierarchies and the ranks of such species are determined by the adjacency matrix of their interaction network. We introduce a framework to calculate the ranks of species by finding the optimal permutation of rows and columns that makes the adjacency matrix maximally nested. [ABSTRACT FROM AUTHOR]

The genus Dendroctonus is a Holarctic taxon composed of 21 nominal species; some of these species are well known in the world as disturbance agents of forest ecosystems. Under the bark of the host tree, these insects are involved in complex and dynamic associations with phoretic ectosymbiotic and endosymbiotic communities. Unlike filamentous fungi and bacteria, the ecological role of yeasts in the bark beetle holobiont is poorly understood, though yeasts were the first group to be recorded as microbial symbionts of these beetles. Our aim was characterize and compare the gut fungal assemblages associated to 14 species of Dendroctonus using the internal transcribed spacer 2 (ITS2) region. A total of 615,542 sequences were recovered yielding 248 fungal amplicon sequence variants (ASVs). The fungal diversity was represented by 4 phyla, 16 classes, 34 orders, 54 families, and 71 genera with different relative abundances among Dendroctonus species. The α-diversity consisted of 32 genera of yeasts and 39 genera of filamentous fungi. An analysis of β-diversity indicated differences in the composition of the gut fungal assemblages among bark beetle species, with differences in species and phylogenetic diversity. A common core mycobiome was recognized at the genus level, integrated mainly by Candida present in all bark beetles, Nakazawaea, Cladosporium, Ogataea, and Yamadazyma. The bipartite networks confirmed that these fungal genera showed a strong association between beetle species and dominant fungi, which are key to maintaining the structure and stability of the fungal community. The functional variation in the trophic structure was identified among libraries and species, with pathotroph-saprotroph-symbiotroph represented at the highest frequency, followed by saprotroph-symbiotroph, and saprotroph only. The overall network suggested that yeast and fungal ASVs in the gut of these beetles showed positive and negative associations among them. This study outlines a mycobiome associated with Dendroctonus nutrition and provides a starting point for future in vitro and omics approaches addressing potential ecological functions and interactions among fungal assemblages and beetle hosts. [ABSTRACT FROM AUTHOR]

The Turán density of an |$r$| -uniform hypergraph |${\mathcal {H}}$|⁠ , denoted |$\pi ({\mathcal {H}})$|⁠ , is the limit of the maximum density of an |$n$| -vertex |$r$| -uniform hypergraph not containing a copy of |${\mathcal {H}}$|⁠ , as |$n \to \infty $|⁠. Denote by |${\mathcal {C}}_{\ell }$| the |$3$| -uniform tight cycle on |$\ell $| vertices. Mubayi and Rödl gave an "iterated blow-up" construction showing that the Turán density of |${\mathcal {C}}_{5}$| is at least |$2\sqrt {3} - 3 \approx 0.464$|⁠ , and this bound is conjectured to be tight. Their construction also does not contain |${\mathcal {C}}_{\ell }$| for larger |$\ell $| not divisible by |$3$|⁠ , which suggests that it might be the extremal construction for these hypergraphs as well. Here, we determine the Turán density of |${\mathcal {C}}_{\ell }$| for all large |$\ell $| not divisible by |$3$|⁠ , showing that indeed |$\pi ({\mathcal {C}}_{\ell }) = 2\sqrt {3} - 3$|⁠. To our knowledge, this is the first example of a Turán density being determined where the extremal construction is an iterated blow-up construction. A key component in our proof, which may be of independent interest, is a |$3$| -uniform analogue of the statement "a graph is bipartite if and only if it does not contain an odd cycle". [ABSTRACT FROM AUTHOR]

The mathematical side of applied problems in multiple subject areas (biology, pattern recognition, etc.) is reduced to the problem of discrete optimization in the following mathematical method. We were provided a network and graphs in its leaves, for which we needed to find a rearrangement of graphs by non-leaf nodes, in which the given functional reached its minimum. Such a problem, even in the simplest case, is NP-hard, which means unavoidable restrictions on the network, on graphs, or on the functional. In this publication, this problem is addressed in the case of all graphs being so-called "structures", meaning directed-loaded graphs consisting of paths and cycles, and the functional as the sum (over all edges in the network) of distances between structures at the endpoints of every edge. The distance itself is equal to the minimal length of sequence from the fixed list of operations, the composition of which transforms the structure at one endpoint of the edge into the structure at its other endpoint. The list of operations (and their costs) on such a graph is fixed. Under these conditions, the given discrete optimization problem is called the reconstruction problem. This paper presents novel algorithms for solving the reconstruction problem, along with full proofs of their low error and low polynomial complexity. For example, for the network, the problem is solved with a zero error algorithm that has a linear polynomial computational complexity; and for the tree the problem is solved using an algorithm with a multiplicative error of at most two, which has a second order polynomial computational complexity. [ABSTRACT FROM AUTHOR]

In this paper, we quantitatively study the dynamics of the tripartite entanglement of the three-mode Gaussian state in a cavity-free optomechanical system. After deriving the explicit form of the evolved state matrix covariance, we elucidate in detail the evidence of entanglement monogamy in different mode partitions, based on Coofman–Kundu–Wotters inequalities, using the Gaussian Contangle quantifying bipartite entanglement. Next, we focus on the genuine tripartite entanglement quantified by means of the Residual Gaussian Contangle. [ABSTRACT FROM AUTHOR]

Centrality measurement plays an important role to identify important/influential vertices and edges in a network or graph from different points of view. It also provide invaluable insights into the structure and functioning of interconnected systems, enabling researchers to identify critical nodes for targeted interventions, predict network behaviors, and optimize network performance. Though there are different centrality measurements in graphs theory, yet closeness centrality is widely used to analyze biological networks, social networks, fuzzy social network, transportation networks, etc. The closeness centrality of a node x in a network/graph is the unit fraction whose denominator is the sum of the distances from x to other nodes. This paper presents theoretical development to compute the closeness centrality of each node/vertex of different corona product graphs between well known graph (path graph, complete graph, cycle graph, wheel graph, star graph and complete bipartite graph) and general graph. Corona graph has lots of applications in signed networks, biotechnology, chemistry, small-world network, etc. We also present a suitable real application of our proposed results by which we can identify the influential nodes in small-world network. [ABSTRACT FROM AUTHOR]

The state-owned power Electricity Generating Authority of Thailand (EGAT), a monopoly market in charge of producing, distributing, and wholesaling power, is the focal point of Thailand's electricity market. Although the government has encouraged people to install on-grid solar panels to sell electricity as producers and retail consumers, the price mechanism, i.e., purchasing price and selling prices, is still unilaterally determined by the government. Therefore, we are interested in studying the case where blockchain can be used as a free trading platform. Without involving buying or selling from the government, this research presents a model of fully traded price mechanisms. Based on the study results of the double auction system, data on buying and selling prices of electrical energy in Thailand were used as the initial data for the electricity peer-to-peer free-trading model. Then, information was obtained to analyze the trading price trends by using the law of demand and supply in addition to the principle of the bipartite graph. The price trend results agree well with those of price equilibrium equations. Therefore, we firmly believe that the model we offer can be traded in a closed system of free-trade platforms. In addition, the players in the system can help to determine the price trend that will occur according to various parameters and will cause true fairness in the sustainable electricity supply chain industry in Thailand. [ABSTRACT FROM AUTHOR]