K_s,t-saturated bipartite graphs

DOI10.1016/J.EJC.2014.10.003MaRDI QIDQ482117zbMATH OpenOpenAlexFDO

Authors Wenying Gan, Dániel Korándi, Benny Sudakov

Publication date 19 December 2014

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

minimum number of edgesordered complete bipartite graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Abstract: An $n$-by-$n$ bipartite graph is $H$-saturated if the addition of any missing edge between its two parts creates a new copy of $H$. In 1964, ErdH{o}s, Hajnal and Moon made a conjecture on the minimum number of edges in a $K_{s,s}$-saturated bipartite graph. This conjecture was proved independently by Wessel and Bollob'as in a more general, but ordered, setting: they showed that the minimum number of edges in a $K_{(s,t)}$-saturated bipartite graph is $n^2-(n-s+1)(n-t+1)$, where $K_{(s,t)}$ is the "ordered" complete bipartite graph with $s$ vertices in the first color class and $t$ vertices in the second. However, the very natural question of determining the minimum number of edges in the unordered $K_{s,t}$-saturated case remained unsolved. This problem was considered recently by Moshkovitz and Shapira who also conjectured what its answer should be. In this short paper we give an asymptotically tight bound on the minimum number of edges in a $K_{s,t}$-saturated bipartite graph, which is only smaller by an additive constant than the conjecture of Moshkovitz and Shapira. We also prove their conjecture for $K_{2,3}$-saturation, which was the first open case.

Recommendations

• Minimizing the number of edges in \(K_{(s,t)}\)-saturated bipartite graphs
• Weak saturation numbers of complete bipartite graphs in the clique
• Minimum degree and the minimum size of \(K_2^t\)-saturated graphs
• P_m-saturated bipartite graphs with minimum size
• MinimumK_{2, 3}-Saturated Graphs

Cites work

• scientific article; zbMATH DE number 3561367 (Why is no real title available?)
• scientific article; zbMATH DE number 3239217 (Why is no real title available?)
• scientific article; zbMATH DE number 3275275 (Why is no real title available?)
• scientific article; zbMATH DE number 3050594 (Why is no real title available?)
• A Problem in Graph Theory
• A survey of minimum saturated graphs
• An extremal problem for sets with applications to graph theory
• Exact bounds for some hypergraph saturation problems
• Linear algebra and bootstrap percolation
• On a Conjecture of Erdos, Hajnal and Moon

Cited in

(11)

• Rainbow Saturation for Complete Graphs
• The saturation number of \(K_{3,3}\)
• Saturated boundary \(k\)-alliances in graphs
• A note on minimum \(K_{2,3}\)-saturated graphs
• Saturation of Ordered Graphs
• Minimum degree and the minimum size of \(K_2^t\)-saturated graphs
• C₄-saturated bipartite graphs
• Partite saturation of complete graphs
• \(K_{r,s}\) graph bootstrap percolation
• Minimizing the number of edges in \(K_{(s,t)}\)-saturated bipartite graphs
• Minimum clique-free subgraphs of Kneser graphs

This page was built for publication: \(K_{s,t}\)-saturated bipartite graphs

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