اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn the asymptotic enumeration of Cayley graphs
215
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this paper we are interested in the asymptotic enumeration of Cayley graphs. It has previously been shown that almost every Cayley digraph has the smallest possible automorphism group: that is, it is a digraphical regular representation (DRR). In this paper, we approach the corresponding question for undirected Cayley graphs. The situation is complicated by the fact that there are two infinite families of groups that do not admit any graphical regular representation (GRR). The strategy for digraphs involved analysing separately the cases where the regular group $R$ has a nontrivial proper normal subgroup $N$ with the property that the automorphism group of the digraph fixes each $N$-coset setwise, and the cases where it does not. In this paper, we deal with undirected graphs in the case where the regular group has such a nontrivial proper normal subgroup.
قيم البحث
اقرأ أيضاً
Following a problem posed by Lovasz in 1969, it is believed that every connected vertex-transitive graph has a Hamilton path. This is shown here to be true for cubic Cayley graphs arising from groups having a $(2,s,3)$-presentation, that is, for grou
ps $G=la a,b| a^2=1, b^s=1, (ab)^3=1, etc. ra$ generated by an involution $a$ and an element $b$ of order $sgeq3$ such that their product $ab$ has order 3. More precisely, it is shown that the Cayley graph $X=Cay(G,{a,b,b^{-1}})$ has a Hamilton cycle when $|G|$ (and thus $s$) is congruent to 2 modulo 4, and has a long cycle missing only two vertices (and thus necessarily a Hamilton path) when $|G|$ is congruent to 0 modulo 4.
We prove an upper bound on the number of pairwise strongly cospectral vertices in a normal Cayley graph, in terms of the multiplicities of its eigenvalues. We use this to determine an explicit bound in Cayley graphs of $mathbb{Z}_2^d$ and $mathbb{Z}_
4^d$. We also provide some infinite families of Cayley graphs of $mathbb{Z}_2^d$ with a set of four pairwise strongly cospectral vertices and show that such graphs exist in every dimension.
In 2011, Fang et al. in (J. Combin. Theory A 118 (2011) 1039-1051) posed the following problem: Classify non-normal locally primitive Cayley graphs of finite simple groups of valency $d$, where either $dleq 20$ or $d$ is a prime number. The only case
for which the complete solution of this problem is known is of $d=3$. Except this, a lot of efforts have been made to attack this problem by considering the following problem: Characterize finite nonabelian simple groups which admit non-normal locally primitive Cayley graphs of certain valency $dgeq4$. Even for this problem, it was only solved for the cases when either $dleq 5$ or $d=7$ and the vertex stabilizer is solvable. In this paper, we make crucial progress towards the above problems by completely solving the second problem for the case when $dgeq 11$ is a prime and the vertex stabilizer is solvable.
A graph is said to be {em vertex-transitive non-Cayley} if its full automorphism group acts transitively on its vertices and contains no subgroups acting regularly on its vertices. In this paper, a complete classification of cubic vertex-transitive n
on-Cayley graphs of order $12p$, where $p$ is a prime, is given. As a result, there are $11$ sporadic and one infinite family of such graphs, of which the sporadic ones occur when $p=5$, $7$ or $17$, and the infinite family exists if and only if $pequiv1 (mod 4)$, and in this family there is a unique graph for a given order.
Building on previous work by the present authors [Proc. London Math. Soc. 119(2):358--378, 2019], we obtain a precise asymptotic estimate for the number $g_n$ of labelled 4-regular planar graphs. Our estimate is of the form $g_n sim gcdot n^{-7/2} rh
o^{-n} n!$, where $g>0$ is a constant and $rho approx 0.24377$ is the radius of convergence of the generating function $sum_{nge 0}g_n x^n/n!$, and conforms to the universal pattern obtained previously in the enumeration of planar graphs. In addition to analytic methods, our solution needs intensive use of computer algebra in order to work with large systems of polynomials equations. In particular, we use evaluation and Lagrange interpolation in order to compute resultants of multivariate polynomials. We also obtain asymptotic estimates for the number of 2- and 3-connected 4-regular planar graphs, and for the number of 4-regular simple maps, both connected and 2-connected.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
