Mobility of vertex-transitive graphs

We define the mobility of a graph automorphism as the minimum distance between a vertex of the graph and its image under the automorphism, and the absolute mobility of a graph as the maximum of the mobilities of its automorphisms. In this paper, we investigate the mobility of certain classes of graphs, in particular, Cartesian and lexicographic products, vertex-transitive graphs, and Cayley graphs.     

The vertex-transitive TLF-planar graphs

We consider the class of the topologically locally finite (in short TLF) planar vertex-transitive graphs. We characterize these graphs by finite combinatorial objects called labeling schemes. As a result, we are able to enumerate and describe all TLF-planar vertex-transitive graphs of given degree, as well as most of their transitive groups of automorphisms. In addition,we are able to decide whether a given TLF-planar transitive graph is Cayley or not. This class contains all the one-ended planar Cayley graphs and the normal transitive tilings of the plane.     

Vertex-transitive graphs: Symmetric graphs of prime valency

Let G be a group acting symmetrically on a graph Σ, let G₁ be a subgroup of G minimal among those that act symmetrically on Σ, and let G₂ be a subgroup of G₁ maximal among those normal subgroups of G₁ which contain no member except 1 which fixes a vertex of Σ. The most precise result of this paper is that if Σ has prime valency p, then either Σ is a bipartite graph or G₂ acts regularly on Σ or G₁ | G₂ is a simple group which acts symmetrically on a graph of valency p which can be constructed from Σ and does not have more vertices than Σ. The results on vertex-transitive groups necessary to establish results like this are also included.     

Structure of vertex-transitive graphs

Every vertex-transitive graph has a characteristic structure. The specific details of structure of a vertex-transitive graph are closely related to the configuration of the parts of any minimum separating set of that graph. It is shown for a vertex-transitive graph G that (i) the number n of isomorphic atomic parts admitted by any minimum separating set S is unique for that G; (ii) G is then isomorphic to a disjoint union of m(≥2) copies of such a set of n atomic parts together with some additional edges joining them; (iii) any minimum separating set S of G consists of the vertex set of the union of some k(≥1) copies of the set of n atomic parts; (iv) at most one nonatomic part will be admitted in conjunction with one or more atomic parts by any minimum separating set of G.This configuration of structure extends to nonatomic parts. A vertex-transitive graph G may contain a not necessarily unique minimum separating set S which admits t(≥3) nonatomic parts. Then it is shown that (i) some (t ? 1)-set of these nonatomic parts are pairwise isomorphic; (ii) if the remaining nonatomic part is nonisomorphic to the others then it contains more vertices than the other parts; (iii) G is isomorphic to a disjoint union of d(≥2) copies of the set of q(≥t ? 1) isomorphic nonatomic parts together with some additional edges joining them; (iv) a minimum separating set S consists of the vertex set of the union of some y(≥1) copies of the set of q isomorphic nonatomic parts. For the case of t = 2 non-atomic parts admitted by a minimum separating set S, counterexamples of (iii) and (iv) are given.     

On self-complementary vertex-transitive graphs

In this paper we study the problem of determining positive integers n for which there exist self-complementary vertex-transitive graphs of order n. The main aim of this paper is to prove that, for distinct primes p, q, there exist self-complementary vertex-transitive graphs of order pq if and only if p, q Scz.tbnd;1 (mod 4). This provides negative answers to a long-standing open question proposed by Zelinka (1979) and a recent open question proposed by Froncek, Rosa Siran (1996).     

Strong cliques in vertex-transitive graphs

A clique (resp, independent set) in a graph is strong if it intersects every maximal independent set (resp, every maximal clique). A graph is clique intersect stable set (CIS) if all of its maximal cliques are strong and localizable if it admits a partition of its vertex set into strong cliques. In this paper we prove that a clique $C$ in a vertex-transitive graph $\mathrm{\Gamma }$ is strong if and only if $\text{◂=▸}\text{◂⋅▸}\mid C\mid \mid I\mid =\mid V\left(\mathrm{\Gamma }\right)\mid$ for every maximal independent set $I$ of $\mathrm{\Gamma }$. On the basis of this result we prove that a vertex-transitive graph is CIS if and only if it admits a strong clique and a strong independent set. We classify all vertex-transitive graphs of valency at most 4 admitting a strong clique, and give a partial characterization of 5-valent vertex-transitive graphs admitting a strong clique. Our results imply that every vertex-transitive graph of valency at most 5 that admits a strong clique is localizable. We answer an open question by providing an example of a vertex-transitive CIS graph which is not localizable.     

Pentavalent vertex-transitive diameter two graphs

We classify the family of pentavalent vertex-transitive graphs Γ with diameter 2. Suppose that the automorphism group of Γ is transitive on the set of ordered distance 2 vertex pairs. Then we show that either Γ is distance-transitive or Γ is one of \(\overline {{C_8}} ,{\kern 1pt} {K_5}\square {K_2},{\kern 1pt} {C_5}\left[ {{K_2}} \right],{\kern 1pt} \overline {2{C_4}} ,{\kern 1pt} or{\kern 1pt} {K_3}\square {K_4}\).     

Distance degrees of vertex-transitive graphs

In [4], a lower bound of distance degrees of distance degree regular graphs is obtained. In this paper, we prove that a lower bound will be improved in some cases of vertex-transitive graphs.     

Long cycles in vertex-transitive graphs

We prove that every connected vertex-transitive graph on n ≥ 4 vertices has a cycle longer than (3n)^1/2. The correct order of magnitude of the longest cycle seems to be a very hard question.     

Vertex-transitive graphs that are not Cayley graphs. II

The Petersen graph on 10 vertices is the smallest example of a vertex-transitive graph that is not a Cayley graph. In 1983, D. Marus˘ic˘ asked, “For what values of n does there exist such a graph on n vertices?” We give several new constructions of families of vertex-transitive graphs that are not Cayley graphs and complete the proof that, if n is divisible by p² for some prime p, then there is a vertex-transitive graph on n vertices that is not a Cayley graph unless n is p², p³, or 12. © 1996 John Wiley & Sons, Inc.     

Multiples of left loops and vertex-transitive graphs

Via representation of vertex-transitive graphs on groupoids, we show that left loops with units are factors of groups, i.e., left loops are transversals of left cosets on which it is possible to define a binary operation which allows left cancellation.     

Super s-restricted edge-connectivity of vertex-transitive graphs

Let G be a connected graph with vertex-set V(G)and edge-set E(G).A subset F of E(G)is an s-restricted edge-cut of G if G-F is disconnected and every component of G-F has at least s vertices.Letλs(G)be the minimum size of all s-restricted edge-cuts of G andξs(G)=min{|[X,V(G)\X]|:|X|=s,G[X]is connected},where[X,V(G)\X]is the set of edges with exactly one end in X.A graph G with an s-restricted edge-cut is called super s-restricted edge-connected,in short super-λs,ifλs(G)=ξs(G)and every minimum s-restricted edge-cut of G isolates one component G[X]with|X|=s.It is proved in this paper that a connected vertex-transitive graph G with degree k5 and girth g5 is super-λs for any positive integer s with s 2g or s 10 if k=g=6.     

Cubic vertex-transitive graphs of girth six

In this paper, a complete classification of finite simple cubic vertex-transitive graphs of girth 6 is obtained. It is proved that every such graph, with the exception of the Desargues graph on 20 vertices, is either a skeleton of a hexagonal tiling of the torus, the skeleton of the truncation of an arc-transitive triangulation of a closed hyperbolic surface, or the truncation of a 6-regular graph with respect to an arc-transitive dihedral scheme. Cubic vertex-transitive graphs of girth larger than 6 are also discussed.     

The Hadwiger number of infinite vertex-transitive graphs

We prove that every infinite, locally finite 3-connected, almost 4-connected, almost transitive, nonplanar graph, which contains infinitely many pairwise disjoint infinite paths belonging to the same end, can be contracted into an infinite complete graph. This implies that every infinite, locally finite, connected, nonplanar vertex-transitive graph with only one end can be contracted into an infinite complete graph. This problem was raised by L. Babai.     

A characterization of locally finite vertex-transitive graphs

A locally finite graph G with no isolated vertices is vertex-transitive if and only if all its vertex-deleted subgraphs G-v are isomorphic.     

On the structure of infinite vertex-transitive graphs

A characterization of all vertex-transitive graphs Γ of connectivity l is given in terms of the lobe structure of Γ. Among these, all graphs are determined whose automorphism groups act primitively (respectively, regularly) on the vertex set.