Concatenating bipartite graphs

DOI10.37236/8451MaRDI QIDQ2144334zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, Patrick Hompe, Sophie Spirkl, Alex Scott, Paul Seymour

Publication date 13 June 2022

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1902.10878

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

directed bipartite graphstripartite digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

Abstract: Let $x,yin(0,1]$ and let $A,B,C$ be disjoint nonempty subsets of a graph $G$, where every vertex in $A$ has at least $x|B|$ neighbours in $B$, and every vertex in $B$ has at least $y|C|$ neighbours in $C$. We denote by $phi(x,y)$ the maximum $z$ such that, in all such graphs $G$, there is a vertex $v$ in $C$ that is joined to at least $z|A|$ vertices in $A$ by two-edge paths. The function $phi$ is interesting, and we investigate some of its properties. For instance, we show that it is symmetric in $x$ and $y$, and that it has a discontinuity at $x=y=1/k$ for all integers $k>1$. We raise a number of questions and conjectures.

Recommendations

• scientific article; zbMATH DE number 4160792
• Bipartite subgraphs
• Bipartite subgraphs of graphs with maximum degree three
• Bipartite graphs with balanced \((a,b)\)-partitions
• A correlation inequality for bipartite graphs

Cites work

• scientific article; zbMATH DE number 3630786 (Why is no real title available?)
• Abschätzung der asymptotischen Dichte von Summenmengen
• Maximum induced trees in graphs
• Short directed cycles in bipartite digraphs

This page was built for publication: Concatenating bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2144334)