Search

We consider the classic budgeted maximum weight independent set (BMWIS) problem. The input is a graph G = (V , E) , where each vertex v ∈ V has a weight w (v) and a cost c (v) , and a budget B. The goal is to find an independent set S ⊆ V in G such that ∑ v ∈ S c (v) ≤ B , which maximizes the total weight ∑ v ∈ S w (v). Since the problem on general graphs cannot be approximated within ratio | V | 1 − ɛ for any ɛ > 0 , BMWIS has attracted significant attention on graph families for which a maximum weight independent set can be computed in polynomial time. Two notable such graph families are bipartite and perfect graphs. BMWIS is known to be NP-hard on both of these graph families; however, prior to this work, the best possible approximation guarantees for these graphs were wide open. In this paper, we give a tight 2-approximation for BMWIS on perfect graphs and bipartite graphs. In particular, we give a (2 − ɛ) lower bound for BMWIS on bipartite graphs, already for the special case where the budget is replaced by a cardinality constraint, based on the Small Set Expansion Hypothesis (SSEH). For the upper bound, we design a 2-approximation for BMWIS on perfect graphs using a Lagrangian relaxation based technique. Finally, we obtain a tight lower bound for the capacitated maximum weight independent set (CMWIS) problem, the special case of BMWIS where w (v) = c (v) ∀ v ∈ V. We show that CMWIS on bipartite and perfect graphs is unlikely to admit an efficient polynomial-time approximation scheme (EPTAS). Thus, the existing PTAS for CMWIS is essentially the best we can expect. [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]

A new kind of bipartite graph is defined in this paper. The work is motivated mainly from a graph introduced by Al-Kaseasbeh and Erfanian [A bipartite graph associated to elements and cosets of subgroups of a finite group, AIMS Math. 6(10) (2021) 10395–10404] and partially from the undirected power graph of a group and from the inclusion graph. For a nontrivial group G, we define a simple undirected bipartite graph Γ(G) with the vertex set V (Γ(G)) = A ∪ B, where A is the set of all elements of the group G and B is the set of all subgroups H of G such that H≠{e} and two vertices a ∈ A and H ∈ B are adjacent if and only if a2 ∈ H. Here, we classify all the finite groups G whose bipartite graphs Γ(G) are planar. In addition, we also classify the finite groups G such that Γ(G) is outerplanar, maximal planar, maximal outerplanar, star, tree, claw graph, respectively. The planarity of the graph Γ(G) corresponding to an infinite group G has also been investigated here. It is also observed that Γ(G) satisfies Vizing’s conjecture. [ABSTRACT FROM AUTHOR]

The classical extremal function for a graph H , ex (K n , H) is the largest number of edges in a subgraph of K n that contains no subgraph isomorphic to H. Note that defining ex (K n , H − ind) by forbidding induced subgraphs isomorphic to H is not very meaningful for a non-complete H since one can avoid it by considering a clique. For graphs F and H , let ex (K n , { F , H − ind }) be the largest number of edges in an n -vertex graph that contains no subgraph isomorphic to F and no induced subgraph isomorphic to H. Determining this function asymptotically reduces to finding either ex (K n , F) or ex (K n , H) , unless H is a biclique or both F and H are bipartite. Here, we consider the bipartite setting, ex (K n , n , { F , H − ind }) when K n is replaced with K n , n , F is a biclique, and H is a bipartite graph. Our main result, a strengthening of a result by Sudakov and Tomon, implies that for any d ≥ 2 and any K d , d -free bipartite graph H with each vertex in one part of degree either at most d or a full degree, so that there are at most d − 2 full degree vertices in that part, one has ex (K n , n , { K t , t , H − ind }) = o (n 2 − 1 / d). This provides an upper bound on the induced Turán number for a wide class of bipartite graphs and implies in particular an extremal result for bipartite graphs of bounded VC-dimension by Janzer and Pohoata. [ABSTRACT FROM AUTHOR]

An edge-coloured path is monochromatic if all of its edges have the same colour. For a k -connected graph G , the monochromatic k -connection number of G , denoted by m c k (G) , is the maximum number of colours in an edge-colouring of G such that, any two vertices are connected by k internally vertex-disjoint monochromatic paths. In this paper, we shall study the parameter m c k (G). We obtain bounds for m c k (G) , for general graphs G. We also compute m c k (G) exactly when k is small, and G is a graph on n vertices, with a spanning k -connected subgraph having the minimum possible number of edges, namely ⌈ k n 2 ⌉. We prove a similar result when G is a bipartite graph. [ABSTRACT FROM AUTHOR]

A bipartite graph G is two-disjoint-cycle-cover edge [ r 1 , r 2 ] -bipancyclic if, for any vertex-disjoint edges u v and x y in G and any even integer ℓ satisfying r 1 ⩽ ℓ ⩽ r 2 , there exist vertex-disjoint cycles C 1 and C 2 such that | V (C 1) | = ℓ , | V (C 2) | = | V (G) | − ℓ , u v ∈ E (C 1) and x y ∈ E (C 2). In this paper, we prove that the n -star graph S n is two-disjoint-cycle-cover edge [ 6 , n ! 2 ] -bipancyclic for n ⩾ 5 , and thus it is two-disjoint-cycle-cover vertex [ 6 , n ! 2 ] -bipancyclic for n ⩾ 5. Additionally, it is examined that S n is two-disjoint-cycle-cover [ 6 , n ! 2 ] -bipancyclic for n ⩾ 4. [ABSTRACT FROM AUTHOR]

Given a graph G , a subset of vertices is called a maximum dissociation set of G if it induces a subgraph with vertex degree at most 1, and the subset has maximum cardinality. The cardinality of a maximum dissociation set is called the dissociation number of G. The adjacency matrix and the degree diagonal matrix of G are denoted by A (G) and D (G) , respectively. In 2017, Nikiforov proposed the A α -matrix: A α (G) = α D (G) + (1 − α) A (G) , where α ∈ [ 0 , 1 ]. The largest eigenvalue of this novel matrix is called the A α -index of G. In this paper, we firstly determine the connected graph (resp. bipartite graph, tree) having the largest A α -index over all connected graphs (resp. bipartite graphs, trees) with fixed order and dissociation number. Secondly, we describe the structure of all the n -vertex graphs having the minimum A α -index with dissociation number τ , where τ ⩾ ⌈ 2 3 n ⌉. Finally, we identify all the connected n -vertex graphs with dissociation number τ ∈ { 2 , ⌈ 2 3 n ⌉ , n − 1 , n − 2 } having the minimum A α -index. [ABSTRACT FROM AUTHOR]

A bisection of a graph is a bipartition of its vertex set in which the two parts differ in size by at most 1, and its size is the number of edges which across the two parts. Let G be a graph with n vertices, m edges and degree sequence d 1 , d 2 , ... , d n . Motivated by a few classical results on Max-Cut of graphs, Lin and Zeng proved that if G is { C 4 , C 6 } -free and has a perfect matching, then G has a bisection of size at least m / 2 + Ω (∑ i = 1 n d i ) , and conjectured the same bound holds for C 4 -free graphs with perfect matchings. In this paper, we confirm the conjecture under the additional condition that G is C 5 -free. [ABSTRACT FROM AUTHOR]

For a graph G , let i k (G) be the number of independent sets of size k in G. The independence polynomial I (G ; x) = ∑ k ≥ 0 i k (G) x k has been the focus of considerable research. In this paper, using the coefficients of independence polynomials, we order graphs with some given parameters. We first determine the extremal graph whose all coefficients of I (G ; x) are the largest (respectively, smallest) among all connected graphs (respectively, bipartite graphs) with given vertex cover number. Then we also derive the extremal graph whose all coefficients of I (G ; x) are the largest among all connected graphs (respectively, bipartite graphs) with given vertex dominate number. [ABSTRACT FROM AUTHOR]

Nakajima's graded quiver varieties naturally appear in the study of bases of cluster algebras. One particular family of these varieties, namely the bipartite determinantal varieties, can be defined for any bipartite quiver and gives a vast generalization of classical determinantal varieties with broad applications to algebra, geometry, combinatorics, and statistics. The ideals that define bipartite determinantal varieties are called bipartite determinantal ideals. We provide an elementary method of proof showing that the natural generators of a bipartite determinantal ideal form a Gröbner basis, using an S-polynomial construction method that relies on the Leibniz formula for determinants. This method is developed from an idea by Narasimhan and Caniglia–Guccione–Guccione. As applications, we study the connection between double determinantal ideals (which are bipartite determinantal ideals of a quiver with two vertices) and tensors, and provide an interpretation of these ideals within the context of algebraic statistics. [ABSTRACT FROM AUTHOR]

Aiming at problems such as the "straggler effect" caused by resource heterogeneity in federated learning in edge computing environments, this paper proposed a match-based model offloading for edge federated learning (Fed-MBMO). This method collected performance analysis results of edge devices, divided devices into strong and weak clients, and considered the time proportion of the four phases of model training, weak clients saved the time of backpropagation on the feature layers by freezing part of the model, and offload the model to the strong client for additional training, finally, the strong clients' feature layers were then reconstructed with the weak clients' fully connected layers. In order to improve the efficiency of model off- loading, the offloading cost matrix is constructed by comprehensively considering the similarity of model feature layers and task completion time, and transform the problem into an iterative solution of the optimal matching problem based on bipartite graph, the proposed approach used a KM-based model offloading algorithm and further analyzed the time complexity of the Fed-MBMO algorithm. Experimental results show that in the case of extremely heterogeneous resources and datasets, this method can accelerate model convergence, and the model training time can be reduced by an average of 46. 65 percent, 12. 66 percent and 38.07 percent compared to FedAvg, FedUE and Aergia, respectively. The experimental results show that the Fed-MBMO algorithm can effectively solve the "straggler effect "problem and significantly improve the efficiency of federated learning. [ABSTRACT FROM AUTHOR]

We prove that in a connected graph, the distances between non-cut vertices are odd if and only if it is the line graph of a strong unique independence tree. We then show that any such tree can be inductively constructed from stars using a simple operation. Further, we study the connected graphs in which the distances between non-cut vertices are even (shortly, NCE-graphs). Our main results on NCE-graphs are the following: we give a criterion of NCE-graphs, show that any bipartite graph is an induced subgraph of an NCE-graph, characterize NCE-graphs with exactly two leaves, characterize graphs that can be subdivided to NCE-graphs, and provide a characterization for NCE-graphs which are maximal with respect to the edge addition operation. [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]

For a given graph H , its subdivisions carry the same topological structure. The existence of H -subdivisions within a graph G has deep connections with topological, structural and extremal properties of G. One prominent example of such a connection, due to Bollobás and Thomason and independently Komlós and Szemerédi, asserts that the average degree of G being d ensures a K Ω (d) -subdivision in G. Although this square-root bound is best possible, various results showed that much larger clique subdivisions can be found in a graph for many natural classes. We investigate the connection between crux, a notion capturing the essential order of a graph, and the existence of large clique subdivisions. This reveals the unifying cause underpinning all those improvements for various classes of graphs studied. Roughly speaking, when embedding subdivisions, natural space constraints arise; and such space constraints can be measured via crux. Our main result gives an asymptotically optimal bound on the size of a largest clique subdivision in a generic graph G , which is determined by both its average degree and its crux size. As corollaries, we obtain • a characterization of extremal graphs for which the square-root bound above is tight: they are essentially disjoint unions of graphs having crux size linear in d ; • a unifying approach to find a clique subdivision of almost optimal size in graphs which do not contain a fixed bipartite graph as a subgraph; • and that the clique subdivision size in random graphs G (n , p) witnesses a dichotomy: when p = ω (n − 1 / 2) , the barrier is the space, while when p = o (n − 1 / 2) , the bottleneck is the density. [ABSTRACT FROM AUTHOR]

An edge e of a matching covered graph G is removable if G−e is also matching covered. The notion of removable edge arises in connection with ear decompositions of matching covered graphs introduced by Lovász and Plummer. A nonbipartite matching covered graph G is a brick if it is free of nontrivial tight cuts. Carvalho, Lucchesi and Murty proved that every brick other than K4 and C6¯ has at least Δ−2 removable edges. A brick G is near‐bipartite if it has a pair of edges {e1,e2} such that G−{e1,e2} is a bipartite matching covered graph. In this paper, we show that in a near‐bipartite brick G with at least six vertices, every vertex of G, except at most six vertices of degree three contained in two disjoint triangles, is incident with at most two nonremovable edges; consequently, G has at least |V(G)|−62 removable edges. Moreover, all graphs attaining this lower bound are characterized. [ABSTRACT FROM AUTHOR]

For f:R2→R, let ΓR(f) be a two‐dimensional algebraically defined graph, that is, a bipartite graph where each partite set is a copy of R2 and two vertices (a,a2) and [x,x2] are adjacent if and only if a2+x2=f(a,x). It is known that ΓR(XY) has girth 6 and can be extended to the point‐line incidence graph of the classical real projective plane. However, it was unknown whether there exists f∈R[X,Y] such that ΓR(f) has girth 6 and is nonisomorphic to ΓR(XY). This paper answers this question affirmatively and thus provides a construction of a nonclassical real projective plane. This paper also studies the diameter and girth of ΓR(f) for families of bivariate functions f. [ABSTRACT FROM AUTHOR]

A matching in a graph is a set of pairwise nonadjacent edges. Denote by m (G , k) the number of matchings of cardinality k in a graph G. A quasi-order ⪯ is defined by G ⪯ H whenever m (G , k) ≤ m (H , k) holds for all k. Let BG 1 (n , γ) be the set of connected bipartite graphs with n vertices and γ cut vertices, and BG 2 (n , γ) be the set of connected bipartite graphs with n vertices and γ cut edges. We determine the greatest and least elements with respect to this quasi-order in BG 1 (n , γ) and the greatest element in BG 2 (n , γ) for all values of n and γ. As corollaries, we find that these graphs maximize (resp. minimize) the Hosoya index and the matching energy within the respective sets. [ABSTRACT FROM AUTHOR]

Consider a graph G = (V , E) and a function f : V → { 0 , 1 , 2 }. A vertex u with f (u) = 0 is defined as undefended by f if it lacks adjacency to any vertex with a positive f -value. The function f is said to be a weak Roman dominating function (WRD function) if, for every vertex u with f (u) = 0 , there exists a neighbor v of u with f (v) > 0 and a new function f ′ : V → { 0 , 1 , 2 } defined in the following way: f ′ (u) = 1 , f ′ (v) = f (v) − 1 , and f ′ (w) = f (w) , for all vertices w in V ∖ { u , v } ; so that no vertices are undefended by f ′. The total weight of f is equal to ∑ v ∈ V f (v) , and is denoted as w (f). The Weak Roman domination number denoted by γ r (G) , represents m i n { w (f) | f is a WRD function of G }. For a given graph G , the problem of finding a WRD function of weight γ r (G) is defined as the Minimum Weak Roman domination problem. The problem is already known to be NP-hard for bipartite and chordal graphs. In this paper, we further study the algorithmic complexity of the problem. We prove the NP-hardness of the problem for star convex bipartite graphs and comb convex bipartite graphs, which are subclasses of bipartite graphs. In addition, we show that for the bounded degree star convex bipartite graphs, the problem is efficiently solvable. We also prove the NP-hardness of the problem for split graphs, a subclass of chordal graphs. On the positive side, we present a polynomial-time algorithm to solve the problem for P 4 -sparse graphs. Further, we have presented some approximation results. [ABSTRACT FROM AUTHOR]

A connected matching in a graph G consists of a set of pairwise disjoint edges whose covered vertices induce a connected subgraph of G. While finding a connected matching of maximum cardinality is a well-solved problem, it is NP-hard to determine an optimal connected matching in an edge-weighted graph, even in the planar bipartite case. We present two mixed integer programming formulations and a sophisticated branch-and-cut scheme to find weighted connected matchings in general graphs. The formulations explore different polyhedra associated to this problem, including strong valid inequalities both from the matching polytope and from the connected subgraph polytope. We conjecture that one attains a tight approximation of the convex hull of connected matchings using our strongest formulation, and report encouraging computational results over DIMACS Implementation Challenge benchmark instances. The source code of the complete implementation is also made available. [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]

The median function is a location/consensus function that maps any profile π (a finite multiset of vertices) to the set of vertices that minimize the distance sum to vertices from π. The median function satisfies several simple axioms: Anonymity (A), Betweeness (B), and Consistency (C). McMorris, Mulder, Novick and Powers (2015) defined the ABC-problem for consensus functions on graphs as the problem of characterizing the graphs (called, ABC-graphs) for which the unique consensus function satisfying the axioms (A), (B), and (C) is the median function. In this paper, we show that modular graphs with G 2 -connected medians (in particular, bipartite Helly graphs) are ABC-graphs. On the other hand, the addition of some simple local axioms satisfied by the median function in all graphs (axioms (T), and (T 2)) enables us to show that all graphs with connected median (comprising Helly graphs, median graphs, basis graphs of matroids and even Δ -matroids) are ABCT-graphs and that benzenoid graphs are ABCT 2 -graphs. McMorris et al (2015) proved that the graphs satisfying the pairing property (called the intersecting-interval property in their paper) are ABC-graphs. We prove that graphs with the pairing property constitute a proper subclass of bipartite Helly graphs and we discuss the complexity status of the recognition problem of such graphs. [ABSTRACT FROM AUTHOR]

An outer-independent triple Roman dominating function (OI[3]RDF) on a graph G = (V,E) is function f : V →{0, 1, 2, 3, 4} having the property that (i) if f(v) = 0, then v must have either a neighbor assigned 4 or two neighbors one of which is assigned 3 and the other at least 2 or v has three neighbors all assigned 2; (ii) no two vertices assigned 0 are adjacent; (iii) if f(v) = 1, then v must have either a neighbor assigned at least 3 or two neighbors assigned 2; (iv) if f(v) = 2, then v must have one neighbor assigned at least 2. The weight of an OI[3]RDF is the sum of its function value over the whole set of vertices, and the outer-independent triple Roman domination number of G is the minimum weight of an OI[3]RDF on G. In this paper, we continue the study of outer-independent triple Roman domination number of graphs by first presenting two sharp lower bounds for the outer-independent triple Roman domination number of trees. Then we strengthen the NP-complete result of the outer-independent triple Roman domination problem for bipartite graphs by showing that the problem remains NP-complete for a subclass of bipartite graphs, namely tree convex bipartite graphs, where two special trees are considered. [ABSTRACT FROM AUTHOR]

ABSTRACT This study is dedicated to the fixed‐time (FDT) bipartite synchronization of stochastic multiplex signed networks via quantized generalized intermittent control (QGIC). Firstly, a multiplex network including signed graphs and stochastic disturbances is introduced. Secondly, a new lemma of FDT stability is established by using reduction to absurdity and mathematical induction. Thirdly, based on the proposed FDT stability and the stochastic analysis techniques, several sufficient conditions on FDT bipartite synchronization are derived by designing a novel QGIC strategy. Significantly, the designed controller is a unified form of periodic and aperiodic cases and is only activated in the work interval. At last, two numerical simulations are offered to validate the superiority and effectiveness of the theoretical findings. [ABSTRACT FROM AUTHOR]

The surge of graph neural networks has catalyzed significant advancements in recommendation systems by enabling more effective modeling of user-item interactions within undirected bipartite graphs. However, the proliferation of graph neural network architectures, coupled with the absence of standardized benchmarking frameworks, presents challenges in systematically evaluating and comparing different dynamic recommendation models. In response, we propose a comprehensive benchmarking study of bipartite graph neural network operators for recommendation systems using the PyTorch geometric library. Our contributions include the development of a flexible benchmarking framework encompassing data preprocessing, model training, and evaluation protocols, facilitating fair comparison across diverse dynamic recommendation scenarios. We rigorously assess the performance of various graph neural network models, ranging from traditional methods to state-of-the-art architectures, on the MovieLens100k dataset. Through insightful analysis of experimental results, we elucidate the strengths and weaknesses of different graph neural network operators and offer practical suggestions for model selection and configuration. Our work aims to foster transparency, reproducibility, and innovation in graph neural network-based dynamic recommendation systems, providing a valuable resource for researchers and practitioners in the field. [ABSTRACT FROM AUTHOR]

Zero forcing and maximum nullity are two important graph parameters which have been laboriously studied in order to aid in the resolution of the Inverse Eigenvalue problem. Motivated in part by an observation that the zero forcing number for the complement of a tree on n vertices is either n − 3 or n − 1 in one exceptional case, we consider the zero forcing number for the complement of more general graphs under certain conditions, particularly those that do not contain complete bipartite subgraphs. We also move well beyond trees and completely study all of the possible zero forcing numbers for the complements of unicyclic graphs and cactus graphs. Finally, we yield equality between the maximum nullity and zero forcing number of several families of graph complements considered. [ABSTRACT FROM AUTHOR]

The deployment of increasingly diverse services on edge devices is becoming increasingly prevalent. Efficiently deploying functionally heterogeneous services to resource heterogeneous edge nodes while achieving superior user experience is a challenge that every edge system must address. In this paper, we propose a container-node graph (CN-Graph)-based container optimal matching deployment algorithm, edge Kuhn-Munkres algorithm (EKM) based on container-node graph, designed for heterogeneous environment to optimize system performance. Initially, containers are categorized by functional labels, followed by construction of a CN-Graph model based on the relationship between containers and nodes. Finally, the container deployment problem is transformed into a weighted bipartite graph optimal matching problem. In comparison with the mainstream container deployment algorithms, Swarm, Kubernetes, and the recently emerged ECSched-dp algorithm, the EKM algorithm demonstrates the ability to effectively enhance the average runtime performance of containers to 3.74 times, 4.10 times, and 2.39 times, respectively. [ABSTRACT FROM AUTHOR]

Given a graph G without isolated vertices, a function f : V (G) → { 0 , 1 , 2 } is a covering total Italian dominating function if (i) the set of vertices labeled with 0 forms an independent set; (ii) every vertex labeled with 0 is adjacent to two vertices labeled with 1 or to one vertex labeled with 2; and (iii) the set of vertices labeled with 1 or 2 forms a total dominating set. The covering total Italian domination number of G is the smallest possible value of the sum ∑ v ∈ V (G) f (v) among all possible covering total Italian dominating functions f on V (G). The concepts above are introduced in this article, and the study of its combinatorial and computational properties is initiated. Specifically, we show several relationships between such parameter and other domination related parameters in graphs. We also prove the NP-completeness of the related decision problem for bipartite graphs, and present some approximation results on computing our parameter. In addition, we compute the exact value of the covering total Italian domination number of some graphs with emphasis on some Cartesian products. [ABSTRACT FROM AUTHOR]

In this paper we study the class of graphs G m , n that have the same degree sequence as two disjoint cliques K m and K n , as well as the class G ¯ m , n of the complements of such graphs. We establish various properties of G m , n and G ¯ m , n related to recognition, connectivity, diameter, bipartiteness, Hamiltonicity, and pancyclicity. We also show that several classical optimization problems on these graphs are NP-hard, while others can be solved efficiently. [ABSTRACT FROM AUTHOR]

Let D = (V , A) be a digraph of order n , S a subset of V of size k , where k is a positive integer and 2 ≤ k ≤ n. A directed cycle C of D is called a directed S -Steiner cycle (or, an S -cycle for short) if S ⊆ V (C). Steiner cycles have applications in the optimal design of reliable telecommunication and transportation networks. A pair of S -cycles is called internally disjoint if they have no common arc and the common vertex set of them is exactly S. Let κ S c (D) be the maximum number of pairwise internally disjoint S -cycles in D. The directed cycle k -connectivity of D is defined as κ k c (D) = min κ S c (D) ∣ S ⊆ V (D) , S = k , 2 ≤ k ≤ n. In this paper, we study the directed cycle k -connectivity of complete digraphs K ↔ n and complete regular bipartite digraphs K ↔ a , a. We give a sharp lower bound for κ k c ( K ↔ n) and determine the exact values for κ k c ( K ↔ n) when k ∈ { 2 , 3 , 4 , 6 }. We also determine the exact value of κ k c ( K ↔ a , a) for each 2 ≤ k ≤ n. [ABSTRACT FROM AUTHOR]

A graph G = ({ 1 , 2 , ... , n } , E) is 12- representable if there is a word w over { 1 , 2 , ... , n } such that two vertices i and j with i < j are adjacent if and only if every j occurs before every i in w. These graphs have been shown to be equivalent to the complements of simple-triangle graphs. This equivalence provides a characterization in terms of forbidden patterns in vertex orderings as well as a polynomial-time recognition algorithm. The class of 12-representable graphs was introduced by Jones et al. (2015) as a variant of word-representable graphs. A general research direction for word-representable graphs suggested by Kitaev and Lozin (2015) is to study graphs representable by some specific types of words. For instance, Gao, Kitaev, and Zhang (2017) and Mandelshtam (2019) investigated word-representable graphs defined by pattern-avoiding words. Following this research direction, this paper studies 12-representable graphs defined by words that avoid a pattern p. Such graphs are trivial when p is of length 2. When p = 111, 121, 231, and 321, the classes of such graphs are equivalent to well-known classes, such as trivially perfect graphs and bipartite permutation graphs. For the cases where p = 123, 132, and 211, this paper provides forbidden pattern characterizations. • Classes of graphs 12-representable by pattern-avoiding words are introduced. • Among such classes, those with patterns of length at most 3 are investigated. • Some classes are equivalent to well-known classes such as trivially perfect graphs. • Forbidden pattern characterizations are provided for other classes. [ABSTRACT FROM AUTHOR]

We consider one variant of stable assignment problems in a bipartite graph endowed with nonnegative capacities on the edges and quotas on the vertices. It can be viewed as a generalization of the stable allocation problem introduced by Baïou and Balinsky, which arises when strong linear orders of preferences on the vertices in the latter are replaced by weak ones. At the same time, our stability problem can be stated in the framework of a theory by Alkan and Gale on stable schedule matchings generated by choice functions of a wide scope. In our case, the choice functions are of a special, so-called mixed , type. The main content of this paper is devoted to a study of rotations in our mixed model, functions on the edges determining "elementary" transformations between close stable assignments. These look more sophisticated compared with rotations in the stable allocation problem (which are generated by simple cycles). We efficiently construct a poset of rotations and show that the stable assignments are in bijection with the so-called closed functions for this poset; this gives rise to a "compact" affine representation for the lattice of stable assignments and leads to an efficient method to find a stable assignment of minimum cost. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph where V and E are the vertex and edge sets, respectively. For two disjoint subsets A and B of V , we say A dominates B if every vertex of B is adjacent to at least one vertex of A. A vertex partition π = { V 1 , V 2 , ... , V k } of G is called a transitive partition of size k if V i dominates V j for all 1 ≤ i < j ≤ k. In this article, we study a variation of transitive partition, namely 2- transitive partition. For two disjoint subsets A and B of V , we say A 2- dominates B if every vertex of B is adjacent to at least two vertices of A. A vertex partition π = { V 1 , V 2 , ... , V k } of G is called a 2- transitive partition of size k if V i 2 -dominates V j for all 1 ≤ i < j ≤ k. The Maximum 2- Transitivity Problem is to find a 2 -transitive partition of a given graph with the maximum number of parts. We show that the decision version of this problem is NP-complete for chordal and bipartite graphs. On the positive side, we design three linear-time algorithms for solving Maximum 2- Transitivity Problem in trees, split, and bipartite chain graphs. [ABSTRACT FROM AUTHOR]

This paper studies the distributed bipartite state consensus tracking problem of discrete-time linear leader-following singular multi-agent systems (MASs). Compared with the traditional continuous-time linear dynamics, it is difficult to achieve the desired cooperative control of discrete-time counterpart since their stability regions are limited to the unit circle. In addition, in some practical scenarios, there are both cooperation and competition coexisting among followers. First, a new distributed state feedback control protocol is proposed based on the Gerschgorin circle theorem and the discrete algebraic Riccati equation. At the same time, by introducing the constant coupling gain associated with the system topology matrix, the global tracking error system can locate in the stable region of the unit circle. Under the structurally balanced condition of directed signed graph, it can be proved that all the agents of two opposite subgroups can achieve bipartite state tracking by Lyapunov stability theory and separation principle. Then, by using the cooperative–competitive interaction information of neighbours, a new distributed state observer is introduced to estimate the state of leader. Furthermore, when the states of followers are not known, an observer-based output feedback bipartite control protocol is proposed, which can also be applied to more general consensus control scenarios. Meanwhile, a bipartite state formation controller is given to achieve the formation control by making the followers to keep the desired relative positions with the leader. Finally, two simulation results are given to verify the feasibility and effectiveness of proposed algorithms. [ABSTRACT FROM AUTHOR]

This paper is concerned with the bipartite secure control issue for a class of discrete-time nonlinear multi-agent systems under a dynamic encryption–decryption approach. First, the coupling relationships between agents are portrayed through a signed graph topology containing the edges of positive and negative connection weights. Next, the information transmissions between agents and their neighbors are executed via a shared communication network. The dynamic encryption–decryption approach is implemented to transform original signals into ciphertexts. Under the assumption that the signed graph is structurally balanced, a signed-network-based bipartite secure controller is designed to achieve the desired state control for the nonlinear multi-agent system and sufficient conditions are obtained for the existence of the desired signed-network-based state controller. Furthermore, a precise definition of the minimum channel capacity is proposed to understand the factors affecting the minimum channel capacity. Finally, the effectiveness of the proposed approach is illustrated by two simulation examples. [ABSTRACT FROM AUTHOR]

In today's fast-evolving technological environment, ensuring confidentiality is of utmost importance. Cryptography stands as a critical discipline in safeguarding information from unauthorized access. It employs various encryption algorithms to secure data effectively. As digital threats evolve, there's a growing demand for unconventional encryption methods to counter traditional cyber-attacks. This paper introduces innovative encryption algorithms leveraging special graphs and public key cryptography techniques, enhancing security through modular arithmetic properties and enabling more robust communication safeguards. A partition V1, V2, . . ., Vk of the vertex set V is called a chromatic partition of G if each Vi, 1 = i = k is an independent set of G. The minimum order of a chromatic partition of G is called chromatic number X(G). A chromatic partition of G is called an ordered partition if |V1| = β0 and |Vi| = β0(V − ∪i j=1Vj). The order of a minimum ordered chromatic partition of G is called ordered chromatic number χ1(G). It is immediate that χ1(G) ≥ χ(G). In this paper we extend Nordhaus Gaddum results to ordered chromatic number. [ABSTRACT FROM AUTHOR]

We study the algebraic connectivity for several classes of random semi-regular graphs. For large random semi-regular bipartite graphs, we explicitly compute both their algebraic connectivity as well as the full spectrum distribution. For an integer d ∈ 3 , 7 , we find families of random semi-regular graphs that have higher algebraic connectivity than random d-regular graphs with the same number of vertices and edges. On the other hand, we show that regular graphs beat semi-regular graphs when d ≥ 8 . More generally, we study random semi-regular graphs whose average degree is d, not necessarily an integer. This provides a natural generalization of a d-regular graph in the case of a non-integer d . We characterize their algebraic connectivity in terms of a root of a certain sixth-degree polynomial. Finally, we construct a small-world-type network of an average degree of 2.5 with relatively high algebraic connectivity. We also propose some related open problems and conjectures. [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]

Solving maximum matching problems in bipartite graphs is critical in fields such as computational biology and social network analysis. This study introduces HybridGNN, a novel Graph Neural Network model designed to efficiently address complex matching problems at scale. HybridGNN leverages a combination of Graph Attention Networks (GATv2), Graph SAGE (SAGEConv), and Graph Isomorphism Networks (GIN) layers to enhance computational efficiency and model performance. Through extensive ablation experiments, we identify that while the SAGEConv layer demonstrates suboptimal performance in terms of accuracy and F1-score, configurations incorporating GATv2 and GIN layers show significant improvements. Specifically, in six-layer GNN architectures, the combinations of GATv2 and GIN layers with ratios of 4:2 and 5:1 yield superior accuracy and F1-score. Therefore, we name these GNN configurations HybridGNN1 and HybridGNN2. Additionally, techniques such as mixed precision training, gradient accumulation, and Jumping Knowledge networks are integrated to further optimize performance. Evaluations on an email communication dataset reveal that HybridGNNs outperform traditional algorithms such as the Hopcroft–Karp algorithm, the Hungarian algorithm, and the Blossom/Edmonds' algorithm, particularly for large and complex graphs. These findings highlight HybridGNN's robust capability to solve maximum matching problems in bipartite graphs, making it a powerful tool for analyzing large-scale and intricate graph data. Furthermore, our study aligns with the goals of the Symmetry and Asymmetry Study in Graph Theory special issue by exploring the role of symmetry in bipartite graph structures. By leveraging GNNs, we address the challenges related to symmetry and asymmetry in graph properties, thereby improving the reliability and fault tolerance of complex networks. [ABSTRACT FROM AUTHOR]

Personalized recommendation can recommend items of interest to different users and is widely used in the real world. Among them, graph collaborative filtering is a method of personalized recommendation. It can enrich the connection between users and items on the basis of collaborative filtering, to learn the embedded representation of nodes more accurately. Since graph collaborative filtering is based on bipartite graphs, few exciting graph collaborative methods consider the relationships between users (or items), the message between homogeneous nodes are diluted or ignored. Predicting and constructing the relationship between users (or items) has become a challenging. To solve this problem, we propose an enhanced sub-graph reconstruction graph neural network for recommendation (SRCF), using a heterogeneous graph neural network based encoder-decoder learn potential relationships between users (or items), and reconstruct sub-graphs based on those relationships. In the proposed model, the information of user and item sub-graphs is merged with the network of graph collaborative filtering, which enhances effective information transfer between homogeneous nodes, thereby improving the model performance. We have selected a number of data sets of different scenarios and different scales to comprehensively evaluate the performance of the model, and the experimental results confirmed the superiority of our model. [ABSTRACT FROM AUTHOR]

The paper examines domestic 'femicide' in Italy. Under an exploratory statistical approach, we investigated: (1) difficulties and strategies for reconstructing a historical dataset on family crimes for studies over time; (2) the main causes of family femicides; and (3) groups of actors driven by the same motivations interpreted as patterns of criminal behavior. First, we integrated and systematised data from official sources to guarantee comparison over time; second, we used Social Network Analysis properties to study the relationships between 'motivations' and 'victim-perpetrator'; and third, we applied and compared community detection algorithms to the linkages between 'actors' and 'motivations' to detect groups of criminal behavior. From 2015 to 2020 in Italy, the cohabitant was the major family murderer, but in 2020, passion motivation also surfaced. Mental problems connected to parents-children and cohabitants, jealousy of ex-partners or rivals, and economic issues for blood relations were observed in 2015. Psychopathologies and money characterised parents-children in 2020, while passion and disagreements caused cohabitants or ex-partners. [ABSTRACT FROM AUTHOR]

Host–parasite interactions are influenced by present and past eco‐evolutionary interactions and the local environment. An ecological community defines the potential host range of each parasite and the potential parasite diversity of each host species. Past and present processes translate potential to realised interaction niches of parasite and host species. Host–parasite interactions are antagonistic, which may slow the saturation of their interaction niches. Intervality, a property of bipartite networks, measures saturation of interaction niches. Intervality of a community increases as the interaction niches of species of one guild (e.g. hosts) become saturated for their interactions with another guild (e.g. parasites). Characteristics driving intervality in host and parasite communities are largely unknown, as well as the effect of environmental change on intervality of these communities. In our study, we assess if the characteristics 'phylogenetic relatedness' and 'overlap in ecological interactions' explain intervality of rodent host–helminth parasite communities. In addition, we contrast intervality of these communities from habitats that differ in their history of human‐driven modification. We performed the analyses for the interaction niches of both parasites and hosts, independently. Our results indicated that host and parasite communities were non‐interval or significantly less interval than expected by chance. Phylogenetic relatedness and overlap in ecological interactions did not explain the maximum values of intervality. We speculate that antagonistic coevolution in host–parasite communities may hinder communities to reach saturation, which would explain why it is difficult to find the characteristics that explain intervality of a community. Interestingly, intervality of the interaction niche of parasites (host range) increased with habitat modification (i.e. saturation increased), whereas intervality of the interaction niche of hosts (parasite diversity) decreased as habitat modification increased. These opposite trends suggest that interaction niches of parasites and hosts respond differently to habitat modification. [ABSTRACT FROM AUTHOR]

In this paper, the output feedback-based bipartite consensus problem for MASs of unstable heat equations is investigated. The interactions of participating individuals are cooperative and competitive on an undirected graph. In order to achieve accurate estimation of system state, a distributed state observer is proposed. By introducing a reversible transformation, the observer system is transformed into a new system, and the controller based on the new system states is designed, which guarantees the well-posedness and stability of the considered control system and the observer system due to the invertibility of the presented transformation. Similarly, the bipartite consensus is analysed and proved. Finally, the validity of the proposed method is verified by simulation examples. [ABSTRACT FROM AUTHOR]

A bipartite graph G(X, Y) is called a star-convex bipartite graph with convexity on X if there is an associated star T(X, F), such that for each vertex in Y, its neighborhood in X induces a subtree in T. A graph G is said to be a split graph if G can be partitioned into a clique (K) and an independent set (I). The objective of this study is twofold: (i) to strengthen the complexity results presented in Chen et al. (J Comb Optim 32(1):95–110, 2016) for the Hamiltonian cycle (HCYCLE), the Hamiltonian path (HPATH), and the Domination (DS) problems on star-convex bipartite graphs (ii) to reinforce the results of Müller (Discret Math 156(1–3):291–298, 1996) for HCYCLE, and HPATH on split graphs by introducing a convex ordering on one of the partitions (K or I). As part of our fine-grained analysis study with the diameter being the parameter, we first show that the diameter of star-convex bipartite graphs is at most six. Next, we observe that the reduction instances of Chen et al. (J Comb Optim 32(1):95–110, 2016) are star-convex bipartite graphs with at most diameter 4, and hence HCYCLE and HPATH are NP-complete on star-convex bipartite graphs with at most diameter 4. We strengthen this result and establish the following results on star-convex bipartite graphs: (i) HCYCLE is NP-complete for diameter 3, and polynomial-time solvable for diameters 2, 5, and 6 (a transformation in complexity: P to NPC to P) (ii) HPATH is polynomial-time solvable for diameter 2, and NP-Complete, otherwise (a dichotomy). Further, with convexity being the parameter, for split graphs with convexity on K (resp. I), we show that HCYCLE and HPATH are NP-complete on star-convex (resp. comb) split graphs with convexity on K (resp. I). Further, we show that HCYCLE is NP-complete on k 1 , r -free star-convex split graphs with convexity on I, r ≥ 6 . On the positive side, we show that for K 1 , 5 -free star-convex split graphs with convexity on I, HCYCLE is polynomial-time solvable. Thus, we establish a dichotomy for HCYCLE on star-convex split graphs with convexity on I. We further show that the dominating set problem (DS) and its variants (resp. Connected, Total, Outer-Connected, and Dominating biclique) are NP-complete on star-convex bipartite graphs with diameter 3 (resp. diameter 5, and diameter 6). On the parameterized complexity front, we prove that the parameterized version of the domination problem and its variants, with the parameter being the solution size, is not fixed-parameter tractable for star-convex bipartite graphs with diameter 3 (resp. diameter 5, and diameter 6), whereas it is fixed-parameter tractable when the parameter is the number of leaves in the associated star. Further, we show that for star-convex bipartite graphs with diameters 5, and 6, the domination problem and its variants cannot be approximated within (1 - ϵ) ln n unless NP ⊆ T I M E (2 n o (1) ) . [ABSTRACT FROM AUTHOR]

Let I be the edge ideal of a Cohen-Macaulay tree of dimension d over a polynomial ring S = k [ x 1 , ... , x d , y 1 , ... , y d ] . We prove that for all t ≥ 1 , depth (S / I t) = max { d − t + 1 , 1 }. [ABSTRACT FROM AUTHOR]

By a classical result of Brodmann, the function depthR/I^t is asymptotically a constant, i.e. there is a number s such that depthR/I^t = depthR/I^s for t > s. One calls the smallest number s with this property the index of depth stability of I and denotes it by dstab(I). This invariant remains mysterious till now. The main result of this paper gives an explicit formula for dstab(I) when I is an arbitrary ideal generated by squarefree monomials of degree 2. That is the first general case where one can characterize dstab(I) explicitly. The formula expresses dstab(I) in terms of the associated graph. The proof involves new techniques which relate different topics such as simplicial complexes, systems of linear inequalities, graph parallelizations, and ear decompositions. It provides an effective method for the study of powers of edge ideals. [ABSTRACT FROM AUTHOR]

Let (X,\tau) be a Polish space with Borel probability measure \mu, and G a locally finite one-ended Borel graph on X. We show that G admits a Borel one-ended spanning tree generically. If G is induced by a free Borel action of an amenable (resp., polynomial growth) group then we show the same result \mu-a.e. (resp., everywhere). Our results generalize recent work of Timár, as well as of Conley, Gaboriau, Marks, and Tucker-Drob, who proved this in the probability measure preserving setting. We apply our theorem to find Borel orientations in even-degree graphs and measurable and Baire measurable perfect matchings in regular bipartite graphs, refining theorems that were previously only known to hold for measure preserving graphs. In particular, we prove that bipartite one-ended d-regular Borel graphs admit Baire measurable perfect matchings. [ABSTRACT FROM AUTHOR]

We call a proper edge coloring of a graph G $G$ a B‐coloring if every 4‐cycle of G $G$ is colored with four different colors. Let qB(G) ${q}_{B}(G)$ denote the smallest number of colors needed for a B‐coloring of G $G$. Motivated by earlier papers on B‐colorings, here we consider qB(G) ${q}_{B}(G)$ for planar and outerplanar graphs in terms of the maximum degree Δ=Δ(G) ${\rm{\Delta }}={\rm{\Delta }}(G)$. We prove that qB(G)≤2Δ+8 ${q}_{B}(G)\le 2{\rm{\Delta }}+8$ for planar graphs, qB(G)≤2Δ ${q}_{B}(G)\le 2{\rm{\Delta }}$ for bipartite planar graphs, and qB(G)≤Δ+1 ${q}_{B}(G)\le {\rm{\Delta }}+1$ for outerplanar graphs with Δ≥4 ${\rm{\Delta }}\ge 4$. We conjecture that, for Δ ${\rm{\Delta }}$ sufficiently large, qB(G)≤2Δ(G) ${q}_{B}(G)\le 2{\rm{\Delta }}(G)$ for planar G $G$, and qB(G)≤Δ(G) ${q}_{B}(G)\le {\rm{\Delta }}(G)$ for outerplanar G $G$. [ABSTRACT FROM AUTHOR]

It is currently an unsolved problem to determine whether, for every 2-list assignment L of a ▵ -free planar graph G, there exists an independent set A L such that G [ V G \ A L ] is L-colorable. However, in this paper, we take a slightly different approach to the above problem. We prove the N P -completeness of the decision problem of determining an independent set A such that G [ V G \ A ] is 2-choosable for ▵ -free, 4-colorable graphs of diameter 3. Building upon this notion, we examine the computational complexity of two optimization problems: minimum near-3-choosability and minimum 2-choosable-edge-deletion. In the former problem, the goal is to find an independent set A of minimum size in a given graph G, such that the induced subgraph G [ V G \ A ] is 2-choosable. We establish that this problem is N P -hard to approximate within a factor of | V G | 1 - ϵ for any ϵ > 0 , for planar bipartite graphs of arbitrary large girth. On the other hand, the problem of minimum 2-choosable-edge-deletion involves determining an edge set F ⊆ E G of minimum cardinality such that the spanning subgraph G [ E G \ F ] is 2-choosable. We prove that this problem can be approximated within a factor of O (log | V G |) . [ABSTRACT FROM AUTHOR]

Let n1, n2, . . ., nk be integers and V1, V2, . . ., Vk be disjoint vertex sets with [Vi] = ni for each i = 1, 2, . . ., k. A k-partite k-uniform hypergraph on vertex classes V1, V2, . . ., Vk is defined to be the k-uniform hypergraph whose edge set consists of the k-element subsets S of V1 ∪ V2 ∪ ⋯ ∪ Vk such that [S ∩ Vi] = 1 for all i = 1, 2, . . ., k. We say that it is balanced if n1 = n2 = ⋯ = nk. In this paper, we give a distance spectral radius condition to guarantee the existence of perfect matching in k-partite k-uniform hypergraphs, this result generalize the result of Zhang and Lin [Perfect matching and distance spectral radius in graphs and bipartite graphs, Discrete Appl. Math., 304 (2021) 315-322]. [ABSTRACT FROM AUTHOR]