ترغب بنشر مسار تعليمي؟ اضغط هنا

Cubic vertex-transitive non-Cayley graphs of order 12p

322   0   0.0 ( 0 )
 نشر من قبل Wei-Juan Zhang
 تاريخ النشر 2017
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

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.



قيم البحث

اقرأ أيضاً

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.
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 $G$ admitting a group $H$ of automorphisms acting semi-regularly on the vertices with exactly two orbits is called a {em bi-Cayley graph/} over $H$. Such a graph $G$ is called {em normal/} if $H$ is normal in the full automorphism group of $G $, and {em normal edge-transitive/} if the normaliser of $H$ in the full automorphism group of $G$ is transitive on the edges of $G$. % In this paper, we give a characterisation of normal edge-transitive bi-Cayley graphs, %which form an important subfamily of bi-Cayley graphs, and in particular, we give a detailed description of $2$-arc-transitive normal bi-Cayley graphs. Using this, we investigate three classes of bi-Cayley graphs, namely those over abelian groups, dihedral groups and metacyclic $p$-groups. We find that under certain conditions, `normal edge-transitive is the same as `normal for graphs in these three classes. As a by-product, we obtain a complete classification of all connected trivalent edge-transitive graphs of girth at most $6$, and answer some open questions from the literature about $2$-arc-transitive, half-arc-transitive and semisymmetric graphs.
In this paper, we construct an infinite family of normal Cayley graphs, which are $2$-distance-transitive but neither distance-transitive nor $2$-arc-transitive. This answers a question raised by Chen, Jin and Li in 2019 and corrects a claim in a literature given by Pan, Huang and Liu in 2015.
We generalise the standard constructions of a Cayley graph in terms of a group presentation by allowing some vertices to obey different relators than others. The resulting notion of presentation allows us to represent every vertex transitive graph. A s an intermediate step, we prove that every countably infinite, connected, vertex transitive graph has a perfect matching. Incidentally, we construct an example of a 2-ended cubic vertex transitive graph which is not a Cayley graph, answering a question of Watkins from 1990.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا