اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe saturation number of $K_{3,3}$
96
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A graph $G$ is called $F$-saturated if $G$ does not contain $F$ as a subgraph (not necessarily induced) but the addition of any missing edge to $G$ creates a copy of $F$. The saturation number of $F$, denoted by $sat(n,F)$, is the minimum number of edges in an $n$-vertex $F$-saturated graph. Determining the saturation number of complete partite graphs is one of the most important problems in the study of saturation number. The value of $sat(n,K_{2,2})$ was shown to be $lfloorfrac{3n-5}{2}rfloor$ by Ollmann, and a shorter proof was later given by Tuza. For $K_{2,3}$, there has been a series of study aiming to determine $sat(n,K_{2,3})$ over the years. This was finally achieved by Chen who confirmed a conjecture of Bohman, Fonoberova, and Pikhurko that $sat(n, K_{2,3})= 2n-3$ for all $ngeq 5$. In this paper, we prove a conjecture of Pikhurko and Schmitt that $sat(n, K_{3,3})=3n-9$ when $n geq 9$.
قيم البحث
اقرأ أيضاً
A graph $G$ is called $C_k$-saturated if $G$ is $C_k$-free but $G+e$ not for any $ein E(overline{G})$. The saturation number of $C_k$, denoted $sat(n,C_k)$, is the minimum number of edges in a $C_k$-saturated graph on $n$ vertices. Finding the exact
values of $sat(n,C_k)$ has been one of the most intriguing open problems in extremal graph theory. In this paper, we study the saturation number of $C_6$. We prove that ${4n}/{3}-2 le sat(n,C_6) le {(4n+1)}/{3}$ for $nge9$, which significantly improves the existing lower and upper bounds for $sat(n,C_6)$.
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}$.
A tripartite-circle drawing of a tripartite graph is a drawing in the plane, where each part of a vertex partition is placed on one of three disjoint circles, and the edges do not cross the circles. The tripartite-circle crossing number of a triparti
te graph is the minimum number of edge crossings among all tripartite-circle drawings. We determine the tripartite-circle crossing number of $K_{2,2,n}$.
For a fixed graph $F$ and an integer $t$, the dfn{rainbow saturation number} of $F$, denoted by $sat_t(n,mathfrak{R}(F))$, is defined as the minimum number of edges in a $t$-edge-colored graph on $n$ vertices which does not contain a dfn{rainbow copy
} of $F$, i.e., a copy of $F$ all of whose edges receive a different color, but the addition of any missing edge in any color from $[t]$ creates such a rainbow copy. Barrus, Ferrara, Vardenbussche and Wenger prove that $sat_t(n,mathfrak{R}(P_ell))ge n-1$ for $ellge 4$ and $sat_t(n,mathfrak{R}(P_ell))le lceil frac{n}{ell-1} rceil cdot binom{ell-1}{2}$ for $tge binom{ell-1}{2}$, where $P_ell$ is a path with $ell$ edges. In this short note, we improve the upper bounds and show that $sat_t(n,mathfrak{R}(P_ell))le lceil frac{n}{ell} rceil cdot left({{ell-2}choose {2}}+4right)$ for $ellge 5$ and $tge 2ell-5$.
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 th
an 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$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
