Search

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.

A graph is called equimatchable if all of its maximal matchings have the same size. Lesk et al. [Equi-matchable graphs, Graph Theory and Combinatorics (Academic Press, London, 1984) 239–254] has provided a characterization of equimatchable bipartite graphs. Motivated by the fact that this characterization is not structural, Frendrup et al. [A note on equimatchable graphs, Australas. J. Combin. 46 (2010) 185–190] has also provided a structural characterization for equimatchable graphs with girth at least five, in particular, a characterization for equimatchable bipartite graphs with girth at least six. In this paper, we extend the characterization of Frendrup by eliminating the girth condition. For an equimatchable graph, an edge is said to be a critical-edge if the graph obtained by the removal of this edge is not equimatchable. An equimatchable graph is called edge-critical, denoted by ECE, if every edge is critical. Noting that each ECE-graph can be obtained from some equimatchable graph by recursively removing non-critical edges, each equimatchable graph can also be constructed from some ECE-graph by joining some non-adjacent vertices. Our study reduces the characterization of equimatchable bipartite graphs to the characterization of bipartite ECE-graphs.

The α-Hermitian adjacency matrix Hα of a mixed graph X has been recently introduced. It is a generalization of the adjacency matrix of unoriented graphs. In this paper, we consider a special case of the complex number α. This enables us to define an incidence matrix of mixed graphs. Consequently, we define a generalization of line graphs as well as a generalization of the signless Laplacian adjacency matrix of graphs. We then study the spectral properties of the gamma-signless Laplacian adjacency matrix of a mixed graph. Lastly, we characterize when the signless Laplacian adjacency matrix of a mixed graph is singular and give lower and upper bounds of number of arcs and digons in terms of largest and lowest eigenvalue of the signless Laplacian adjacency matrix.

J. P. Hayes proposed a graph-based model of fault tolerant systems, which in a more abstract form corresponds to vertex and edge extensions of graphs. A graph $G^*$ is called a vertex $k$-extension of a graph $G$ if the graph $G$ is embedded in every graph obtained from $G^*$ by removing any $k$ vertices. If no proper part of the graph $G^*$ is a vertex $k$-extension of the graph $G$, then the extension $G^*$ is said to be irreducible. If a vertex $k$-extension has the minimum possible number of vertices and edges, then it is called minimal. The task of finding minimal extensions for an arbitrary graph is computationally difficult. Only for some classes of graphs, it was possible to find a partial or complete description of their minimal vertex extensions. In this paper, we propose a general scheme for constructing vertex 1- and 2-extensions for almost all bipartite graphs, including hypercubes. The hypercube is an interesting graph in terms of its properties and the possibility of using it as a topology of an interconnection network. The minimum vertex extensions for hypercubes are unknown. In practice, trivial 1-extensions are used, which are obtained by adding one vertex and connecting it to all the others. The irreducible 1-extension for the 16-vertex hypercube proposed in this paper contains one less edge than the trivial 1-extension. The article also determines the number of non-isomorphic extensions for each hypercube that can be constructed using the proposed schemes and proves the irreducibility of hypercube vertex 1-extensions.

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 (P6,C6)-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 (P6,C6)-free graphs that is symmetrical to the linear recognition algorithms of weak-bisplit graphs and star1,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.

For any simple connected graph G of order n, having eigen spectrum μ 1 ≥ μ 2 ≥ ⋯ ≥ μ n with middle eigenvalues μ H and μ L, where H = ⌊(n + 1)/2⌋ and L = ⌈(n + 1)/2⌉, the HOMO–LUMO gap is defined as as ΔG = μ H = μ L. In this article, a simple upper bound for the HOMO–LUMO gap corresponding to a special class of connected bipartite graphs is estimated. As an application, the upper bounds for the HOMO–LUMO gap of certain classes of nanotubes and nanotori are estimated.

The primary aim of the study aims to provide a solution for scheduling examinations for most of the universities and colleges across India which follow the Choice Based Credit System (CBCS) using a graph coloring algorithm. Nowadays, due to the flexibility of opting various subjects, and many students taking up different courses in their colleges and universities, it becomes difficult to schedule these examinations. Creating an examination schedule can be quite challenging and time-consuming for controlling the body of an examination. Our research work focuses on reducing the efforts for scheduling such examinations. With the knowledge of graph theory and graph traversing and coloring algorithms, our algorithm with the help of a few assumptions gives an efficient solution to the examination scheduling problem. A detailed correctness proof along with performance analysis has been done. The efficiency of our proposed algorithm is then compared to that of the coloring algorithm using backtracking.

For any S ⊂ ℤ we say that a graph G has the S-property if there exists an S-edge-weighting w : E(G) → S such that for any pair of adjacent vertices u, v we have ∑e∈E(v) w(e) ≠ ∑e∈E(u) w(e), where E(v) and E(u) are the sets of edges incident to v and u, respectively. This work focuses on {a, a + 2}-edge-weightings where a ∈ ℤ is odd. We show that a 2-connected bipartite graph has the {a, a + 2}-property if and only if it is not a so-called odd multi-cactus. In the case of trees, we show that only one case is pathological. That is, we show that all trees have the {a, a + 2}-property for odd a ≠ −1, while there is an easy characterization of trees without the {−1, 1}-property.

In 6G, one of the important application scenarios is ultra-massive machinetype communications, which is mainly oriented to the application scenarios of concurrent access of massive terminals such as the satellite Internet of Things.How to design an access mechanism that can meet the concurrent access service requirements of large-scale users in machine communication scenarios for the future 6G satellite communication network is an important problem to be solved.A random access protocol based on intra-frame interference cancellation was proposed.In this protocol, each access user who needs to transmit data sends multiple packet copies in one frame, and the receiver can successfully receive packets from multiple users in confl icting time slots by using interference cancellation algorithms in the frame.Compared with the traditional random access mechanism, this mechanism can greatly improve the throughput performance in the scenario of multi-user concurrent access.

We define the anti-communicability function for the nodes of a simple graph as the nondiagonal entries of exp (-A). We prove that it induces an embedding of the nodes into a Euclidean space. The anti-communicability angle is then defined as the angle spanned by the position vectors of the corresponding nodes in the anti-communicability Euclidean space. We prove analytically that in a given k-partite graph, the anti-communicability angle is larger than 90° for every pair of nodes in different partitions and smaller than 90° for those in the same partition. This angle is then used as a similarity metric to detect the “best” k-partitions in networks where certain level of edge frustration exists. We apply this method to detect the “best” k-partitions in 15 real-world networks, finding partitions with a very low level of “edge frustration”. Most of these partitions correspond to bipartitions but tri- and pentapartite structures of real-world networks are also reported.

The advancement in coloring schemes of graphs is expanding over time to solve emerging problems. Recently, a new form of coloring, namely P3-coloring, was introduced. A simple graph is called a P3-colorable graph if its vertices can be colored so that all the vertices in each P3 path of the graph have different colors; this is called the P3-coloring of the graph. The minimum number of colors required to form a P3-coloring of a graph is called the P3-chromatic number of the graph. The aim of this article is to determine the P3-chromatic number of different well-known classes of bipartite graphs such as complete bipartite graphs, tree graphs, grid graphs, and some special types of bipartite graphs. Moreover, we have also presented some algorithms to produce a P3-coloring of these classes with a minimum number of colors required.

This paper offers a bird’s eye perception of how bipartite graph modeling could help to comprehend the progression of Alzheimer Disease (AD). We will also discuss the role of the various software tools available in the literature to identify the bipartite structure in AD affected patient brain networks and a general procedure to generate a graph from the AD brain network. Further, as AD is a minacious disorder that leads to the progressive decline of memory and physical ability we resort to Computer-Aided Diagnosis. It has a vital part in the preliminary estimation and finding of AD. We propose an approach to become aware of AD particularly in its beginning phase by analyzing the measurable variations in the hippocampus, grey matter, cerebrospinal fluid and white matter of the brain from Magnetic resonance images. Hence an appropriate segmentation and categorization methods are projected to detect the presence of AD. The trials were carried out on Magnetic resonance images to distinguish from the section of interest. The effectiveness of the CAD system was experimentally evaluated from the images considered from publicly available databases. Obtained findings recommend that the established CAD system has boundless prospective and great guarantee for the prognosis of AD.

Nowadays, graph theory is one of the most exciting fields of mathematics due to the tremendous developments in modern technology, where it is used in many important applications. The orthogonal double cover (ODC) is a branch of graph theory and is considered as a special class of graph decomposition. In this paper, we decompose the complete bipartite graphs Kx,x by caterpillar graphs using the method of ODCs. The article also deals with constructing the ODCs of Kx,x by general symmetric starter vectors of caterpillar graphs such as stars–caterpillar, the disjoint copies of cycles–caterpillars, complete bipartite caterpillar graphs, and the disjoint copies of caterpillar paths. We decompose the complete bipartite graph by the complete bipartite subgraphs and by the disjoint copies of complete bipartite subgraphs using general symmetric starter vectors. The advantage of some of these new results is that they enable us to decompose the giant networks into large groups of small networks with the comprehensive coverage of all parts of the giant network by using the disjoint copies of symmetric starter subgraphs. The use case of applying the described theory for various applications is considered.

Consensus-based data aggregation in d-regular bipartite graphs poses a challenging task for the scientific community since some of these algorithms diverge in this critical graph topology. Nevertheless, one can see a lack of scientific studies dealing with this topic in the literature. Motivated by our recent research concerned with this issue, we provide a comparative study of frequently applied consensus algorithms for distributed averaging in d-regular bipartite graphs in this paper. More specifically, we examine the performance of these algorithms with bounded execution in this topology in order to identify which algorithm can achieve the consensus despite no reconfiguration and find the best-performing algorithm in these graphs. In the experimental part, we apply the number of iterations required for consensus to evaluate the performance of the algorithms in randomly generated regular bipartite graphs with various connectivities and for three configurations of the applied stopping criterion, allowing us to identify the optimal distributed consensus algorithm for this graph topology. Moreover, the obtained experimental results presented in this paper are compared to other scientific manuscripts where the analyzed algorithms are examined in non-regular non-bipartite topologies.

Let $G=(V,E)$ be a connected graph of order $n$. $S \subseteq V$ is an edge metric generator of $G$ if any pair of edges in $E$ can be distinguished by some element of $S$. The edge metric dimension $edim(G)$ of a graph $G$ is the least size of an edge metric generator of $G$. In this paper, we give the characterization of all connected bipartite graphs with $edim=n-2$, which partially answers an open problem of Zubrilina (2018). Furthermore, we also give a sufficient and necessary condition for $edim(G)=n-2$, where $G$ is a graph with maximum degree $n-1$. In addition, the relationship between the edge metric dimension and the clique number of a graph $G$ is investigated by construction.

A subset \(D\) of the vertex set \(V\) of a graph \(G\) is called an \([1,k]\)-dominating set if every vertex from \(V-D\) is adjacent to at least one vertex and at most \(k\) vertices of \(D\). A \([1,k]\)-dominating set with the minimum number of vertices is called a \(\gamma_{[1,k]}\)-set and the number of its vertices is the \([1,k]\)-domination number \(\gamma_{[1,k]}(G)\) of \(G\). In this short note we show that the decision problem whether \(\gamma_{[1,k]}(G)=n\) is an \(NP\)-hard problem, even for bipartite graphs. Also, a simple construction of a bipartite graph \(G\) of order \(n\) satisfying \(\gamma_{[1,k]}(G)=n\) is given for every integer \(n \geq (k+1)(2k+3)\).

Given two graphs G and H, the mapping of f:V(G)→V(H) is called a graph homomorphism from G to H if it maps the adjacent vertices of G to the adjacent vertices of H. For the graph G, a subset of vertices is called a dissociation set of G if it induces a subgraph of G containing no paths of order three, i.e., a subgraph of a maximum degree, which is at most one. Graph homomorphisms and dissociation sets are two generalizations of the concept of independent sets. In this paper, by utilizing an entropy approach, we provide upper bounds on the number of graph homomorphisms from the bipartite graph G to the graph H and the number of dissociation sets in a bipartite graph G.

In 2010, Vukičević introduced an new graph invariant, the inverse sum indeg index of a graph, which has been studied due to its wide range of applications. Let Bnd be the class of bipartite graphs of order n and diameter d. In this paper, we mainly characterize the bipartite graphs in Bnd with the maximal inverse sum indeg index. Bipartite graphs with the largest, second-largest, and smallest inverse sum indeg indexes are also completely characterized.

Composite events are sense maximizes collaboration through multiple sensors. Efficient matching of multi-modal sensing nodes in multi-composite events is always a thorny problem. In this paper, the composite event sensing model is first proposed, and then the collaborative-sense problem of multi-modal sensing nodes is translated into a binary matching problem. For these multi-class sensors and multi-class compound events scene, a pruning-grafting and parallel strategy be adopted, which can speed up the traversal speed and find the maximum matching edge quickly. For multi-nodes selection, the distance of the composite event constraints into binarily weighted matching. A collaborative-sense intelligent matching algorithm is suggested. It takes collaborative in various kinds of nodes matching combining with the distribution of the composite event itself around the nodes. Combined with the random distribution of various sensor nodes and composite events, the matching rate of some sensor nodes is sacrificed for the overall event efficiency. Compare to parallel algorithms, it has another effect on perceived efficiency. Finally, by comparing with other algorithms, CSSMA and other proposed algorithms have a certain advantage in the inclusive sense efficiency. In terms of composite events collaborative-sense, this work has nice theoretical significance and practical value.

Sina Weibo, a Twitter-like microblogging Website in China, has become the main source of different kinds of information, such as breaking news, social events, and products. There is great value to exploiting the actual interests and behaviors of users, which creates opportunity for better understanding of the information dissemination mechanisms on social network sites. In this paper, we focus our attention to characterizing user behaviors in tweeting, retweeting, and commenting on Sina Weibo. In particular, we built a Shenzhen Weibo community graph to analyze user behaviors, clustering the coefficients of the community graph and exploring the impact of user popularity on social network sites. Bipartite graphs and one-mode projections are used to analyze the similarity of retweeting and commenting activities, which reveal the weak correlations between these two behaviors. In addition, to characterize the user retweeting behaviors deeply, we also study the tweeting and retweeting behaviors in terms of the gender of users. We observe that females are more likely to retweet than males. This discovery is useful for improving the efficiency of message transmission. What is more, we introduce an information-theoretical measure based on the concept of entropy to analyze the temporal tweeting behaviors of users. Finally, we apply a clustering algorithm to divide users into different groups based on their tweeting behaviors, which can improve the design of plenty of applications, such as recommendation systems.news,

With users being exposed to the growing volume of online information, the recommendation system aiming at mining the important or interesting information is becoming a modern research topic. One approach of recommendation is to integrate the graph neural network with deep learning algorithms. However, some of them are not tailored for bipartite graphs, which is a unique type of heterogeneous graph having two entity types. Others, though customized, neglect the importance of implicit relation and content information. In this paper, we propose the attentive implicit relation recommendation incorporating content information (AIRC) framework that is designed for bipartite graphs based on the GC–MC algorithm. First, through reconstructing the bipartite graphs, we obtain the implicit relation graphs. Then we analyze the content information of users and items with a CNN process, so that each user and item has its feature-tailored embeddings. Besides, we expand the GC–MC algorithms by adding a graph attention mechanism layer, which handles the implicit relation graph by highlighting important features and neighbors. Therefore, our framework takes into consideration both the implicit relation and content information. Finally, we test our framework on Movielens dataset and the results show that our framework performs better than other state-of-art recommendation algorithms.

This paper describes the modeling of social networks subject to a recommendation. The Cold Start User-Item Model (CSUIM) of a bipartite graph is considered, which simulates bipartite graph growth based on several parameters. An algorithm is proposed to compute parameters of this model with desired properties. The primary desired property is that the generated graph has similar graph metrics. The next is a change in our graph growth process due to recommendations. The meaning of CSUI model parameters in the recommendation process is described. We make several simulations generating networks from the CSUI model to verify theoretical properties. Also, proposed methods are tested on real-life networks. We prove that the CSUIM model of bipartite graphs is very flexible and can be applied to many different problems. We also show that the parameters of this model can be easily obtained from an unknown bipartite graph.

We show that the problem of deciding whether the edge set of a bipartite graph can be partitioned into three matchings, of size k1, k2 and k3 is NP-complete, even if one of the matchings is required to be perfect. We also show that the problem of deciding whether the edge set of a simple graph contains a perfect matching and a disjoint matching of size k or not is NP-complete, already for bipartite graphs with maximum degree 3. It also follows from our construction that it is NP-complete to decide whether in a bipartite graph there is a perfect matching and a disjoint matching that covers all vertices whose degree is at least 2.

In this article, we discuss new characterizations of Cohen-Macaulay bipartite edge ideals. For arbitrary bipartite edge ideals I ( G ) , we also discuss methods to recognize regular elements on I ( G ) s for all s ≥ 1 in terms of the combinatorics of the graph G.

For many parallel and distributed systems, automatic data redistribution improves its locality and increases system performance for various computer problems and applications. In general, an array can be distributed to multiple processing systems by using regular or irregular distributions. Some data distribution adopts BLOCK, CYCLIC, or BLOCK-CYCLIC to specify data array decomposition and distribution. On the other hand, irregular distributions specify a different-size data array distribution according to user-defined commands or procedures. In this work, we propose three bipartite graph problems, including the “maximum edge coloring problem”, the “maximum degree edge coloring problem”, and the “cost-sharing maximum edge coloring problem” to formulate these kinds of distribution problems. Next, we propose an approximation algorithm with a ratio bound of two for the maximum edge coloring problem when the input graph is biplanar. Moreover, we also prove that the “cost-sharing maximum edge coloring problem” is an NP-complete problem even when the input graph is biplanar.

Let \(k \geq 0\) be an integer. A set \(S\) of vertices of a graph \(G=(V(G),E(G))\) is called a global offensive \(k\)-alliance if \(|N(v) \cap S| \geq |N(v) \cap S|+k\) for every \(v \in V(G)-S\), where \(0 \leq k \leq \Delta\) and \(\Delta\) is the maximum degree of \(G\). The global offensive \(k\)-alliance number \(\gamma^k_o(G)\) is the minimum cardinality of a global offensive \(k\)-alliance in \(G\). We show that for every bipartite graph \(G\) and every integer \(k \geq 2\), \(\gamma^k_o(G) \leq \frac{n(G)+|L_k(G)|}{2}\), where \(L_k(G)\) is the set of vertices of degree at most \(k-1\). Moreover, extremal trees attaining this upper bound are characterized.

It is well-known that the different products of graphs are some of the more symmetric classes of graphs. Since we are interested in hyperbolicity, it is interesting to study this property in products of graphs. Some previous works characterize the hyperbolicity of several types of product graphs (Cartesian, strong, join, corona and lexicographic products). However, the problem with the direct product is more complicated. The symmetry of this product allows us to prove that, if the direct product G1×G2 is hyperbolic, then one factor is bounded and the other one is hyperbolic. Besides, we prove that this necessary condition is also sufficient in many cases. In other cases, we find (not so simple) characterizations of hyperbolic direct products. Furthermore, we obtain good bounds, and even formulas in many cases, for the hyperbolicity constant of the direct product of some important graphs (as products of path, cycle and even general bipartite graphs).

In the Vertex Cover Reconfiguration (VCR) problem, given a graph G, positive integers k and ℓ and two vertex covers S and T of G of size at most k, we determine whether S can be transformed into T by a sequence of at most ℓ vertex additions or removals such that every operation results in a vertex cover of size at most k. Motivated by results establishing the W [ 1 ] -hardness of VCR when parameterized by ℓ, we delineate the complexity of the problem restricted to various graph classes. In particular, we show that VCR remains W [ 1 ] -hard on bipartite graphs, is NP -hard, but fixed-parameter tractable on (regular) graphs of bounded degree and more generally on nowhere dense graphs and is solvable in polynomial time on trees and (with some additional restrictions) on cactus graphs.

Let \(G=(X,Y,E)\) be a balanced \(2\)-connected bipartite graph and \(S \subset V(G)\). We will say that \(S\) is cyclable in \(G\) if all vertices of \(S\) belong to a common cycle in \(G\). We give sufficient degree conditions in a balanced bipartite graph \(G\) and a subset \(S \subset V(G)\) for the cyclability of the set \(S\).

Graph Theory

We introduce an axiom system for a collection of matchings that describes the triangulation of product of simplices.

Let G be a connected bipartite graph with bipartition (X,Y) such that |X|≥|Y|(≥2), n=|X| and m=|Y|. Suppose, for all vertices x∈X and y∈Y, dist(x,y)=3 implies d(x)+d(y)≥n+1. Then G contains a cycle of length 2m. In particular, if m=n, then G is hamiltomian.