اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدMixed Cages: monotony, connectivity and upper bounds
62
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A emph{$[z, r; g]$-mixed cage} is a mixed graph $z$-regular by arcs, $r$-regular by edges, with girth $g$ and minimum order. %In this paper we study structural properties of mixed cages: Let $n[z,r;g]$ denote the order of a $[z,r;g]$-mixed cage. In this paper we prove that $n[z,r;g]$ is a monotonicity function, with respect of $g$, for $zin {1,2}$, and we use it to prove that the underlying graph of a $[z,r;g]$-mixed cage is 2-connected, for $zin {1,2}$. We also prove that $[z,r;g]$-mixed cages are strong connected. We present bounds of $n[z,r;g]$ and constructions of $[z,r;5]$-mixed graphs and show a $[10,3;5]$-mixed cage of order $50$.
قيم البحث
اقرأ أيضاً
We introduce the notion of a $[z, r; g]$-mixed cage. A $[z, r; g]$-mixed cage is a mixed graph $G$, $z$-regular by arcs, $r$-regular by edges, with girth $g$ and minimum order. In this paper we prove the existence of $[z, r ;g]$-mixed cages and exhib
it families of mixed cages for some specific values. We also give lower and upper bounds for some choices of $z, r$ and $g$. In particular we present the first results on $[z,r;g]$- mixed cages for $z=1$ and any $rgeq 1$ and $ggeq 3$, and for any $zgeq 1$, $r=1$ and $g=4$.
In 1992, Kalai and Kleitman proved a quasipolynomial upper bound on the diameters of convex polyhedra. Todd and Sukegawa-Kitahara proved tail-quasipolynomial bounds on the diameters of polyhedra. These tail bounds apply when the number of facets is g
reater than a certain function of the dimension. We prove tail-quasipolynomial bounds on the diameters of polytopes and normal simplicial complexes. We also prove tail-polynomial upper bounds on the diameters of polyhedra.
A $t$-bar visibility representation of a graph assigns each vertex up to $t$ horizontal bars in the plane so that two vertices are adjacent if and only if some bar for one vertex can see some bar for the other via an unobstructed vertical channel of
positive width. The least $t$ such that $G$ has a $t$-bar visibility representation is the bar visibility number of $G$, denoted by $b(G)$. We show that if $H$ is a spanning subgraph of $G$, then $b(H)le b(G)+1$. It follows that $b(G)le lceil n/6rceil+1$ when $G$ is an $n$-vertex graph. This improves the upper bound obtained by Chang et al. (SIAM J. Discrete Math. 18 (2004) 462).
The permanent of a multidimensional matrix is the sum of products of entries over all diagonals. By Mincs conjecture, there exists a reachable upper bound on the permanent of 2-dimensional (0,1)-matrices. In this paper we obtain some generalizations
of Mincs conjecture to the multidimensional case. For this purpose we prove and compare several bounds on the permanent of multidimensional (0,1)-matrices. Most estimates can be used for matrices with nonnegative bounded entries.
We give upper bounds on the order of the automorphism group of a simple graph
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
