اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدNew families of small regular graphs of girth 5
70
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this paper we are interested in the {it{Cage Problem}} that consists in constructing regular graphs of given girth $g$ and minimum order. We focus on girth $g=5$, where cages are known only for degrees $k le 7$. We construct regular graphs of girth $5$ using techniques exposed by Funk [Note di Matematica. 29 suppl.1, (2009) 91 - 114] and Abreu et al. [Discrete Math. 312 (2012), 2832 - 2842] to obtain the best upper bounds known hitherto. The tables given in the introduction show the improvements obtained with our results.
قيم البحث
اقرأ أيضاً
In this paper we obtain $(q+3)$--regular graphs of girth 5 with fewer vertices than previously known ones for $q=13,17,19$ and for any prime $q ge 23$ performing operations of reductions and amalgams on the Levi graph $B_q$ of an elliptic semiplane o
f type ${cal C}$. We also obtain a 13-regular graph of girth 5 on 236 vertices from $B_{11}$ using the same technique.
The first known families of cages arised from the incidence graphs of generalized polygons of order $q$, $q$ a prime power. In particular, $(q+1,6)$--cages have been obtained from the projective planes of order $q$. Morever, infinite families of smal
l regular graphs of girth 5 have been constructed performing algebraic operations on $mathbb{F}_q$. In this paper, we introduce some combinatorial operations to construct new infinite families of small regular graphs of girth 7 from the $(q+1,8)$--cages arising from the generalized quadrangles of order $q$, $q$ a prime power.
In this note we construct a new infinite family of $(q-1)$-regular graphs of girth $8$ and order $2q(q-1)^2$ for all prime powers $qge 16$, which are the smallest known so far whenever $q-1$ is not a prime power or a prime power plus one itself.
An induced forest of a graph G is an acyclic induced subgraph of G. The present paper is devoted to the analysis of a simple randomised algorithm that grows an induced forest in a regular graph. The expected size of the forest it outputs provides a l
ower bound on the maximum number of vertices in an induced forest of G. When the girth is large and the degree is at least 4, our bound coincides with the best bound known to hold asymptotically almost surely for random regular graphs. This results in an alternative proof for the random case.
In this paper infinite families of linear binary nested completely regular codes are constructed. They have covering radius $rho$ equal to $3$ or $4$, and are $1/2^i$-th parts, for $iin{1,ldots,u}$ of binary (respectively, extended binary) Hamming co
des of length $n=2^m-1$ (respectively, $2^m$), where $m=2u$. In the usual way, i.e., as coset graphs, infinite families of embedded distance-regular coset graphs of diameter $D$ equal to $3$ or $4$ are constructed. In some cases, the constructed codes are also completely transitive codes and the corresponding coset graphs are distance-transitive.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
