اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe Tripartite-Circle Crossing Number of $K_{2,2,n}$
133
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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 tripartite 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}$.
قيم البحث
اقرأ أيضاً
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. We present upper and lower bounds on the minimum nu
mber of crossings in tripartite-circle drawings of $K_{m,n,p}$ and the exact value for $K_{2,2,n}$. In contrast to 1- and 2-circle drawings, which may attain the Harary-Hill bound, our results imply that balanced restricted 3-circle drawings of the complete graph are not optimal.
We bound the number of minimal hypergraph transversals that arise in tri-partite 3-uniform hypergraphs, a class commonly found in applications dealing with data. Let H be such a hypergraph on a set of vertices V. We give a lower bound of 1.4977 |V | and an upper bound of 1.5012 |V | .
A frequency $n$-cube $F^n(4;2,2)$ is an $n$-dimensional $4$-by-...-by-$4$ array filled by $0$s and $1$s such that each line contains exactly two $1$s. We classify the frequency $4$-cubes $F^4(4;2,2)$, find a testing set of size $25$ for $F^3(4;2,2)$,
and derive an upper bound on the number of $F^n(4;2,2)$. Additionally, for any $n$ greater than $2$, we construct an $F^n(4;2,2)$ that cannot be refined to a latin hypercube, while each of its sub-$F^{n-1}(4;2,2)$ can. Keywords: frequency hypercube, frequency square, latin hypercube, testing set, MDS code
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 e
dges 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$.
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}$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
