Graph Imperfection with a Co-Site Constraint. by Gerke, S, McDiarmid, C

“…These classes include comparability graphs, co-comparability graphs, and line-graphs of bipartite graphs.…”

Fine-grained dichotomies for the Tutte plane and Boolean #CSP by Roth, M, Brand, C, Dell, H

“…The main ingredient is to prove that the number of independent sets in bipartite graphs with n vertices cannot be computed in time exp(o(n)) unless #ETH fails.…”

Total 2-Rainbow Domination in Graphs by Huiqin Jiang, Yongsheng Rao

“…We prove that the MT2RDP is NP-complete for planar bipartite graphs, chordal bipartite graphs, undirected path graphs and split graphs. …”
Get full text

A Community Detection and Graph-Neural-Network-Based Link Prediction Approach for Scientific Literature by Chunjiang Liu, Yikun Han, Haiyun Xu, Shihan Yang, Kaidi Wang, Yongye Su

“…This consistent increase in performance—reflected in our extensive experimentation on bipartite graphs of scientific collaborations and citations—highlights the synergistic potential of combining community detection with GNNs to overcome common link prediction challenges such as scalability and resolution limits. …”
Get full text

Belief Propagation and LP Relaxation for Weighted Matching in General Graphs by Sanghavi, S., Malioutov, Dmitry M., Willsky, Alan S.

“…This establishes the extension of the recent result by Bayati, Shah and Sharma, which considered bipartite graphs, to general graphs. Perhaps more interestingly, we also establish a tight converse, namely that the presence of any fractional LP optimum implies that max-product will fail to yield useful estimates on some of the edges. …”
Get full text
Get full text

The price of connectivity in fair division by Bei, Xiaohui, Igarashi, Ayumi, Lu, Xinhang, Suksompong, Warut

“…In addition, we determine the optimal relaxation of envy-freeness that can be obtained with each graph for two agents, and characterize the set of trees and complete bipartite graphs that always admit an allocation satisfying envy-freeness up to one good (EF1) for three agents. …”
Get full text

The k-Ramsey number of two five cycles by Johannes H. Hattingh, Elizabeth Jonck, Ronald J. Maartens

“…AbstractGiven any two graphs F and H, the Ramsey number R(F, H) is defined as the smallest positive integer n such that every red-blue coloring of the edges of the complete graph Kn of order n, there will be a subgraph of Kn isomorphic to F whose edges are all colored red (a red F) or a subgraph of Kn isomorphic to H whose edges are all colored blue (a blue H). If F and H are bipartite graphs, then the k-Ramsey number [Formula: see text] is defined as the smallest positive integer n such that for any red-blue coloring of the edges of the complete k-partite graph of order n in which each partite set is of order [Formula: see text] or [Formula: see text] there will be a subgraph isomorphic to F whose edges are all colored red (a red F) or a subgraph isomorphic to H whose edges are all colored blue (a blue H). …”
Get full text

Quasi-total Roman reinforcement in graphs by N. Ebrahimi, J. Amjadi, M. Chellali, S.M. Sheikholeslami

“…We first show that the decision problem associated with the quasi-total Roman reinforcement problem is NP-hard even when restricted to bipartite graphs. Then basic properties of the quasi-total Roman reinforcement number are provided. …”
Get full text

Matching algorithms to assist in designing with reclaimed building elements by A Tomczak, S M Haakonsen, M Łuczkowski

“…The implementation includes greedy algorithms, bipartite graphs, and mixed integer linear programming. …”
Get full text

Multi-objective Beam-ACO for Maximising Reliability and Minimising Communication Overhead in the Component Deployment Problem by Dhananjay Thiruvady, Asef Nazari, Aldeida Aleti

“…Moreover, this problem can be modelled by bipartite graphs with complicating constraints, but known methods do not scale well under the additional restrictions. …”
Get full text

Forbidden Structures for Planar Perfect Consecutively Colourable Graphs by Borowiecka-Olszewska Marta, Drgas-Burchardt Ewa

“…Sevast- janov showed that the corresponding decision problem is NP-complete even restricted to the class of bipartite graphs. We focus our attention on the class of consecutively colourable graphs whose all induced subgraphs are consecutively colourable, too. …”
Get full text

The complexity of counting problems by Annan, J, Annan, James

“…</p><p>Polynomial-time computable recurrence relations are given for the Tutte polynomial of the complete graphs and complete bipartite graphs, which can be solved at certain points. …”

Hop total Roman domination in graphs by H. Abdollahzadeh Ahangar, M. Chellali, S. M. Sheikholeslami, M. Soroudi

“…More precisely, we show that the decision problem corresponding to the hop total Roman domination problem is NP-complete for bipartite graphs, and we determine the exact value of [Formula: see text] for paths and cycles. …”
Get full text

On eulerian irregularity in graphs by Andrews Eric, Lumduanhom Chira, Zhang Ping

“…Furthermore, Eulerian irregularities are determined for all graphs of cycle rank 2 and all complete bipartite graphs…”
Get full text

Connectivity and Hamiltonicity of Canonical Colouring Graphs of Bipartite and Complete Multipartite Graphs by Ruth Haas, Gary MacGillivray

“…It is shown that for complete multipartite graphs, and bipartite graphs there exists a vertex ordering &pi; such that Can k &pi; ( G ) is connected for large enough values of k. …”
Get full text

Analysis of biclusters with applications to gene expression data by Gahyun Park, Wojciech Szpankowski

“…These findings complete some recent results concerning maximal biclusters and maximum balanced bicliques for random bipartite graphs.…”
Get full text

Pseudo-determinism by Grossman, Ofer

“…We first show a pseudo-deterministic NC algorithm for finding matchings in bipartite graphs. As a corollary, we also show a pseudo-deterministic NC algorithm for constructing DFS trees in graphs. …”
Get full text

Explicit Two-Sided Unique-Neighbor Expanders by Hsieh, Jun-Ting, McKenzie, Theo, Mohanty, Sidhanth, Paredes, Pedro

“…Our main result is the first two-sided construction of imbalanced unique-neighbor expanders, meaning bipartite graphs where small sets contained in both the left and right bipartitions exhibit unique-neighbor expansion, along with algebraic properties relevant to constructing quantum codes. …”
Get full text

The energy and seidel energy of cayley graphs associated to dihedral, alternating and symmetric groups by Ahmad Fadzil, Amira Fadina

Get full text

Fine-grained dichotomies for the Tutte Plane and Boolean #CSP by Brand, C, Dell, H, Roth, M

“…The main ingredient is to prove that the number of independent sets in bipartite graphs with n vertices cannot be computed in time Open image in new window unless #ETH fails. …”