ترغب بنشر مسار تعليمي؟ اضغط هنا

Minimizing the number of edges in $K_{s,t}$-saturated bipartite graphs

261   0   0.0 ( 0 )
 نشر من قبل Debsoumya Chakraborti
 تاريخ النشر 2020
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

This paper considers an edge minimization problem in saturated bipartite graphs. An $n$ by $n$ bipartite graph $G$ is $H$-saturated if $G$ does not contain a subgraph isomorphic to $H$ but adding any missing edge to $G$ creates a copy of $H$. More than half a century ago, Wessel and Bollobas independently solved the problem of minimizing the number of edges in $K_{(s,t)}$-saturated graphs, where $K_{(s,t)}$ is the `ordered complete bipartite graph with $s$ vertices from the first color class and $t$ from the second. However, the very natural `unordered analogue of this problem was considered only half a decade ago by Moshkovitz and Shapira. When $s=t$, it can be easily checked that the unordered variant is exactly the same as the ordered case. Later, Gan, Korandi, and Sudakov gave an asymptotically tight bound on the minimum number of edges in $K_{s,t}$-saturated $n$ by $n$ bipartite graphs, which is only smaller than the conjecture of Moshkovitz and Shapira by an additive constant. In this paper, we confirm their conjecture for $s=t-1$ with the classification of the extremal graphs. We also improve the estimates of Gan, Korandi, and Sudakov for general $s$ and $t$, and for all sufficiently large $n$.



قيم البحث

اقرأ أيضاً

A graph $G$ is $F$-saturated if it contains no copy of $F$ as a subgraph but the addition of any new edge to $G$ creates a copy of $F$. We prove that for $s geq 3$ and $t geq 2$, the minimum number of copies of $K_{1,t}$ in a $K_s$-saturated graph is $Theta ( n^{t/2})$. More precise results are obtained when $t = 2$ where the problem is related to Moore graphs with diameter 2 and girth 5. We prove that for $s geq 4$ and $t geq 3$, the minimum number of copies of $K_{2,t}$ in an $n$-vertex $K_s$-saturated graph is at least $Omega( n^{t/5 + 8/5})$ and at most $O(n^{t/2 + 3/2})$. These results answer a question of Chakraborti and Loh. General estimates on the number of copies of $K_{a,b}$ in a $K_s$-saturated graph are also obtained, but finding an asymptotic formula remains open.
103 - V. Nikiforov 2021
Write $rholeft( Gright) $ for the spectral radius of a graph $G$ and $S_{n,r}$ for the join $K_{r}veeoverline{K}_{n-r}.$ Let $n>rgeq2$ and $G$ be a $K_{r+1}$-saturated graph of order $n.$ Recently Kim, Kim, Kostochka, and O determined exactly the minimum value of $rholeft( Gright) $ for $r=2$, and found an asymptotically tight bound on $rholeft( Gright) $ for $rgeq3.$ They also conjectured that [ rholeft( Gright) >rholeft( S_{n,r-1}right) , ] unless $G=S_{n,r-1}.$ In this note their conjecture is proved.
For a graph $H$, a graph $G$ is $H$-saturated if $G$ does not contain $H$ as a subgraph but for any $e in E(overline{G})$, $G+e$ contains $H$. In this note, we prove a sharp lower bound for the number of paths and walks on length $2$ in $n$-vertex $K _{r+1}$-saturated graphs. We then use this bound to give a lower bound on the spectral radii of such graphs which is asymptotically tight for each fixed $r$ and $ntoinfty$.
299 - Xiaolan Hu , Xing Peng 2021
For a simple graph $G$, let $chi_f(G)$ be the fractional chromatic number of $G$. In this paper, we aim to establish upper bounds on $chi_f(G)$ for those graphs $G$ with restrictions on the clique number. Namely, we prove that for $Delta geq 4$, if $ G$ has maximum degree at most $Delta$ and is $K_{Delta}$-free, then $chi_f(G) leq Delta-tfrac{1}{8}$ unless $G= C^2_8$ or $G = C_5boxtimes K_2$. This im proves the result in [King, Lu, and Peng, SIAM J. Discrete Math., 26(2) (2012), pp. 452-471] for $Delta geq 4$ and the result in [Katherine and King, SIAM J.Discrete Math., 27(2) (2013), pp. 1184-1208] for $Delta in {6,7,8}$.
246 - Matthew Wales 2021
The Hadwiger number $h(G)$ is the order of the largest complete minor in $G$. Does sufficient Hadwiger number imply a minor with additional properties? In [2], Geelen et al showed $h(G)geq (1+o(1))ctsqrt{ln t}$ implies $G$ has a bipartite subgraph with Hadwiger number at least $t$, for some explicit $csim 1.276dotsc$. We improve this to $h(G) geq (1+o(1))tsqrt{log_2 t}$, and provide a construction showing this is tight. We also derive improved bounds for the topological minor variant of this problem.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا