K_s,t-saturated bipartite graphs

DOI10.1016/J.EJC.2014.10.003zbMATH Open1304.05075arXiv1402.2471OpenAlexW2593811639MaRDI QIDQ482117FDOQ482117

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

Publication date: 19 December 2014

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

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.

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

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

zbMATH Keywords

minimum number of edgesordered complete bipartite graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Cites Work

• A survey of minimum saturated graphs
• A Problem in Graph Theory
• Title not available (Why is that?)
• On a Conjecture of Erdos, Hajnal and Moon
• Title not available (Why is that?)
• Title not available (Why is that?)
• An extremal problem for sets with applications to graph theory
• Linear algebra and bootstrap percolation
• Title not available (Why is that?)
• Exact bounds for some hypergraph saturation problems

Cited In (8)

• Partite Saturation of Complete Graphs
• Saturated boundary \(k\)-alliances in graphs
• Saturation of Ordered Graphs
• Minimizing the Number of Edges in $K_{(s,t)}$-Saturated Bipartite Graphs
• \(C_4\)-saturated bipartite graphs
• \(K_{r,s}\) graph bootstrap percolation
• Minimum clique-free subgraphs of Kneser graphs
• Rainbow Saturation for Complete 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)