Search

This paper addresses the pressing need for effective k-tips decomposition in dynamic bipartite graphs, a crucial aspect of real-time applications that analyze and mine binary relationship patterns. Recognizing the dynamic nature of these graphs, our study is the first to provide a solution for k-tips decomposition in such evolving environments. We introduce a pioneering projection-based algorithm, coupled with advanced incremental maintenance strategies for edge modifications, tailored specifically for dynamic graphs. This novel approach not only fills a significant gap in the analysis of dynamic bipartite graphs but also substantially enhances the accuracy and timeliness of data-driven decisions in critical areas like public health. Our contributions set a new benchmark in the field, paving the way for more nuanced and responsive analyses in various domains reliant on dynamic data interpretation.

We give an example of two non isomorphic coordinate rings of a special kind of convex polyominoes whose Cohen–Macaulay types are generalized Fuss–Catalan numbers. We further provide a determinantal formula for these numbers.

In this paper, we study the problem of maximal biclique enumeration on large signed bipartite graphs. Given a signed bipartite graph $G=(U,V,E,s)$G=(U,V,E,s), a parameter $\theta \in [0.5, 1.0]$θ∈[0.5,1.0], our goal is to efficiently enumerate all maximal $\theta$θ-bicliques in $G$G, where a maximal $\theta$θ-biclique $B(L,R)$B(L,R) is a complete subgraph of $G$G with (1) the proportion of positive neighbors for each vertex in $B$B is at least $\theta$θ, and (2) $B$B is not contained in another biclique $B^{\prime }$B', while $B^{\prime }$B' also satisfies (1). This problem has many applications, such as biclustering for genes, recommendation of similar groups, collaboration in communities, etc. However, it is computationally challenging due to its #P-completeness. Besides, we prove that even determining the maximality of a $\theta$θ-biclique is NP-hard. To the best of our knowledge, there is no efficient and scalable solution to this problem in the literature. In this paper, we first propose a branch-and-bound framework, namely ${\sf MSiBE}$MSiBE, which enumerates all maximal $\theta$θ-bicliques in a depth-first manner. Then, we develop three effective optimizations to improve the performance of ${\sf MSiBE}$MSiBE. (1) The local information of each search space is utilized to enhance the pruning capacity. (2) When expanding the partial biclique, we always focus on the side with fewer candidates first, by which fruitless search branches can be skipped early. (3) We implement ${\sf MSiBE}$MSiBE with efficient array reordering techniques and set intersection strategy. To further accelerate the computation, we introduce useful graph reduction techniques. Comprehensive performance studies on 10 real datasets demonstrate that our proposals can significantly outperform the baseline methods by up to 3 orders of magnitude.

We characterize the bipartite graphs that minimize the (first degree-based) entropy among all bipartite graphs of given size. For bipartite graphs given size and (upper bound on the) order, we give a lower bound for this entropy. The extremal graphs turn out to be complete bipartite graphs, or nearly complete bipartite. Here we make use of an equivalent representation of bipartite graphs by means of Young diagrams, which make it easier to compare the entropy of related graphs. We conclude that the general characterization of the extremal graphs is a difficult problem, due to its connections with number theory. However, it is easier to identify them for particular values of the order n and size m because we have narrowed down the possible extremal graphs. We indicate that some of our ideas extend to other degree-based topological indices as well. • Characterize the bipartite graphs that minimize the first-degree based entropy given the size or both the size and the order. • Prove that the extremal graphs turn out to be complete bipartite graphs, or nearly complete bipartite. • Make use of an equivalent representation of bipartite graphs by means of Young diagrams. • Extend our ideas to some degree-based topological indices. [ABSTRACT FROM AUTHOR]

Many real applications can be modeled using bipartite graphs, such as users vs. files in a P2P system, traders vs. stocks in a financial trading system, conferences vs. authors in a scientific publication network, and so on. We introduce two operations on bipartite graphs: 1) identifying similar nodes (relevance search), and 2) finding nodes connecting irrelevant nodes (anomaly detection). And we propose algorithms to compute the relevance score for each node using random walk with restarts and graph partitioning; we also propose algorithms to identify anomalies, using relevance scores. We evaluate the quality of relevance search based on semantics of the datasets, and we also measure the performance of the anomaly detection algorithm with manually injected anomalies. Both effectiveness and efficiency of the methods are confirmed by experiments on several real datasets.

Finding bicliques is a fundamental problem in bipartite graph analysis, and can find numerous applications. However, previous studies only focus on unsigned bipartite graphs. Signed information, such as friend and enemy, naturally exists in real-world networks. It is critical to leverage signed information to better characterize biclique. To fill this gap, we propose a novel biclique model, named balanced signed biclique, by leveraging the property of balance theory. Specifically, given a signed bipartite graph $G$G and two positive integers $\tau _{U}, \tau _{V}$τU,τV, a subgraph $S=(U_{S},V_{S},E_{S})$S=(US,VS,ES) of $G$G is a balanced signed biclique if $i)$i) $S$S is a biclique without any unstable motif, i.e., unbalanced butterfly, and $ii)$ii) $|U_{S}| \geq \tau _{U}$|US|≥τU and $|V_{S}| \geq \tau _{V}$|VS|≥τV. In this paper, we propose and investigate two important problems, i.e., maximal balanced signed biclique enumeration and maximum balanced signed biclique identification. Due to the unique features of signed bipartite graphs, the previous works cannot be applied to our problems directly. For the enumeration task, to construct a reasonable baseline, we extend the existing biclique enumeration framework for unsigned bipartite graphs and integrate the developed balanced bipartite graph property. To scale for large networks, optimized strategies are proposed to overcome the three limitations in the baseline method. For the identification task, we first propose a baseline method by leveraging the proposed enumeration framework. Moreover, employing novel optimizations, an anchor balanced bipartite graph based search framework is introduced to accelerate the search. Finally, extensive experiments are conducted on 8 real-world datasets to demonstrate the efficiency and effectiveness of the proposed techniques and model.

In this article, we propose the $(\alpha,\beta,\eta)$(α,β,η)-core model, which is the first cohesive subgraph model on uncertain bipartite graphs. To capture the uncertainty of relationships/edges, $\eta$η-degree is adopted to measure the vertex engagement level, which is the largest integer $k$k such that the probability of a vertex having at least $k$k neighbors is not less than $\eta$η. Given degree constraints $\alpha$α and $\beta$β, and a probability threshold $\eta$η, the $(\alpha,\beta,\eta)$(α,β,η)-core requires that each vertex on the upper or lower level have $\eta$η-degree no less than $\alpha$α or $\beta$β, respectively. An $(\alpha,\beta,\eta)$(α,β,η)-core can be obtained by iteratively removing the vertices with $\eta$η-degrees below the degree constraints. Apart from the online computation algorithm, we propose a probability-aware index to strike a balance between time and space costs. To efficiently build such an index, we design a top-down index construction algorithm to allow computation sharing. Then, we show how to parallelize our query algorithms and index construction algorithms. In addition, we study community search on uncertain bipartite graphs by adopting the $(\alpha,\beta,\eta)$(α,β,η)-core model. Extensive experiments are conducted on 13 datasets to validate the efficiency and effectiveness of our proposed techniques.

In this article, we study the problem of maximal biclique enumeration on large uncertain bipartite graphs. Given an uncertain bipartite graph $\mathcal {G}=(U,V,E,p)$G=(U,V,E,p), a probability threshold $\tau$τ, and two size constraints $\alpha$α and $\beta$β, we aim to efficiently enumerate all maximal $\tau$τ-bicliques in $\mathcal {G}$G, where a maximal $\tau$τ-biclique $B(L,R)$B(L,R) is a complete subgraph of $\mathcal {G}$G with (1) the probability of $B$B is no less than $\tau$τ, (2) $|L| \geq \alpha$|L|≥α and $|R| \geq \beta$|R|≥β, and (3) $B$B is a maximal complete subgraph satisfying (1) and (2). This problem has many applications, such as biclustering of gene expression data, fraud detection, similar group identification, etc. Despite the wide range of applications, to the best of our knowledge, we note that there are no efficient and scalable solutions to this problem in the literature. This problem is computationally challenging due to its #P-completeness. In this article, we propose a competitive branch-and-bound method, namely ${\sf MBEN}$MBEN, which explores the search space in a depth-first manner with a variety of pruning techniques. To improve the performance of ${\sf MBEN}$MBEN, we propose several novel and efficient search processing optimizations. First, we always select the side with fewer candidates to expand the search space. With this search strategy, we have a chance to prune the fruitless branches early. Second, we devise an advanced pruning technique by considering the size pruning and probability pruning at the same time to boost the pruning capacity. Last, we implement ${\sf MBEN}$MBEN with pre-allocated arrays and pointer maintaining techniques such that the frequent work sets creating operations can be substituted by array element switching operations. In addition, we introduce useful graph reduction techniques to further accelerate the computation. Comprehensive performance studies on 10 real datasets demonstrate that our proposals can significantly outperform the baseline methods by more than two orders of magnitude.

A matching in a bipartite graph with parts X and Y is called envy-free, if no unmatched vertex in X is a adjacent to a matched vertex in Y. Every perfect matching is envy-free, but envy-free matchings exist even when perfect matchings do not. We prove that every bipartite graph has a unique partition such that all envy-free matchings are contained in one of the partition sets. Using this structural theorem, we provide a polynomial-time algorithm for finding an envy-free matching of maximum cardinality. For edge-weighted bipartite graphs, we provide a polynomial-time algorithm for finding a maximum-cardinality envy-free matching of minimum total weight. We show how envy-free matchings can be used in various fair division problems with either continuous resources ("cakes") or discrete ones. In particular, we propose a symmetric algorithm for proportional cake-cutting, an algorithm for 1 -out-of- (2 n - 2) maximin-share allocation of discrete goods, and an algorithm for 1 -out-of- ⌊ 2 n / 3 ⌋ maximin-share allocation of discrete bads among n agents. [ABSTRACT FROM AUTHOR]

Clustering bipartite graphs is a fundamental task in network analysis. In the high-dimensional regime where the number of rows $n_{1}$and the number of columns $n_{2}$of the associated adjacency matrix are of different order, the existing methods derived from the ones used for symmetric graphs can come with sub-optimal guarantees. Due to increasing number of applications for bipartite graphs in the high-dimensional regime, it is of fundamental importance to design optimal algorithms for this setting. The recent work of Ndaoud et al. (2022, IEEE Trans. Inf. Theory, 68, 1960–1975) improves the existing upper-bound for the misclustering rate in the special case where the columns (resp. rows) can be partitioned into $L = 2$(resp. $K = 2$) communities. Unfortunately, their algorithm cannot be extended to the more general setting where $K \neq L \geq 2$. We overcome this limitation by introducing a new algorithm based on the power method. We derive conditions for exact recovery in the general setting where $K \neq L \geq 2$, and show that it recovers the result in Ndaoud et al. (2022, IEEE Trans. Inf. Theory, 68, 1960–1975). We also derive a minimax lower bound on the misclustering error when $K=L$under a symmetric version of our model, which matches the corresponding upper bound up to a factor depending on $K$.

Bipartite graphs are widely used to capture the relationships between two types of entities. In bipartite graph analysis, finding the maximum balanced biclique (MBB) is an important problem with numerous applications. A biclique is balanced if its two disjoint vertex sets are of equal size. However, in real-world scenarios, each vertex is associated with a weight to denote its properties, such as influence, i.e., weighted bipartite graph. For weighted bipartite graphs, the previous studies for MBB are no longer applicable due to the ignorance of weight. To fill the gap, in this paper, we propose a reasonable definition of “balance” by restricting the weight difference between two sides of a biclique within $k$k. Given a weighted bipartite graph $G$G and a constraint $k$k, we aim to find the maximum $k$k-balanced biclique (Max $k$k BB) with the maximum weight. To address the problem, we first propose an approach based on biclique enumeration on single side of $G$G following the Branch-and-Bound framework. To improve the performance, we further devise three optimization strategies to prune invalid search branches. Moreover, we utilize graph reduction strategy to reduce the redundant search space. Extensive experiments are conducted on 12 real bipartite datasets to demonstrate the efficiency, effectiveness and scalability of our proposed algorithms. The experimental results show that our algorithms can address MBB detection problem efficiently, and the case study demonstrates the effectiveness of our model compared with MBB model.

There are extensive studies focusing on the application scenario that all the bipartite cohesive subgraphs need to be discovered in a bipartite graph. However, we observe that, for some applications, one is interested in finding bipartite cohesive subgraphs containing a specific vertex. In this paper, we study a new query-dependent bipartite cohesive subgraph search problem based on $k$k-wing model, named as personalized $k$k-wing search problem. We study the $k$k-wing equivalence relationship to summarize the edges of a bipartite graph $G$G into groups. Therefore, all the edges of $G$G are segregated into different groups, i.e., $k$k-wing equivalence class, forming an efficient and wing number conserving index called EquiWing-Graph. Further, we propose a more compact index, EquiWing-Tree, which is achieved by using our proposed $k$k-butterfly loose approach and discovered hierarchy properties. These indices are used to expedite the personalized $k$k-wing search with a non-repetitive access to $G$G, which leads to linear algorithms for searching the personalized $k$k-wing. Moreover, we conduct a thorough study on the maintenance of the proposed indices for evolving bipartite graphs. We discover novel properties that help us localize the scope of the maintenance at a low cost. By exploiting the discoveries, we propose novel algorithms for maintaining the two indices, which substantially reduces the cost of maintenance. We perform extensive experimental studies in real-world graphs to validate the efficiency and effectiveness of EquiWing-Graph and EquiWing-Tree compared to the baseline.

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.

Tip decomposition has a pivotal role in mining cohesive subgraphs in bipartite graphs by computing the tip number of each vertex in accordance with the non-trivial motif butterfly ((2,2)-biclique). It has been a popular research topic with applications in document clustering, spam group detection, and analysis of affiliation networks. In such applications, the graphs are not only large, but they evolve quickly with new edges being continuously added/deleted. While existing centralized techniques could solve the tip decomposition problem for static bipartite graphs, they are not efficient for maintaining the tip numbers of vertices on large-scale graphs. In this paper, we study butterfly analysis problems on bipartite graphs in a distributed environment with the vertex-centric model. We first extend a centralized butterfly counting algorithm to a distributed version, called DBCA. An ingenious message aggregation strategy is designed to reduce massive redundant messaging and avoid the memory overflow problem while processing large-scale graphs. Based on the results of DBCA, we develop a distributed tip decomposition algorithm (DTDA) to get the tip number of each vertex in parallel. Finally, to maintain the tip numbers of vertices efficiently while graphs evolve over time, we explore a distributed tip maintenance algorithm (DTMA) along with a novel task-split strategy. Specifically, for an updated edge (insertion/deletion), several sub-tasks will be generated in line with the topology structure of the original bipartite graph. To our best knowledge, this is the first study to process the butterfly analysis problems in a distributed environment. In addition, comprehensive experiments have been conducted on real-world bipartite graphs. The experiment results demonstrate that our proposed algorithms are efficient and scalable.

AbstractFor an ordered subset W={w1,w2,…,wk}of vertices and a vertex vin a connected graph G, the ordered k-vector r(v|W)=(d(v,w1),d(v,w2),…,d(v,wk))is called the representation of vwith respect to W, where d(v,wi)is the distance between vand wi, for 1≤i≤k. The set Wis called a resolving setof Gif r(u|W)≠r(v|W), for every pair u,v∈V(G). The minimum positive integer kfor which Ghas a resolving set of cardinality kis the metric dimension of G, denoted as dim(G). A resolving set of Gof cardinality dim(G) is a metric basis of G. For a bipartite graph G, projection is defined as a graph with the vertices of one of the partite sets, where two vertices are adjacent if they have at least one common neighbor in the other partite set. In this paper, we investigate the relation between the metric dimension of a bipartite graph and its projections. Furthermore, we present some realization results for the bounds on the metric dimension of a bipartite graph.

Given a bipartite graph, the maximum edge biclique problem (${{\sf MEB}}$MEB) aims to find a biclique with the largest number of edges. ${{\sf MEB}}$MEB is a fundamental problem with many real applications, such as community analysis, E-commerce services and bioinformatics. However, in some scenarios, the weight of an edge reflects valuable and important information on the relationship between two entities. Motivated by this, in this paper, we investigate the problem of maximum edge-weighted biclique search (${{\sf MEWB}}$MEWB), which finds a biclique with the largest total weight of edges in a weighted bipartite graph. ${{\sf MEWB}}$MEWB has many real applications, including item recommendation, fraud detection, gene clustering, etc. Although we show that ${{\sf MEWB}}$MEWB can be resolved by adapting the search algorithm designed for ${{\sf MEB}}$MEB, the performance of this method is yet unsatisfactory. To improve the computation efficiency, two optimizations in terms of upper bound and search order are proposed. For the upper bound, we consider the degree distribution for vertices in the candidate set, and thus have a chance to discard a few edges to tighten the upper bound. For search order, we theoretically show that a vertex order generating the most similar search depth on vertices can achieve the least time cost for ${{\sf MEWB}}$MEWB. Guided by this fact, we propose the global summation vertex order. To further accelerate the computation, we extend our approach to a parallel environment, and develop a heuristic approach to deal with large-scale graphs by slightly sacrificing the answer quality. Extensive performance studies conducted on real datasets demonstrate that our proposals can significantly outperform the baseline method by up to two orders of magnitude. Besides, our heuristic approach gives the optimal result on 8 out of 10 real datasets, while achieving more than an order of magnitude of speed-up.

Bipartite graphs are widely used to model relationships between two types of entities. Community search retrieves densely connected subgraphs containing a query vertex, which has been extensively studied on unipartite graphs. However, it remains largely unexplored on bipartite graphs. Moreover, all existing cohesive subgraph models on bipartite graphs only measure the structure cohesiveness while overlooking the edge weight. In this paper, we study the significant ($\alpha$α, $\beta$β)-community search problem on weighted bipartite graphs. Given a query vertex $q$q, we aim to find the significant ($\alpha$α, $\beta$β)-community $\mathcal {R}$R of $q$q which adopts ($\alpha$α, $\beta$β)-core to characterize the engagement level of vertices, and maximizes the minimum edge weight (significance) within $\mathcal {R}$R. To support fast retrieval of $\mathcal {R}$R, we first obtain the maximal connected subgraph of ($\alpha$α, $\beta$β)-core containing $q$q (the ($\alpha$α, $\beta$β)-community), and the search space is limited to this subgraph with a much smaller size than the original graph. A novel index structure is presented to support retrieving the ($\alpha$α, $\beta$β)-community in optimal time. Efficient index maintenance techniques are also proposed to handle dynamic graphs. To further obtain $\mathcal {R}$R, we develop peeling and expansion algorithms. The experimental results on real graphs validate the effectiveness and efficiency of our proposed techniques.

Bipartite graphs have been widely adopted in applications such as e-healthcare and recommendation systems thanks to their ability to model various real-world relationships. Meanwhile, $(\alpha,\beta)$(α,β)-core query services over bipartite graphs are generally recognized as a promising approach for finding communities, i.e., sets of closely related vertices, in a bipartite graph. As the bipartite graph grows, the service providers tend to outsource the services to the cloud for flexible and highly reliable computational resources. However, since the cloud is not fully trustable, there are privacy concerns related to the dataset, query requests, and results. Although many schemes have been proposed for privacy-preserving queries over graphs, they cannot be directly adopted to handle accurate $(\alpha,\beta)$(α,β)-core queries over bipartite graphs. Aiming at the challenges, under the two-server setting, this paper constructs two privacy-preserving schemes with different levels of security to handle $(\alpha,\beta)$(α,β)-core queries over the bipartite graph. Specifically, in the proposed schemes, a graph is represented as an index containing an edge table and a node table and further encrypted by a symmetric homomorphic encryption scheme, and then the two servers securely traverse the index. Detailed security analysis shows that both schemes can achieve access pattern privacy, while the security-enhanced one can further protect the structure privacy of the query requests and results. In addition, extensive performance evaluations are conducted, and the results also indicate our proposed schemes are computationally efficient.

We propose a novel cohesive subgraph model called τ -strengthened (α , β) -core (denoted as (α , β) τ -core), which is the first to consider both tie strength and vertex engagement on bipartite graphs. An edge is a strong tie if contained in at least τ butterflies (2 × 2 -bicliques). (α , β) τ -core requires each vertex on the upper or lower level to have at least α or β strong ties, given strength level τ. To retrieve the vertices of (α , β) τ -core optimally, we construct index I α , β , τ to store all (α , β) τ -cores. Effective optimization techniques are proposed to improve index construction. To make our idea practical on large graphs, we propose 2D-indexes I α , β , I β , τ , and I α , τ that selectively store the vertices of (α , β) τ -core for some α , β , and τ. The 2D-indexes are more space-efficient and require less construction time, each of which can support (α , β) τ -core queries. As query efficiency depends on input parameters and the choice of 2D-index, we propose a learning-based hybrid computation paradigm by training a feed-forward neural network to predict the optimal choice of 2D-index that minimizes the query time. Extensive experiments show that (1) (α , β) τ -core is an effective model capturing unique and important cohesive subgraphs; (2) the proposed techniques significantly improve the efficiency of index construction and query processing. [ABSTRACT FROM AUTHOR]

A chain bipartite graph is a graph whose graph vertices can be partitioned into ndisjoint sets so that no two vertices within the same set are adjacent and only between any two sets edges are connected. Also, it is known by clustered bipartite graph. In this paper it is proved that chain bipartite graph satisfies graceful and α-labeling. Graceful labeling proves the uniqueness between and within clusters and improves in the distributed computing techniques to the solution of computationally intensive applications across networks of computers.

This paper introduces the signed graph into fractional-order coupled neural networks (FCNNs) and the bipartite synchronization is investigated for leaderless FCNNs. Instead of formulating leader's state or isolated node's state as the synchronization reference target, the bipartite synchronization of leaderless FCNNs is discussed by developing a direct error approach. First, an important fractional-order inequality is rigorously proved by contradiction. By virtue of fractional-order inequality, gauge transformation and several analytical tools, the criteria of bipartite leaderless synchronization are obtained for FCNNs with heterogeneous and homogeneous coupling weights. Specially, for the two types coupling weights, the adaptive pinning schemes are adopted which just rely on partial network information based on the spanning tree and connected dominating set, respectively. Eventually, the theoretical analysis is verified by two numerical simulations. [ABSTRACT FROM AUTHOR]

Co-clustering aims to explore coherent patterns by simultaneously clustering samples and features of data. Several co-clustering methods have been proposed in the past decades. However, in real-world applications, datasets are often with multiple modalities or composed of multiple representations (i.e., views), which provide different yet complementary information. Hence, it is essential to develop multi-view co-clustering models to solve the multi-view application problems. In this paper, a novel multi-view co-clustering method based on bipartite graphs is proposed. To make use of the duality between samples and features of multi-view data, a bipartite graph for each view is constructed such that the co-occurring structure of data can be extracted. The key point of utilizing the bipartite graphs to deal with the multi-view co-clustering task is to reasonably integrate these bipartite graphs and obtain an optimal consensus one. As for this point, the proposed method can learn an optimal weight for each bipartite graph automatically without introducing an additive parameter as previous methods do. Furthermore, an efficient algorithm is proposed to optimize this model with theoretically guaranteed convergence. Extensive experimental results on both toy data and several benchmark datasets have demonstrated the effectiveness of the proposed model. [ABSTRACT FROM AUTHOR]

An antimagic labeling of a graph G= (V, E) is a one-to-one mapping from Eto {1, 2, . . ., |E|} such that distinct vertices receive different label sums from the edges incident to them. Gis called antimagic if it admits an antimagic labeling. It was conjectured that every connected graph other than K2is antimagic. The conjecture remains open though it was verified for several classes of graphs such as regular graphs. A bipartite graph is called (k, k′)-biregular, if each vertex of one of its parts has the degree k, while each vertex of the other parts has the degree k′. This paper shows the following results. (1) Each connected (2, k)-biregular (k≥ 3) bipartite graph is antimagic; (2) Each (k, pk)-biregular (k≥ 3, p≥ 2) bipartite graph is antimagic; (3) Each (k, k2+ y)-biregular (k≥ 3, y≥ 1) bipartite graph is antimagic.

Given a connected graph Gwith vertex set VG, a subset Iof VGis called independent if there are no edges between any two vertices from I. Let ik(G)be the number of independent sets with cardinality kof Gand let i0(G)=1. The independence polynomial of Gis defined as I(G;x)=∑k⩾0ik(G)xk, where i(G)=I(G;1)is called the Merrifield–Simmons index of G. In this paper, some extremal problems on the coefficients of the independence polynomial of bipartite graphs are considered. Firstly, the second largest ik(G)(k⩾2)among all bipartite graphs is determined, and the graph which simultaneously minimizes all coefficients of I(G; x) among all bipartite graphs is characterized. Secondly, the largest ik(G)(k⩾2)among all bipartite graphs with at least one cycle is determined, and the unique graph which minimizes all coefficients of I(G; x) among all bipartite graphs with given matching number (resp. diameter at most four, connectivity) is characterized as well.

In this paper, we study the parameterized complexity of the induced matchingproblem in hamiltonian bipartite graphs and the inapproximability of the maximum induced matching problem in hamiltonian bipartite graphs. We show that, given a hamiltonian bipartite graph, the induced matching problem is W[1]-hard and cannot be solved in time no⁢(k){n^{o(\sqrt{k})}}, where nis the number of vertices in the graph, unless the 3SAT problem can be solved in subexponential time. In addition, we show that unless NP=P{\operatorname{NP}=\operatorname{P}}, a maximum induced matching in a hamiltonian bipartite graph cannot be approximated within a ratio of n1/4-ϵ{n^{1/4-\epsilon}}, where nis the number of vertices in the graph.

In 2003 Kostochka, Pelsmajer, and West introduced a list analogue of equitable coloring called equitable choosability. A k-assignment, L, for a graph Gassigns a list, L(v), of kavailable colors to each v∈ V(G), and an equitable L-coloring of Gis a proper coloring, f, of Gsuch that f(v) ∈ L(v) for each v ∈ V(G) and each color class of fhas size at most ⌈|V(G)|/k⌉. Graph Gis said to be equitably k-choosable if an equitable L-coloring of Gexists whenever Lis a k-assignment for G. In this note we study the equitable choosability of complete bipartite graphs. A result of Kostochka, Pelsmajer, and West implies Kn,mis equitably k-choosable if k≥ max{n, m} provided Kn,m≠ K2l+1,2l+1. We prove Kn,mis equitably k-choosable if m≤ ⌈ (m+ n)/k⌉ (k− n) which gives Kn,mis equitably k-choosable for certain ksatisfying k

AbstractUsing a result of Vdovina, we may associate to each complete connected bipartite graph $\kappa $ a two-dimensional square complex, which we call a tile complex, whose link at each vertex is $\kappa $ . We regard the tile complex in two different ways, each having a different structure as a $2$ -rank graph. To each $2$ -rank graph is associated a universal $C^{\star }$ -algebra, for which we compute the K-theory, thus providing a new infinite collection of $2$ -rank graph algebras with explicit K-groups. We determine the homology of the tile complexes and give generalisations of the procedures to complexes and systems consisting of polygons with a higher number of sides.

A fundamental quest in the theory of computing is to understand the power of randomness. It is not known whether every problem with an efficient randomized algorithm also has one that does not use randomness. One of the extensively studied problems under this theme is that of perfect matching. The perfect matching problem has a randomized parallel (NC) algorithm based on the Isolation Lemma of Mulmuley, Vazirani, and Vazirani. It is a long-standing open question whether this algorithm can be derandomized. In this article, we give an almost complete derandomization of the Isolation Lemma for perfect matchings in bipartite graphs. This gives us a deterministic parallel (quasi-NC) algorithm for the bipartite perfect matching problem. Derandomization of the Isolation Lemma means that we deterministically construct a weight assignment so that the minimum weight perfect matching is unique. We present three different ways of doing this construction with a common main idea. [ABSTRACT FROM AUTHOR]

Community search on bipartite graphs has been extensively studied in suspicious-group detection and team formation. However, the existing studies focused on the cohesiveness of the community, but ignored the size constraint on bipartite graphs, potentially leading to large community sizes and high costs. In this study, a size-constrained (α , β)–community (SCC) containing a query vertex on a bipartite graph was investigated, where the upper layer size of the community cannot exceed threshold s and the lower layer size cannot exceed threshold t. For supporting SCC search in different situations, two search methods—peeling and expansion—are proposed by peeling from the (α , β)-core containing the query vertex and expanding from the query vertex respectively. An efficient lower bound based on degree gap is proposed by terminating unpromising search branches early to increase the efficiency of the community search. The experimental results indicated that the proposed methods can be used to find communities within the size thresholds, with the efficiency of the search increased based on the lower bound. [ABSTRACT FROM AUTHOR]

Abstract: An equigenerated monomial ideal \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I$$\end{document}in the polynomial ring \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R=k[z_1,\ldots, z_n]$$\end{document}is a Freiman ideal if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mu(I^2)=\ell(I)\mu(I)-{\ell(I)\choose 2}$$\end{document}, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell(I)$$\end{document}is the analytic spread of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I$$\end{document}and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mu(I)$$\end{document}is the number of the minimal generators of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I$$\end{document}. In this paper we classify all simple connected unmixed bipartite graphs whose cover ideals are Freiman ideals.

For any S⊂ ℤ we say that a graph Ghas the S-property if there exists an S-edge-weighting w: E(G) → Ssuch that for any pair of adjacent vertices u, vwe have ∑e∈E(v)w(e) ≠ ∑e∈E(u)w(e), where E(v) and E(u) are the sets of edges incident to vand 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.

An embedding of a graph Hin a graph Gis an injection (i.e., a one-to-one function) σfrom the vertices of Hto the vertices of Gsuch that σ(x)σ(y) is an edge of Gfor all edges xyof H. The image of Hin Gunder σis denoted by σ(H). A k-packing of a graph Hin a graph Gis a sequence (σ1, σ2,…, σk) of embeddings of Hin Gsuch that σ1(H), σ2(H),…, σk(H) are edge disjoint. We prove that for any tree Tof order n, there is a 4-packing of Tin a complete bipartite graph of order at most n+ 12.

A dominating set in a graph G= (V, E) is a set Ssuch that every vertex of Gis either in Sor adjacent to a vertex in S. While the minimum cardinality of a dominating set in Gis called the domination number of Gdenoted by Γ(G), the maximum cardinality of a minimal dominating set in Gis called the upper domination number of Gdenoted by Γ(G). We call the difference between these two parameters the domination gapof Gand denote it by µd(G) = Γ(G) − Γ(G). While a graph Gwith µd(G) = 0 is said to be a well-dominatedgraph, we call a graph Gwith µd(G) = 1 an almost well-dominatedgraph. In this work, we first establish an upper bound for the cardinality of bipartite graphs with µd(G) = k, where k≥ 1, and minimum degree at least two. We then provide a complete structural characterization of almost well-dominated bipartite graphs with minimum degree at least two. While the results by Finbow et al. [Ars Comb. 25A(1988) 5–10] imply that a 4-cycle is the only well-dominated bipartite graph with minimum degree at least two, we prove in this paper that there exist precisely 31 almost well-dominated bipartite graphs with minimum degree at least two.

In recent years, Graph Convolutional Networks (GCNs), which extend convolutional neural networks to graph structure, have achieved great success on many graph learning tasks by fusing structure and feature information, such as node classification. However, the graph structure is constructed from real-world data and usually contains noise or redundancy. In addition, this structural information is based on manually defined relations and is not potentially optimal for downstream tasks. In this paper, we utilize the knowledge from node features to enhance the expressive power of GCN models in a plug-and-play fashion. Specifically, we build a node-feature bipartite graph and exploit the bipartite graph convolutional network to model node-feature relations. By aligning results from the original graph structure and node-feature relations, we can make a more accurate prediction for each node in an end-to-end manner. Extensive experiments demonstrate that the proposed model can extract knowledge from two branches and improve the performance of various GCN models on typical graph data sets and 3D point cloud data. [ABSTRACT FROM AUTHOR]

AbstractLet Ck, Skdenote a cycle, star with kedges and let Km,ndenotes a complete bipartite graph with mand nvertices in the parts. In this paper, we obtain necessary and sufficient conditions for the existence of a decomposition of complete bipartite graphs into cycles and stars with four edges.

AbstractLet G= (V, E) be a graph with set of vertices Vand set of edges E. An independent set in Gis a subset Sof Vsuch that no two vertices of Sare mutually adjacent. E. Sampathkumar et al. (2003) gave a generalization of independent sets. In this context, we define graph G= V, E) is said to be k-distance bipartite (or Dk-bipartite) if its vertex set can be partitioned into two Dkindependent sets. If the diameter of Gis < k, then Gis distance k-bipartite and so if Gis not distance k-bipartite then diameter of Gis at least k. Given any integer k >0, we can associate a graph G(k)as follows: The DK-graph of G, denoted by G(k)is the graph on same vertex set Vand two vertices uand vare adjacent if and only if distance between them is equal to k. Clearly, a graph is Dk-bipartite if and only if G(k)is bipartite. In this paper, we presented several characterizations of k-distance bipartite graphs.

In this paper, we study the local law for eigenvalues of large random regular bipartite graphs with degree growing moderately fast. We prove that the empirical spectral distribution of the adjacency matrix converges in probability to a scaled down copy of the Marchenko–Pastur distribution on intervals of short length.

AUTH Rodents living in a subterranean ecotope face a unique combination of evolutionary and ecological pressures and while host species evolution may be driven by the selective pressure from the parasites they harbour, the parasites may be responding to the selective pressures of the host. Here, we obtained all available subterranean rodent host–parasite records from the literature and integrated these data by utilizing a bipartite network analysis to determine multiple critical parameters to quantify and measure the structure and interactions of the organisms present in host–parasite communities. A total of 163 species of subterranean rodent hosts, 174 parasite species and 282 interactions were used to create 4 networks with data well-represented from all habitable continents. The results show that there was no single species of parasite that infects subterranean rodents throughout all zoogeographical regions. Nevertheless, species representing the genera Eimeria and Trichuris were common across all communities of subterranean rodents studied. Based on our analysis of host–parasite interactions across all communities studied, the parasite linkages show that community connectance (due to climate change or other anthropogenic factors) appears to show degraded linkages in both the Nearctic and Ethiopian regions: in this case parasites are acting as bell-weather probes signalling the loss of biodiversity. [ABSTRACT FROM AUTHOR]

Let Gbe either a complete graph of odd order or a complete bipartite graph in which each vertex partition has an even number of vertices. In this paper, we determine the set of triples (p, q, r), with p, q, r >0, for which there exists a decomposition of Ginto ppaths, qstars, and rcycles, each of which has 4 edges.

Topological index of a graph is a numerical representation linked to the graph or the molecular structure associated with the graph, shedding light on its topological and structural properties. Different topological indices showcase unique attributes rooted in their degree, spectrum, and distance characteristics. Among these, the first and second K Banhatti indices, introduced by Kulli, involving both vertex and edge degrees, have garnered significant scholarly interest, prompting extensive discussions in graph theory. Within this research paper, a thorough exploration delves into the attributes surrounding the fuzzified first and second K Banhatti indices. This exploration is directed towards several bounds of the index and index of various structures like cycles, complete fuzzy graphs, complete bipartite graphs and stars. Relation between a fuzzy graph and its partial subgraphs, fuzzy graph and its complement graph in connection with the indices is also found. Additionally, the research paper investigates the first and second K Banhatti indices concerning graph operations such as the corona product and coalescence. Additionally, the paper outlines an algorithm designed to accurately compute the first and second K Banhatti indices and proposes an application in decision-making. [ABSTRACT FROM AUTHOR]

In this paper, we consider the relationships between the numbers of perfect matchings (1-factors) of bipartite graphs and Pell, Mersenne and Perrin Numbers. Then we give some Maple procedures in order to calculate the numbers of perfect matchings of these bipartite graphs.

Research on graph representation learning (a.k.a. embedding) has received great attention in recent years and shows effective results for various types of networks. Nevertheless, few initiatives have been focused on the particular case of embeddings for bipartite graphs. In this paper, we first define the graph embedding problem in the case of bipartite graphs. Next, we propose a taxonomy of approaches used to tackle this problem and draw a description of state-of-the-art methods. Then, we establish their pros and cons with respect to conventional network embeddings. Finally, we provide a description of available resources to lead experiments on the subject.

A sequence Sof vertices of a graph Gis called a dominating sequence of Gif (1) each vertex vof Sdominates a vertex of Gthat was not dominated by any of the vertices preceding vertex vin S, and (2) every vertex of Gis dominated by at least one vertex of S. The Grundy Dominationproblem is to find a longest dominating sequence for a given graph G. It has been known that the decision version of the Grundy Dominationproblem is NP-complete even when restricted to chordal graphs. In this paper, we prove that the decision version of the Grundy Dominationproblem is NP-complete for bipartite graphs and co-bipartite graphs. On the positive side, we present a linear-time algorithm that solves the Grundy Dominationproblem for chain graphs, which form a subclass of bipartite graphs.

AbstractWe consider quadruples of positive integers with and such that every proper edge-coloring of the complete bipartite graph contains a rainbow subgraph. We show that every such quadruple with and satisfies this property and find an infinite sequence where this bound is sharp. We also define and compute some new anti-Ramsey numbers.

In the note we consider vertex coloring of a graph in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of coloring is the sum of costs incurred at each vertex. We show that the minimum cost coloring problem for n-vertex bipartite graph of degree Δ ≤ 4 can be solved in O(n2) time. This extends Jansen’s result [K. Jansen, The optimum cost chromatic partition problem, in: Proc. CIAC’97, Lecture Notes in Comput. Sci. 1203 (1997) 25–36] for paths and cycles to subgraphs of biquartic graphs.

The strong geodetic number, sg(G),of a graph Gis the smallest number of vertices such that by fixing a suitable geodesic between each pair of selected vertices, all vertices of the graph are covered. In this paper, the formula for sg(Kn,m)is given, as well as a formula for the crown graphs Sn0. Bounds on the strong geodetic number of the hypercube Qnare also discussed.

AbstractWe determine the number of cycles of different lengths in the minimum fundamental cycle basis of some bipartite graphs with centralized spanning trees. As applications, we characterize the minimum fundamental cycle basis of some -regular balanced graphs with order .

AbstractAn edge labeled graph is a graph whose edges are labeled with non-zero ideals of a commutative ring . A Generalized Spline on an edge labeled graph is a vertex labeling of by elements of the ring , such that the difference between any two adjacent vertex labels belongs to the ideal corresponding to the edge joining both the vertices. The set of generalized splines forms a subring of the product ring , with respect to the operations of coordinate-wise addition and multiplication. This ring is known as the generalized spline ring , defined on the edge labeled graph , for the commutative ring . We have considered particular graphs such as complete graphs, complete bipartite graphs and hypercubes, labeling the edges with the non-zero ideals of an integral domain and have identified the generalized spline ring for these graphs. Also, general algorithms have been developed to find these splines for the above mentioned graphs, for any number of vertices and Python code has been written for finding these splines.