Inapproximability of the partition function for the antiferromagnetic ising and hard-core models by Galanis, A, Stefankovic, D, Vigoda, E

“…Our proof works by relating certain second moment calculations for random Δ-regular bipartite graphs to the tree recursions used to establish the critical points on the infinite tree. …”

Decomposition, approximation, and coloring of odd-minor-free graphs by Demaine, Erik D., Hajiaghayi, Mohammad Taghi, Kawarabayashi, Ken-ichi

“…The class of odd-H-minor-free graphs is a vast generalization of the well-studied H-minor-free graph families and includes, for example, all bipartite graphs plus a bounded number of apices. Odd-H-minor-free graphs are particularly interesting from a structural graph theory perspective because they break away from the sparsity of H- minor-free graphs, permitting a quadratic number of edges.…”
Get full text
Get full text

Randić energy of digraphs by Roberto Cruz, Juan Monsalve, Juan Rada

“…Also, we deduce a new upper bound for the Randić energy of graphs in terms of rank, concretely, we show that ER(G)≤rank(G) for all graphs G, and equality holds if and only if G is a disjoint union of complete bipartite graphs.…”
Get full text

Approximately Counting Locally-Optimal Structures by Goldberg, L, Gysel, R, Lapinskas, J

“…Motivated by the difficulty of approximately counting maximal independent sets in bipartite graphs, we also study counting problems involving minimal separators and minimal edge separators (which are also locally-optimal structures). …”

Counting and finding homomorphisms is universal for parameterized complexity theory by Roth, M, Wellnitz, P

“…As a special case, we obtain an easy proof of the parameterized intractability result of the problem of counting k-matchings in bipartite graphs. …”

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

“…The respected Cayley graphs are found and represented as the union of complete graphs, cycle graphs, and complete bipartite graphs. The obtained graphs are then mapped onto their adjacency matrix and Seidel matrix respectively to obtain the eigenvalues and Seidel eigenvalues of the graphs. …”
Get full text

Revealing proteome-level functional redundancy in the human gut microbiome using ultra-deep metaproteomics by Leyuan Li, Tong Wang, Zhibin Ning, Xu Zhang, James Butcher, Joeselle M. Serrana, Caitlin M. A. Simopoulos, Janice Mayne, Alain Stintzi, David R. Mack, Yang-Yu Liu, Daniel Figeys

“…Ultra-deep metaproteomics reveals high proteome-level functional redundancy and high nestedness in the human gut proteomic content networks (i.e., the bipartite graphs connecting taxa to functions). We find that the nested topology of proteomic content networks and relatively small functional distances between proteomes of certain pairs of taxa together contribute to high $${{{{{{\rm{FR}}}}}}}_{p}$$ FR p in the human gut microbiome. …”
Get full text

Color code techniques in rainbow connection by Fendy Septyanto, Kiki A. Sugeng

“…In this paper we generalize the notion of “color codes” that was originally used by Chartrand et al. in their study of the rc and src of complete bipartite graphs, so that it now applies to any connected graph. …”
Get full text

ON SOME VERTEX-TRANSITIVE DISTANCE-REGULAR ANTIPODAL COVERS OF COMPLETE GRAPHS by Ludmila Yu. Tsiovkina

“…Earlier, it was shown that the family of non-bipartite graphs \(\Gamma\) with the property \((*)\) such that \(rk(\widetilde{G}^{\Sigma})=3\) and the socle of \(\widetilde{G}^{\Sigma}\) is a sporadic or an alternating group is finite and limited to a small number of potential examples. …”
Get full text

Impact of technology readiness in the development of automotive systems when incorporating new styling : a graph theory approach to OPM hierarchical decomposition of the system's a... by Rodríguez Sánchez, Fernando

Get full text

Bipartite Perfect Matching in Pseudo-Deterministic NC by Goldwasser, Shafi, Grossman, Ofer

“…We present a pseudo-deterministic NC algorithm for finding perfect matchings in bipartite graphs. Specifically, our algorithm is a randomized parallel algorithm which uses poly(n) processors, poly(log n) depth, poly(log n) random bits, and outputs for each bipartite input graph a unique perfect matching with high probability. …”
Get full text

Inapproximability of counting hypergraph colourings by Galanis, A, Guo, H, Wang, J

“…This allows us to utilise reduction techniques available for the graph case, which hinge upon understanding the behaviour on random regular bipartite graphs that serve as gadgets in the reduction. …”

Total Perfect Roman Domination by Ahlam Almulhim

“…We proved that total perfect Roman domination is NP-complete for chordal graphs, bipartite graphs, and for planar bipartite graphs. Finally, we related <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msubsup><mi>γ</mi><mrow><mi>t</mi><mi>R</mi></mrow><mi>p</mi></msubsup><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> to perfect domination <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msup><mi>γ</mi><mi>p</mi></msup><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> by proving <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msubsup><mi>γ</mi><mrow><mi>t</mi><mi>R</mi></mrow><mi>p</mi></msubsup><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>≤</mo><mn>3</mn><msup><mi>γ</mi><mi>p</mi></msup><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> for every graph <i>G</i>, and we characterized trees <i>T</i> of order <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>≥</mo><mn>3</mn></mrow></semantics></math></inline-formula> for which <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msubsup><mi>γ</mi><mrow><mi>t</mi><mi>R</mi></mrow><mi>p</mi></msubsup><mrow><mo>(</mo><mi>T</mi><mo>)</mo></mrow><mo>=</mo><mn>3</mn><msup><mi>γ</mi><mi>p</mi></msup><mrow><mo>(</mo><mi>T</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>. …”
Get full text

Seascape connectivity: ontogenetic migration for Haemulon flavolineatum by Diana Carolina Rodriguez-Torres, Alberto Acosta

“…With published information on the H. flavolineatum home range and its ontogenetic migration distances, we estimated the potential functional connectivity (CONNECT and migration distances) between ecosystems by building bipartite graphs. The benthic habitat configuration of the BPK could allow Haemulon flavolineatum to complete at least two stages of its life cycle (stage 5 mangroves to reefs being more likely than stage 4 seagrass to mangroves). …”
Get full text

Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems by Salvatore Mandrà, Gian Giacomo Guerreschi, Alán Aspuru-Guzik

“…The same worst-case complexity holds for $(3,3)$ -regular bipartite graphs. As a reference, the current best classical algorithm has a (worst-case) running time bounded by $O({2}^{31n/96})$ . …”
Get full text

Stacks, Queues and Tracks: Layouts of Graph Subdivisions by Vida Dujmović, David R. Wood

“…Finally, we establish a tight relationship between queue layouts and so-called 2-track thickness of bipartite graphs. \par…”
Get full text

Matchings, matroids and submodular functions by Harvey, Nicholas James Alexander

Get full text

Some variations of the commutativity degree of some groups and their applications in graph theory by Alrehaili, Suad

“…These graphs are found to be either empty graphs, complete graphs or bipartite graphs. Finally, several algebraic properties of these order commuting graphs are determined including the degrees of the vertices, graphs independence number, chromatic number, clique number, diameter and girth.…”
Get full text

Usefulness of Vaccine Adverse Event Reporting System for Machine-Learning Based Vaccine Research: A Case Study for COVID-19 Vaccines by James Flora, Wasiq Khan, Jennifer Jin, Daniel Jin, Abir Hussain, Khalil Dajani, Bilal Khan

“…Differences in results after applying various machine learning algorithms (association rule mining, self-organizing maps, hierarchical clustering, bipartite graphs) on VAERS data were noticed. Moderna reports showed <i>injection-site</i>-related AEs of higher frequencies by 15.2%, consistent with the online survey (12% higher reporting rate for <i>pain in the muscle</i> for Moderna compared to Pfizer-BioNTech). …”
Get full text

On the complexity of some hop domination parameters by Nader Jafari Rad, Elahe Shabani

“…In this paper, we study the complexity of the hop independent dominating problem, the hop Roman domination function problem and the hop Roman independent domination function problem, and show that the decision problem for each of the above three problems is NP-complete even when restricted to planar bipartite graphs or planar chordal graphs.</p>…”
Get full text