Search

Luo, Tian and Wu (2022) conjectured that for any tree $T$ with bipartition $X$ and $Y$, every $k$-connected bipartite graph $G$ with minimum degree at least $k+t$, where $t=$max$\{|X|,|Y|\}$, contains a tree $T'\cong T$ such that $G-V(T')$ is still $k$-connected. Note that $t=\lceil\frac{m}{2}\rceil$ when the tree $T$ is the path with order $m$. In this paper, we proved that every $k$-connected bipartite graph $G$ with minimum degree at least $k+ \lceil\frac{m+1}{2}\rceil$ contains a path $P$ of order $m$ such that $G-V(P)$ remains $k$-connected. This shows that the conjecture is true for paths with odd order. And for paths with even order, the minimum degree bound in this paper is the bound in the conjecture plus one.

Enumerating maximal $k$-biplexes (MBPs) of a bipartite graph has been used for applications such as fraud detection. Nevertheless, there usually exists an exponential number of MBPs, which brings up two issues when enumerating MBPs, namely the effectiveness issue (many MBPs are of low values) and the efficiency issue (enumerating all MBPs is not affordable on large graphs). Existing proposals of tackling this problem impose constraints on the number of vertices of each MBP to be enumerated, yet they are still not sufficient (e.g., they require to specify the constraints, which is often not user-friendly, and cannot control the number of MBPs to be enumerated directly). Therefore, in this paper, we study the problem of finding $K$ MBPs with the most edges called MaxBPs, where $K$ is a positive integral user parameter. The new proposal well avoids the drawbacks of existing proposals. We formally prove the NP-hardness of the problem. We then design two branch-and-bound algorithms, among which, the better one called FastBB improves the worst-case time complexity to $O^*(\gamma_k^ n)$, where $O^*$ suppresses the polynomials, $\gamma_k$ is a real number that relies on $k$ and is strictly smaller than 2, and $n$ is the number of vertices in the graph. For example, for $k=1$, $\gamma_k$ is equal to $1.754$. We further introduce three techniques for boosting the performance of the branch-and-bound algorithms, among which, the best one called PBIE can further improve the time complexity to $O^*(\gamma_k^{d^3})$ for large sparse graphs, where $d$ is the maximum degree of the graph. We conduct extensive experiments on both real and synthetic datasets, and the results show that our algorithm is up to four orders of magnitude faster than all baselines and finding MaxBPs works better than finding all MBPs for a fraud detection application., Comment: This paper has been accepted by SIGMOD 2023

In vertex-cut sparsification, given a graph $G=(V,E)$ with a terminal set $T\subseteq V$, we wish to construct a graph $G'=(V',E')$ with $T\subseteq V'$, such that for every two sets of terminals $A,B\subseteq T$, the size of a minimum $(A,B)$-vertex-cut in $G'$ is the same as in $G$. In the most basic setting, $G$ is unweighted and undirected, and we wish to bound the size of $G'$ by a function of $k=|T|$. Kratsch and Wahlstr\"om [JACM 2020] proved that every graph $G$ (possibly directed), admits a vertex-cut sparsifier $G'$ with $O(k^3)$ vertices, which can in fact be constructed in randomized polynomial time. We study (possibly directed) graphs $G$ that are quasi-bipartite, i.e., every edge has at least one endpoint in $T$, and prove that they admit a vertex-cut sparsifier with $O(k^2)$ edges and vertices, which can in fact be constructed in deterministic polynomial time. In fact, this bound naturally extends to all graphs with a small separator into bounded-size sets. Finally, we prove information-theoretically a nearly-matching lower bound, i.e., that $\tilde{\Omega}(k^2)$ edges are required to sparsify quasi-bipartite undirected graphs., Comment: 12 pages, 3 figures

The upper density of an infinite graph $G$ with $V(G) \subseteq \mathbb{N}$ is defined as $\overline{d}(G) = \limsup_{n \rightarrow \infty}{|V(G) \cap \{1,\ldots,n\}|}/{n}$. Let $K_{\mathbb{N}}$ be the infinite complete graph with vertex set $\mathbb{N}$. Corsten, DeBiasio, Lamaison and Lang showed that in every $2$-edge-colouring of $K_{\mathbb{N}}$, there exists a monochromatic path with upper density at least $(12 + \sqrt{8})/17$, which is best possible. In this paper, we extend this result to $k$-edge-colouring of $K_{\mathbb{N}}$ for $k \ge 3$. We conjecture that every $k$-edge-coloured $K_{\mathbb{N}}$ contains a monochromatic path with upper density at least $1/(k-1)$, which is best possible (when $k-1$ is a prime power). We prove that this is true when $k = 3$ and asymptotically when $k =4$. Furthermore, we show that this problem can be deduced from its bipartite variant, which is of independent interest., Comment: fixed some typos

We consider the averaging process on a graph, that is the evolution of a mass distribution undergoing repeated averages along the edges of the graph at the arrival times of independent Poisson processes. We establish cutoff phenomena for both the $L^1$ and $L^2$ distance from stationarity when the graph is a discrete hypercube and when the graph is complete bipartite. Some general facts about the averaging process on arbitrary graphs are also discussed., Comment: 30 pages. Comments are welcome

A graph $\mathcal{H}=(W,E_\mathcal{H})$ is said to have {\em bandwidth} at most $b$ if there exists a labeling of $W$ as $w_1,w_2,\dots,w_n$ such that $|i-j|\leq b$ for every edge $w_iw_j\in E_\mathcal{H}$. We say that $\mathcal{H}$ is a {\em balanced $(\beta,\Delta)$-graph} if it is a bipartite graph with bandwidth at most $\beta |W|$ and maximum degree at most $\Delta$, and it also has a proper 2-coloring $\chi :W\rightarrow[2]$ such that $||\chi^{-1}(1)|-|\chi^{-1}(2)||\leq\beta|\chi^{-1}(2)|$. In this paper, we prove that for every $\gamma>0$ and every natural number $\Delta$, there exists a constant $\beta>0$ such that for every balanced $(\beta,\Delta)$-graph $\mathcal{H}$ on $n$ vertices we have $$R(\mathcal{H}, \mathcal{H}, C_n) \leq (3+\gamma)n$$ for all sufficiently large odd $n$. The upper bound is sharp for several classes of graphs. Let $\theta_{n,t}$ be the graph consisting of $t$ internally disjoint paths of length $n$ all sharing the same endpoints. As a corollary, for each fixed $t\geq 1$, $R(\theta_{n, t},\theta_{n, t}, C_{nt+\lambda})=(3t+o(1))n,$ where $\lambda=0$ if $nt$ is odd and $\lambda=1$ if $nt$ is even. In particular, we have $R(C_{2n},C_{2n}, C_{2n+1})=(6+o(1))n$, which is a special case of a result of Figaj and {\L}uczak (2018)., Comment: 17 pages

In bottom-up proteomics, proteins are enzymatically digested into peptides before measurement with mass spectrometry. The relationship between proteins and their corresponding peptides can be represented by bipartite graphs. We conduct a comprehensive analysis of bipartite graphs using quantified peptides from measured data sets as well as theoretical peptides from an in silico digestion of the corresponding complete taxonomic protein sequence databases. The aim of this study is to characterize and structure the different types of graphs that occur and to compare them between data sets. We observed a large influence of the accepted minimum peptide length during in silico digestion. When changing from theoretical peptides to measured ones, the graph structures are subject to two opposite effects. On the one hand, the graphs based on measured peptides are on average smaller and less complex compared to graphs using theoretical peptides. On the other hand, the proportion of protein nodes without unique peptides, which are a complicated case for protein inference and quantification, is considerably larger for measured data. Additionally, the proportion of graphs containing at least one protein node without unique peptides rises when going from database to quantitative level. The fraction of shared peptides and proteins without unique peptides as well as the complexity and size of the graphs highly depends on the data set and organism. Large differences between the structures of bipartite peptide-protein graphs have been observed between database and quantitative level as well as between analyzed species. In the analyzed measured data sets, the proportion of protein nodes without unique peptides ranged from 6.4% to 55.0%. This highlights the need for novel methods that can quantify proteins without unique peptides. The knowledge about the structure of the bipartite peptide-protein graphs gained in this study will be useful for the development of such algorithms.

Let K be a graph with n vertices and G= { π(x) : x ∈v (K)} be a collection of isomorphic pages (called subgraphs) of K . Then G is an orthogonal double cover (ODC) of K by G iff (i) every edge of K is repeated exactly twice in G and (ii) π(a) and π(b) have one edge iff a and b are adjacent vertices in K . In this paper, we are interested in finding new symmetric starter vectors (SSV) based on Cartesian product methods, such as SSV of complete bipartite graphs with complete bipartite graphs, disjoint copies of paths with stars, stars with caterpillars, disjoint copies of stars with caterpillars, disjoint copies of cycles with caterpillars, disjoint copies of paths with caterpillars, and complete bipartite graphs with caterpillars. Then we use these symmetric starter vectors to get the enormous graphs and construct the ODCs.

Bipartite graphs can be used to model many real-world relationships, with applications in many domains such as medicine and social networks. We present an application of maximal bicliques of bipartite graphs to recommendation systems that makes use of the notion of biclique similarity of a set of vertices in order to recommend items to users in a certain order of preference. Experimental results using real-world datasets that justify our approach are presented.

In 2019, Czabarka, Dankelmann and Székely showed that for every undirected graph of order $n$, the minimum degree threshold for diameter two orientability is $\frac{n}{2}+ \Theta(\ln n)$. In this paper, we consider bipartite graphs and give a sufficient condition in terms of the minimum degree for such graphs to have oriented diameter three. We in particular prove that for balanced bipartite graphs of order $n$, the minimum degree threshold for diameter three orientability is $\frac{n}{4}+\Theta(\ln n)$.

Jupyter notebook and example data files to reproduce the figures from the manuscript "Martingales and the characteristic functions of absorption time on bipartite graphs."

Petri nets (PNs) are bipartite graphs with two types of nodes: places and transitions. Places usually represent objects and transitions represent some actions or reactions. Places may contain tokens, which according to defined rules, can be transferred between places by transitions. The basic idea of PNs is simple. However, it allows to create a wide range of models. This chapter is focused on PNs models in biology. A few examples of PNs applications in this discipline are presented: modeling of Gene Regulatory Networks; metabolic, signaling and regulatory network modeling and analysis of Molecular Dynamic simulations results. Basic definitions, biologically important properties and the most commonly used extensions of PNs are also presented. The chapter shows that PNs can be used to create variety of models: qualitative, quantitative, synchronous, asynchronous, which can be applied to various biological phenomena.

Let $X=(V, E)$ be a finite regular graph and $H_t(u, v), \, u, v \in V$, the heat kernel on $X$. We prove that, if the graph $X$ is bipartite and has four distinct Laplacian eigenvalues, the ratio $H_t(u, v)/H_t(u, u), \, u, v \in V,$ is monotonically non-decreasing as a function of $t$. The key to the proof is the fact that such a graph is an incidence graph of a symmetric 2-design., Comment: 13 pages, 2 figures

We 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 ( n − k ) -regular balanced graphs with order 2 n .

Graph embedding is an important technique used in studying the problem of efficiently implementing parallel algorithms on parallel computers. Wirelength is an embedding parameter widely studied in data structures and data representations, electrical networks, VLSI network and chemical graphs. This parameter had been studied for embedding complete bipartite graphs into complete necklace, star necklace and windmill graphs.

In this paper, we focus on a so-called Fan-type condition assuring us the existence of long paths in bipartite graphs. As a consequence of our main result, we completely determine the bipartite Ramsey numbers $$b(P_{s},B_{t_{1},t_{2}})$$, where $$B_{t_{1},t_{2}}$$ is the graph obtained from a $$t_{1}$$-star and a $$t_{2}$$-star by joining their centers.

Let G be a connected graph with vertex set V(G). The Harary index of a graph is defined as H(G) = ∑u ≠ v 1/d(u, v), where d(u, v) denotes the distance between u and v. In this paper, we determine the extremal graphs with the maximum Harary index among all bipartite graphs of order n with a given matching number, with a given vertex-connectivity and with a given edge-connectivity, respectively.

We prove that each of the 34 non-isomorphic connected unicyclic bipartite graphs with eight edges decomposes the complete graph K n whenever the necesary conditions are satisfied.

We continue the study of a class of signed graphs called finite connected loop-free edge-bipartite graphs Δ (bigraphs, for short), started in Simson (2013) [33] and continued in Gąsiorek et al. (2016) [14] and Simson-Zając (2017) [38] . In this paper we present an algorithmic approach to the study of non-negative bigraphs Δ with n + r ≥ 2 vertices of corank r ≥ 1 , that is, bigraphs with the symmetric Gram matrix G Δ : = 1 2 ( G ˇ Δ + G ˇ Δ t r ) ∈ M n + r ( 1 2 Z ) positive semi-definite of rank n ≥ 1 , where G ˇ Δ ∈ M n + r ( Z ) is the non-symmetric Gram matrix of Δ. One of the main results of this paper are Theorem 2.1 , Theorem 2.17 asserting that every such a bigraph Δ with n + r ≥ 2 vertices can be obtained from a corank zero (i.e. positive) connected loop-free bigraph Δ ′ with n ≥ 1 vertices by an r-point extension procedure ( Δ ′ , u ( 1 ) , … , u ( r ) ) ↦ Δ : = Δ ′ [ [ u ( 1 ) , … , u ( r ) ] ] along the r ≥ 1 roots u ( 1 ) , … , u ( r ) ∈ Z n of the positive definite Gram form q Δ ′ : Z n → Z , v ↦ v G ˇ Δ ′ v t r . It is also shown that the extension procedure yields a combinatorial algorithm allowing us to obtain inductively all connected loop-free non-negative corank r ≥ 1 bigraphs with n + r ≥ 2 vertices, from the corank-zero bigraphs Δ ′ with n ≥ 1 vertices.

For a graph with an even number of vertices, the matching preclusion number is the minimum number of edges whose deletion results in a graph with no perfect matchings. The conditional matching preclusion number, introduced as an extension of the matching preclusion number, has the additional requirement that the resulting graph have no isolated vertices. In bipartite graphs, the edge sets that achieve these minimum numbers can be construed in terms of obstruction sets of vertices. From this perspective, the generalized matching preclusion problem was developed; the matching preclusion number of order a is the minimum number of edges whose deletion results in a graph with no perfect matchings and no obstruction sets with fewer than a vertices. In this paper, we extend known sufficient conditions regarding the matching preclusion and conditional matching preclusion numbers (orders 1 and 2, respectively) to give sufficient conditions for the matching preclusion problem of order a, for any positive integer a.

Let B u ( n , r ) denote the set of unlabeled bipartite graphs whose edges connect a set of n vertices with a set of r vertices. In this paper, we provide exact formulas for | B u ( 2 , r ) | and | B u ( 3 , r ) | using Polya’s Counting Theorem. Extending these results to n ≥ 4 involves solving a set of complex recurrences and remains open. In particular, the number of recurrences that must be solved to compute | B u ( n , r ) | is given by the number of partitions of n that is known to increase exponentially with n by Ramanujan–Hardy–Rademacher’s asymptotic formula.

Motivated by Ramsey-type questions, we consider edge-colorings of complete graphs and complete bipartite graphs without rainbow path. Given two graphs G and H , the k -colored Gallai–Ramsey number g r k ( G : H ) is defined to be the minimum integer n such that n 2 ≥ k and for every N ≥ n , every rainbow G -free coloring (using all k colors) of the complete graph K N contains a monochromatic copy of H . In this paper, we first provide some exact values and bounds of g r k ( P 5 : K t ) . Moreover, we define the k -colored bipartite Gallai–Ramsey number b g r k ( G : H ) as the minimum integer n such that n 2 ≥ k and for every N ≥ n , every rainbow G -free coloring (using all k colors) of the complete bipartite graph K N , N contains a monochromatic copy of H . Furthermore, we describe the structures of complete bipartite graph K n , n with no rainbow P 4 and P 5 , respectively. Finally, we find the exact values of b g r k ( P 4 : K s , t ) ( 1 ≤ s ≤ t ), b g r k ( P 4 : F ) (where F is a subgraph of K s , t ), b g r k ( P 5 : K 1 , t ) and b g r k ( P 5 : K 2 , t ) by using the structural results.

A graceful labeling of a graph G with n edges is an assignment to each vertex of G a distinct element of $$\{0,\ldots ,n\}$$ such that if each edge of G inherits the label given by the absolute value of the difference of the labels of its incident vertices, then the set of inherited edge labels is $$\{1,\ldots ,n\}$$. The long-standing graceful labeling conjecture proposes that every tree is graceful. In this paper we present methods to combine graceful bipartite graphs to create new graceful graphs. These methods unify and generalize some well-known results in the graceful labeling literature. Along the way we introduce a new class of graceful trees.

Let $G$ be a finite simple graph on $n$ vertices and $J_G$ denote the corresponding binomial edge ideal in $S = K[x_1, \ldots, x_n, y_1, \ldots, y_n].$ In this article, we prove that if $G$ is a fan graph of a complete graph, then $reg(S/J_G) \leq c(G)$, where $c(G)$ denote the number of maximal cliques in $G$. Further, we show that if $G$ is a $k$-pure fan graph, then $reg(S/J_G) = k+1$. We then compute a precise expression for the regularity of Cohen-Macaulay bipartite graphs., Minor correction in Remark 2.1; To Appear in Comm. Algebra

For a set Ω = {1, 2, . . . , n} where n = 2k ≥ 6, let Ω{k} denote the set of all subsets of Ω of size k. We examine the binary codes from the row span of biadjacency matrices of bipartite graphs wi...

Choi et al. (2016) introduced the notion of the partial order competition dimension of a graph and characterized the graphs with partial order competition dimension d in terms of homothetic regular ( d − 1 ) -simplices in R d which are contained in the hyperplane { x ∈ R d ∣ x ⋅ 1 = 0 } . In this paper, we introduce a useful notion “order types for two points in R 3 ” and give an upper bound of the partial order competition dimension of a graph in terms of its chromatic number, which is achieved via constructing a matrix in a somewhat clever way, to study partial order competition dimensions of bipartite graphs and planar graphs.

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, community search on bipartite graphs remains largely unexplored. Moreover, all existing cohesive subgraph models on bipartite graphs can only be applied to measure the structure cohesiveness between two sets of vertices while overlooking the edge weight in forming the community. In this paper, we study the significant (alpha, beta)-community search problem on weighted bipartite graphs. Given a query vertex q, we aim to find the significant (alpha, beta)-community R of q which adopts (alpha, beta)-core to characterize the engagement level of vertices, and maximizes the minimum edge weight (significance) within R. To support fast retrieval of R, we first retrieve the maximal connected subgraph of (alpha, beta)-core containing the query vertex (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 which can be built in O(delta * m) time and takes O(delta * m) space where m is the number of edges in G, delta is bounded by the square root of m and is much smaller in practice. Utilizing the index, the (alpha, beta)-community can be retrieved in optimal time. To further obtain R, we develop peeling and expansion algorithms to conduct searches by shrinking from the (alpha, beta)-community and expanding from the query vertex, respectively. The experimental results on real graphs not only demonstrate the effectiveness of the significant (alpha, beta)-community model but also validate the efficiency of our query processing and indexing techniques.

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. Folkman and Fulkerson [2] described bipartite graphs whose edge set can be partitioned into l1 matchings of size k1 and l2 matchings of size k2. We complement this result by showing that it is NP-complete to decide whether the edge set of a bipartite graph can be partitioned into three matchings, of size k1, k2 and k3. This will follow from the NP-completeness of the following “perfect matching + matching” problem. Input: G bipartite graph with maximum degree 3, natural number k. Goal: Decide whether G contains an edge-disjoint perfect matching and a matching of size k. Computing Classification System 1998: G.2.2 Mathematics Subject Classification 2010: 05C30, 05C50

A simple generalization of the Hall's condition in bipartite graphs, the Normalized Matching Property (NMP) in a graph $G(X,Y,E)$ with vertex partition $(X,Y)$ states that for any subset $S\subseteq X$, we have $\frac{|N(S)|}{|Y|}\ge\frac{|S|}{|X|}$. In this paper, we show the following results about having the Normalized Matching Property in random and pseudorandom graphs. 1. We establish $p=\frac{\log n}{k}$ as a sharp threshold for having NMP in $\mathbb{G}(k,n,p)$, which is the graph with $|X|=k,|Y|=n$ (assuming $k\le n\leq \exp(o(k))$), and in which each pair $(x,y)\in X\times Y$ is an edge independently with probability $p$. This generalizes a classic result of Erd\H{o}s-R\'enyi on the $\frac{\log n}{n}$ threshold for having a perfect matching in $\mathbb{G}(n,n,p)$. 2. We also show that a pseudorandom bipartite graph - upon deletion of a vanishingly small fraction of vertices - admits NMP, provided it is not too sparse. More precisely, a bipartite graph $G(X,Y)$, with $k=|X|\le |Y|=n$, is said to be Thomason pseudorandom (following A. Thomason (Discrete Math., 1989)) with parameters $(p,\varepsilon)$ if each $x\in X$ has degree at least $pn$ and each pair of distinct $x, x'\in X$ has at most $(1+\varepsilon)p^2n$ common neighbors. We show that for any large enough $(p,\varepsilon)$-Thomason pseudorandom graph $G(X,Y)$, there are "tiny" subsets $\mathrm{Del}_X\subset X, \ \mathrm{Del}_Y\subset Y$ such that the subgraph $G(X\setminus \mathrm{Del}_X,Y\setminus \mathrm{Del}_Y)$ has NMP, provided $p \gg\tfrac{1}{k}$. En route, we prove an "almost" vertex decomposition theorem: Every such Thomason pseudorandom graph admits - excluding a negligible portion of its vertex set - a partition of its vertex set into graphs that we call Euclidean trees. These are trees that have NMP, and which arise organically through the Euclidean GCD algorithm., Comment: 28 pages, 3 figures; Changes from v1 to v2: improved exposition and clarity of proofs, added references. Change from v2 to v3: added one new reference for Euclidean trees

For a graph [Formula: see text] and a set [Formula: see text] of size at least [Formula: see text], a path in [Formula: see text] is said to be an [Formula: see text]-path if it connects all vertices of [Formula: see text]. Two [Formula: see text]-paths [Formula: see text] and [Formula: see text] are said to be internally disjoint if [Formula: see text] and [Formula: see text]. Let [Formula: see text] denote the maximum number of internally disjoint [Formula: see text]-paths in [Formula: see text]. The [Formula: see text]-path-connectivity [Formula: see text] of [Formula: see text] is then defined as the minimum [Formula: see text], where [Formula: see text] ranges over all [Formula: see text]-subsets of [Formula: see text]. In [M. Hager, Path-connectivity in graphs, Discrete Math. 59 (1986) 53–59], the [Formula: see text]-path-connectivity of the complete bipartite graph [Formula: see text] was calculated, where [Formula: see text]. But, from his proof, only the case that [Formula: see text] was considered. In this paper, we calculate the situation that [Formula: see text] and complete the result.

Motivation The increasing number of publicly available databases containing drugs’ chemical structures, their response in cell lines, and molecular profiles of the cell lines has garnered attention to the problem of drug response prediction. However, many existing methods do not fully leverage the information that is shared among cell lines and drugs with similar structure. As such, drug similarities in terms of cell line responses and chemical structures could prove to be useful in forming drug representations to improve drug response prediction accuracy. Results We present two deep learning approaches, BiG-DRP and BiG-DRP+, for drug response prediction. Our models take advantage of the drugs’ chemical structure and the underlying relationships of drugs and cell lines through a bipartite graph and a heterogeneous graph convolutional network that incorporate sensitive and resistant cell line information in forming drug representations. Evaluation of our methods and other state-of-the-art models in different scenarios shows that incorporating this bipartite graph significantly improves the prediction performance. In addition, genes that contribute significantly to the performance of our models also point to important biological processes and signaling pathways. Analysis of predicted drug response of patients’ tumors using our model revealed important associations between mutations and drug sensitivity, illustrating the utility of our model in pharmacogenomics studies. Availability and implementation An implementation of the algorithms in Python is provided in https://github.com/ddhostallero/BiG-DRP. Supplementary information Supplementary data are available at Bioinformatics online.

We study the metastable behaviour of a stochastic system of particles with hard-core interactions in a high-density regime. Particles sit on the vertices of a bipartite graph. New particles appear subject to a neighbourhood exclusion constraint, while existing particles disappear, all according to independent Poisson clocks. We consider the regime in which the appearance rates are much larger than the disappearance rates, and there is a slight imbalance between the appearance rates on the two parts of the graph. Starting from the configuration in which the weak part is covered with particles, the system takes a long time before it reaches the configuration in which the strong part is covered with particles. We obtain a sharp asymptotic estimate for the expected transition time, show that the transition time is asymptotically exponentially distributed, and identify the size and shape of the critical droplet representing the bottleneck for the crossover. For various types of bipartite graphs the computations are made explicit. Proofs rely on potential theory for reversible Markov chains, and on isoperimetric results. In a follow-up paper we will use our results to study the performance of random-access wireless networks., 56 pages, 17 figures; small corrections (hypothesis H0, example 4.3, typos)

A chain bipartite graph is a graph whose graph vertices can be partitioned into n disjoint 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 $$\alpha $$ -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.

We study the imbalance problem on complete bipartite graphs. The imbalance problem is a graph layout problem and is known to be NP-complete. Graph layout problems find their applications in the optimization of networks for parallel computer architectures, VLSI circuit design, information retrieval, numerical analysis, computational biology, graph theory, scheduling and archaeology. In this paper, we give characterizations for the optimal solutions of the imbalance problem on complete bipartite graphs. Using the characterizations, we can solve the imbalance problem in $\mathcal{O}(\log(|V|) \cdot \log(\log(|V|)))$ time, when given the cardinalities of the parts of the graph, and verify whether a given solution is optimal in $O(|V|)$ time on complete bipartite graphs. We also introduce a restricted form of proper interval bipartite graphs on which the imbalance problem is solvable in $\mathcal{O}(c \cdot \log(|V|) \cdot \log(\log(|V|)))$ time, where $c = \mathcal{O}(|V|)$, by using the aforementioned characterizations., Comment: 22 pages (of which 9 pages appendix), 17 figures

A word-representable graph is a simple graph $G$ which can be represented by a word $w$ over the vertices of $G$ such that any two vertices are adjacent in $G$ if and only if they alternate in $w$. It is known that the class of comparability graphs -- the graphs which admit a transitive orientation -- is precisely the class of graphs that can be represented by a concatenation of permutations of vertices. The class of bipartite graphs is a subclass of comparability graphs. While it is an open problem to determine the representation number of comparability graphs, it was conjectured that the representation number of bipartite graphs on $n$ vertices is at most $n/4$. In this paper, we propose a polynomial time relabeling algorithm to produce a word representing a given bipartite graph which is a concatenation of permutations of the graph's vertices. Thus we obtain an upper bound for the representation number of bipartite graphs, which in turn gives us an upper bound for the dimension of the posets corresponding to bipartite graphs., Comment: 19th International Conference on Relational and Algebraic Methods in Computer Science (RAMiCS 2021)

A dominating set in a graph G = (V, E) is a set S such that every vertex of G is either in S or adjacent to a vertex in S. While the minimum cardinality of a dominating set in G is called the domination number of G denoted by Γ(G), the maximum cardinality of a minimal dominating set in G is called the upper domination number of G denoted by Γ(G). We call the difference between these two parameters the domination gap of G and denote it by µd(G) = Γ(G) − Γ(G). While a graph G with µd(G) = 0 is said to be a well-dominated graph, we call a graph G with µd(G) = 1 an almost well-dominated graph. 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.

The vector choice number of a graph G over a field \(\mathbb {F}\), introduced by Haynes et al. (Electron. J. Comb., 2010), is the smallest integer k such that for every assignment of k-dimensional subspaces of a vector space over \(\mathbb {F}\) to the vertices, it is possible to choose nonzero vectors for the vertices from their subspaces so that the vectors received by adjacent vertices are orthogonal over \(\mathbb {F}\). This work is concerned with the vector choice number of bipartite graphs over various fields. We first observe that the vector choice number of bipartite graphs can be arbitrarily large over any field. We then consider the problem of estimating, for a given integer k, the smallest integer m for which the vector choice number of the complete bipartite graph \(K_{k,m}\) over \(\mathbb {F}\) exceeds k. We prove upper and lower bounds on this quantity, implying a substantial difference between the behavior of the (color) choice number and the vector choice number on bipartite graphs. For the computational aspect, we show a hardness result for deciding whether the vector choice number of a given bipartite graph over \(\mathbb {F}\) is at most k, provided that \(k \ge 3\) and that \(\mathbb {F}\) is either the real field or any finite field.