اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدInduced forests in regular graphs with large girth
110
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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 lower 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.
قيم البحث
اقرأ أيضاً
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 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.
We show that every n-vertex cubic graph with girth at least g have domination number at most 0.299871n+O(n/g)<3n/10+O(n/g).
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 girt
h $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 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
