Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPresentations for Vertex Transitive Graphs
66
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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. As 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.
rate research
Read More
For a non-complete graph $Gamma$, a vertex triple $(u,v,w)$ with $v$ adjacent to both $u$ and $w$ is called a $2$-geodesic if $u eq w$ and $u,w$ are not adjacent. Then $Gamma$ is said to be $2$-geodesic transitive if its automorphism group is transitive on both arcs and 2-geodesics. In previous work the author showed that if a $2$-geodesic transitive graph $Gamma$ is locally disconnected and its automorphism group $Aut(Gamma)$ has a non-trivial normal subgroup which is intransitive on the vertex set of $Gamma$, then $Gamma$ is a cover of a smaller 2-geodesic transitive graph. Thus the `basic graphs to study are those for which $Aut(Gamma)$ acts quasiprimitively on the vertex set. In this paper, we study 2-geodesic transitive graphs which are locally disconnected and $Aut(Gamma)$ acts quasiprimitively on the vertex set. We first determine all the possible quasiprimitive action types and give examples for them, and then classify the family of $2$-geodesic transitive graphs whose automorphism group is primitive on its vertex set of $PA$ type.
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.
Let $Gamma$ denote a $Q$-polynomial distance-regular graph with vertex set $X$ and diameter $D$. Let $A$ denote the adjacency matrix of $Gamma$. Fix a base vertex $xin X$ and for $0 leq i leq D$ let $E^*_i=E^*_i(x)$ denote the projection matrix to the $i$th subconstituent space of $Gamma$ with respect to $x$. The Terwilliger algebra $T(x)$ of $Gamma$ with respect to $x$ is the semisimple subalgebra of $mathrm{Mat}_X(mathbb{C})$ generated by $A, E^*_0, E^*_1, ldots, E^*_D$. Remark that the isomorphism class of $T(x)$ depends on the choice of the base vertex $x$. We say $Gamma$ is pseudo-vertex-transitive whenever for any vertices $x,y in X$, the Terwilliger algebras $T(x)$ and $T(y)$ are isomorphic. In this paper we discuss pseudo-vertex transitivity for distance-regular graphs with diameter $Din {2,3,4}$. In the case of diameter $2$, a strongly regular graph $Gamma$ is thin, and $Gamma$ is pseudo-vertex-transitive if and only if every local graph of $Gamma$ has the same spectrum. In the case of diameter $3$, Taylor graphs are thin and pseudo-vertex-transitive. In the case of diameter $4$, antipodal tight graphs are thin and pseudo-vertex-transitive.
A graph $Gamma$ is said to be symmetric if its automorphism group $rm Aut(Gamma)$ acts transitively on the arc set of $Gamma$. In this paper, we show that if $Gamma$ is a finite connected heptavalent symmetric graph with solvable stabilizer admitting a vertex-transitive non-abelian simple group $G$ of automorphisms, then either $G$ is normal in $rm Aut(Gamma)$, or $rm Aut(Gamma)$ contains a non-abelian simple normal subgroup $T$ such that $Gleq T$ and $(G,T)$ is explicitly given as one of $11$ possible exception pairs of non-abelian simple groups. Furthermore, if $G$ is regular on the vertex set of $Gamma$ then the exception pair $(G,T)$ is one of $7$ possible pairs, and if $G$ is arc-transitive then the exception pair $(G,T)=(A_{17},A_{18})$ or $(A_{35},A_{36})$.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
