Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA construction of small (q-1)-regular graphs of girth 8
178
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
Let $q$ be a prime power; $(q+1,8)$-cages have been constructed as incidence graphs of a non-degenerate quadric surface in projective 4-space $P(4, q)$. The first contribution of this paper is a construction of these graphs in an alternative way by means of an explicit formula using graphical terminology. Furthermore by removing some specific perfect dominating sets from a $(q+1,8)$-cage we derive $k$-regular graphs of girth 8 for $k= q-1$ and $k=q$, having the smallest number of vertices known so far.
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 small 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 of type ${cal C}$. We also obtain a 13-regular graph of girth 5 on 236 vertices from $B_{11}$ using the same technique.
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.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
