Structure and enumeration of $(3+1)$-free posets (extended abstract) by Mathieu Guay-Paquet, Alejandro H. Morales, Eric Rowland

“…We enumerate all $(3+1)$-free posets by giving a decomposition into bipartite graphs, and obtain generating functions for $(3+1)$-free posets with labelled or unlabelled vertices.…”
Get full text

Topological network entanglement as order parameter for the emergence of geometry by M Cristina Diamantini, Carlo A Trugenberger

“…As a concrete example we analyze the recently proposed model in which geometry emerges due to the condensation of 4-cycles in random regular bipartite graphs, driven by the combinatorial Ollivier–Ricci curvature. …”
Get full text

Edge-maximal -free non-bipartite Hamiltonian graphs of odd order by M. M. M. Jaradat, A. Baniabedalruhman, M. S. Bataineh, A. M. M. Jaradat, A. A. Al-Rhayyel

“…AbstractLet [Formula: see text] denote the class of non-bipartite graphs on n vertices containing no [Formula: see text]-graph and [Formula: see text] Let [Formula: see text] denote the class of non-bipartite Hamiltonian graphs on n vertices containing no [Formula: see text]-graph and [Formula: see text] In this paper we determine [Formula: see text] by proving that for sufficiently large odd n, [Formula: see text] Furthermore, the bound is best possible. …”
Get full text

A fast new algorithm for weak graph regularity by Lovász, László Miklós, Zhao, Yufei

“…The algorithm outputs an approximation of a given graph as a weighted sum of ϵ-O(1) many complete bipartite graphs. As a corollary, we give a deterministic algorithm for estimating the number of copies of H in an n-vertex graph G up to an additive error of at most ϵn v(H), in time ϵ-O H(1) n 2…”
Get full text

Tilings of a Domain on a Hexagon Mesh with Balanced 3-Tiles by Gilles Radenne

“…The first one is based on matchings in bipartite graphs, which in this case are in correspondance with tilings of domains by lozenges, and thus can be efficiently studied, using Thurston's algorithm (see [Thu90]). …”
Get full text

Optimal quantization for compressive sensing under message passing reconstruction by Kamilov, Ulugbek, Goyal, Vivek K., Rangan, Sundeep

“…GAMP is an iterative reconstruction scheme inspired by the belief propagation algorithm on bipartite graphs which generalizes approximate message passing (AMP) for arbitrary measurement channels. …”
Get full text

The Distance Magic Index of a Graph by Godinho Aloysius, Singh Tarkeshwar, Arumugam S.

“…In this paper we determine the distance magic index of trees and complete bipartite graphs.…”
Get full text

Gaussian Amplitude Amplification for Quantum Pathfinding by Daniel Koch, Massimiliano Cutugno, Samuel Karlson, Saahil Patel, Laura Wessing, Paul M. Alsing

“…We focus on the geometry of sequentially connected bipartite graphs, which naturally gives rise to solution spaces describable by Gaussian distributions. …”
Get full text

Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems by Galanis, A, Goldberg, L, Yang, K

“…Our main result shows that: (i) if every function in Γ is affine, then #CSP∆(Γ) is in FP for all ∆, (ii) otherwise, if every function in Γ is in a class called IM2, then for large ∆, #CSP∆(Γ) is equivalent under approximation-preserving reductions to the problem of counting independent sets in bipartite graphs, (iii) otherwise, for large ∆, it is NP-hard to approximate #CSP∆(Γ), even within an exponential factor.…”

Finding Dominating Induced Matchings in P9-Free Graphs in Polynomial Time by Brandstädt Andreas, Mosca Raffaele

“…The DIM problem is 𝕅𝕇-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree 3 but was solved in linear time for P7-free graphs and in polynomial time for P8-free graphs. …”
Get full text

Approximately counting locally-optimal structures by Goldberg, L, Gysel, R, Lapinskas, J

“…Assuming that #BIS is not equivalent to #SAT under AP-reductions, we show that counting maximal independent sets in bipartite graphs is harder than counting maximum independent sets. …”

Annihilating Graph of Abelian Groups by saeed safaeeyan, Soraya Barzegar

“…Among other things, we characterize Abelian groups for which their annihilating graphs are complete, bipartite or complete bipartite  graphs.…”
Get full text

A new two-variable generalization of the chromatic polynomial by Klaus Dohmen, André Poenitz, Peter Tittmann

“…We finally give explicit expressions for the generalized chromatic polynomial of complete graphs, complete bipartite graphs, paths, and cycles, and show that it can be computed in polynomial time for trees and graphs of restricted pathwidth.…”
Get full text

On interval number in cycle convexity by Julio Araujo, Guillaume Ducoffe, Nicolas Nisse, Karol Suchan

“…Then, we present some hardness results by showing that deciding whether $in_{cc} (G)$ ≤ k is NP-complete, even if G is a split graph or a bounded-degree planar graph, and that the problem is W[2]-hard in bipartite graphs when k is the parameter. As a consequence, we obtainthat $in_{cc} (G)$ cannot be approximated up to a constant factor in the classes of split graphs and bipartite graphs (unless P = N P ).On the positive side, we present polynomial-time algorithms to compute $in_{cc} (G)$ for outerplanar graphs, cobipartite graphs and interval graphs. …”
Get full text

Five results on maximizing topological indices in graphs by Stijn Cambie

“…We prove that the maximum for the difference of the Wiener index and the eccentricity is attained by the path if the order $n$ is at least $9$ and that the maximum weighted Szeged index of graphs of given order is attained by the balanced complete bipartite graphs.…”
Get full text

Modeling Information Flow in Face-to-Face Meetings while Protecting Privacy by Rudolph, Larry, Zhenghao, Chen

“…Rather than looking at graphs derived from email, on-line forums, or telephone connections, we consider sequences of bipartite graphs that represent face-to-face meetings between individuals, and define a new metric to identify the information elite individuals. …”
Get full text

On the relationship between variable Wiener index and variable Szeged index by Cambie, S, Haslegrave, J

“…They proved the weak conjecture for bipartite graphs, and the strong conjecture for trees. …”

Pattern-Avoidance in Binary Fillings of Grid Shapes (short version) by Alexey Spiridonov

“…For some shapes, fillings that avoid specific $2 \times 2$ pairs are in bijection with totally nonnegative Grassmann cells, or with acyclic orientations of bipartite graphs. We prove a number of results analogous to Wilf-equivalence for these objects ―- that is, we show that for certain classes of shapes, some pattern-avoiding fillings are equinumerous with others.…”
Get full text

Research of NP-Complete Problems in the Class of Prefractal Graphs by Rasul Kochkarov

“…As an example, algorithms for searching for spanning trees and packing bipartite graphs are proposed. The developed algorithms are polynomial and based on well-known algorithms and are used in the form of procedures. …”
Get full text

On Eccentricity Version of Zagreb Coindices by Mahdieh Azari

“…We also determine the extremal values of the second Zagreb eccentricity coindex over some specific families of graphs such as trees, unicyclic graphs, connected graphs, and connected bipartite graphs and describe the extremal graphs. Moreover, we compare the second Zagreb eccentricity coindex with the eccentric connectivity coindex and give directions for further studies.…”
Get full text