Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the asymptotic enumeration of Cayley graphs
215
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 groups $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 non-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} rho^{-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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
