Search

A graph is said to be uniquely hamiltonian if it has a unique hamiltonian cycle. For a natural extension of this concept to infinite graphs, we find all uniquely hamiltonian vertex‐transitive graphs with finitely many ends, and also discuss some examples with infinitely many ends. In particular, we show each nonabelian free group Fn has a Cayley graph of degree 2n+2 that has a unique hamiltonian circle. (A weaker statement had been conjectured by Georgakopoulos.) Furthermore, we prove that these Cayley graphs of Fn are outerplanar. [ABSTRACT FROM AUTHOR]

If ${\mathbf v} \in {\mathbb R}^{V(X)}$ is an eigenvector for eigenvalue $\lambda $ of a graph X and $\alpha $ is an automorphism of X , then $\alpha ({\mathbf v})$ is also an eigenvector for $\lambda $. Thus, it is rather exceptional for an eigenvalue of a vertex-transitive graph to have multiplicity one. We study cubic vertex-transitive graphs with a nontrivial simple eigenvalue, and discover remarkable connections to arc-transitivity, regular maps, and number theory. [ABSTRACT FROM AUTHOR]

In this paper, first we introduce the notion of two-sided Cayley graph of a semigroup. Then, we investigate some fundamental properties of these graphs and we use our results to give partial answers to some problems raised by Iradmusa and Praeger about two-sided group graphs (two-sided Cayley graphs of groups). Specially, as a consequence of our results, we determine all undirected two-sided Cayley graphs of groups which are connected. Furthermore, by introducing the notion of color-preserving automorphisms of a two-sided Cayley graph of a semigroup (group) and calculating them under some assumptions, we determine the family of color-vertex transitive two-sided Cayley graphs of semigroups (groups). [ABSTRACT FROM AUTHOR]

A graph Γ is called G-basic if G is quasiprimitive or bi-quasiprimitive on the vertex set of Γ , where G ⩽ Aut (Γ) . It is known that locally primitive vertex-transitive graphs are normal covers of basic ones. In this paper, a complete classification of the basic locally primitive vertex-transitive graph of order 2 p 2 is given, where p is an odd prime. [ABSTRACT FROM AUTHOR]

The k -dimensional Weisfeiler-Leman algorithm (k - WL) is a very useful combinatorial tool in graph isomorphism testing. We address the applicability of k - WL to recognition of graph properties. Let G be an input graph with n vertices. We show that, if n is prime, then vertex-transitivity of G can be seen in a straightforward way from the output of 2 - WL on G and on the vertex-individualized copies of G. This is perhaps the first non-trivial example of using the Weisfeiler-Leman algorithm for recognition of a natural graph property rather than for isomorphism testing. On the other hand, we show that, if n is divisible by 16, then k - WL is unable to distinguish between vertex-transitive and non-vertex-transitive graphs with n vertices unless k = Ω (n). Similar results are obtained for recognition of arc-transitivity. Our lower bounds are based on an analysis of the Cai-Fürer-Immerman construction, which might be of independent interest. In particular, we provide sufficient conditions under which the Cai-Fürer-Immerman graphs can be made colorless. • The Weisfeiler-Leman algorithm is used to recognize vertex-transitivity of graphs with a prime number of vertices • This is perhaps the first example of using it for recognition of a natural graph property rather than for isomorphism testing • This is no longer possible if the number of vertices is divisible by 16 • The negative result is based on an analysis of the Cai-Fürer-Immerman construction • This analysis might be of independent interest as it provides a very straight way of making the CFI graphs colorless [ABSTRACT FROM AUTHOR]

We characterize colour-preserving automorphism vertex transitivity and vertex transitivity of the Cayley graphs of all semigroups in a class of pseudo-unitary homogeneous semigroups. [ABSTRACT FROM AUTHOR]

We prove that for a sequence of finite vertex-transitive graphs of increasing sizes, the cover times are asymptotically concentrated if and only if the product of the spectral gap and the expected cover time diverges. In fact, we prove this for general reversible Markov chains under the much weaker assumption (than transitivity) that the maximal hitting time of a state is of the same order as the average hitting time. [ABSTRACT FROM AUTHOR]

The generating sets of have been enumerated which consist of integral four‐dimensional vectors with components −1, 0, 1 and allow Cayley graphs without edge intersections in a straight‐edge embedding in a four‐dimensional Euclidean space. Owing to computational restrictions the valency of enumerated graphs has been fixed to 10. Up to isomorphism 58 graphs have been found and characterized by coordination sequences, shortest cycles and automorphism groups. To compute automorphism groups, a novel strategy is introduced that is based on determining vertex stabilizers from the automorphism group of a sufficiently large finite ball cut out from an infinite graph. Six exceptional, rather 'dense' graphs have been identified which are locally isomorphic to a five‐dimensional cubic lattice within a ball of radius 10. They could be built by either interconnecting interpenetrated three‐ or four‐dimensional cubic lattices and therefore necessarily contain Hopf links between quadrangular cycles. As a consequence, a local combinatorial isomorphism does not extend to a local isotopy. [ABSTRACT FROM AUTHOR]

In this paper, we present DiscreteZOO, a project which illustrates some of the possibilities for computer-supported management of collections of finite combinatorial (discrete) objects, in particular graphs with a high degree of symmetry. DiscreteZOO encompasses a data repository, a website and a SageMath Package. [ABSTRACT FROM AUTHOR]

A Kähler graph is a compound of two graphs having a common set of vertices and is a discrete model of a Riemannian manifold equipped with magnetic fields. In this paper we study selfadjointness of adjacency operators of Kähler graphs and express their zeta functions in terms of eigenvalues of their principal and auxiliary adjacency operators when they are commutative. Also, we construct finite vertex-transitive Kähler graphs satisfying the commutativity condition. [ABSTRACT FROM AUTHOR]

In this paper, we define meta-Cayley graphs on dihedral groups. We fully determine the automorphism groups of the constructed graphs in question. Further, we prove that some of the graphs that we have constructed do not admit subgroups which act regularly on their vertex set; thus proving that they cannot be represented as Cayley graphs on groups. [ABSTRACT FROM AUTHOR]

Abstract We consider the problem of finding largest vertex-transitive graphs of given degree and diameter. Using two classical number theory results due to Niven and Erdős, we prove that for any fixed degree Δ ≥ 3 and any positive integer δ , the order of a largest vertex-transitive Δ-regular graph of diameter D differs from the Moore bound by more than δ for (asymptotically) almost all diameters D ≥ 2. We also obtain an estimate for the growth of this difference, or defect, as a function of D. [ABSTRACT FROM AUTHOR]

The total domination number of a graph G without isolated vertices is the minimum number of vertices that dominate all vertices in G . The total bondage number of G is the minimum number of edges whose removal enlarges the total domination number. In this paper, we establish a tight lower bound for the total bondage number of a vertex-transitive graph. We also obtain upper bounds for regular graphs by investigating the relation between the total bondage number and the efficient total domination. As applications, we study the total bondage numbers for some circulant graphs and toroidal meshes by characterizing the existence of efficient total dominating sets in these graphs. [ABSTRACT FROM AUTHOR]

A graph is said to be 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 equals 5, 7 or 17, and the infinite family exists if and only if p ≡ 1 (mod 4), and in this family there is a unique graph for a given order. [ABSTRACT FROM AUTHOR]

Partial cubes are graphs isometrically embeddable into hypercubes. In this article, it is proved that every cubic, vertex-transitive partial cube is isomorphic to one of the following graphs: [ABSTRACT FROM AUTHOR]

In this note, we introduce the notions of color-permutable automorphisms and color-permutable vertex-transitive Cayley graphs of semigroups. As a main result, for a finite monoid S and a generating set C of S, we explicitly determine the color-permutable automorphism group of $$\mathrm {Cay}(S,C)$$ [Theorem 1.1]. Also for a monoid S and a generating set C of S, we explicitly determine the color-preserving automorphism group (endomorphism monoid) of $$\mathrm {Cay}(S,C)$$ [Proposition 2.3 and Corollary 2.4]. Then we use these results to characterize when $$\mathrm {Cay}(S,C)$$ is color-endomorphism vertex-transitive [Theorem 3.4]. [ABSTRACT FROM AUTHOR]

It is well known that Cayley graphs of groups are automatically vertex-transitive. A pioneer result of Kelarev and Praeger implies that Cayley graphs of semigroups can be regarded as a source of possibly new vertex-transitive graphs. In this note, we consider the following problem: Is every vertex-transitive Cayley graph of a semigroup isomorphic to a Cayley graph of a group? With the help of the results of Kelarev and Praeger, we show that the vertex-transitive, connected and undirected finite Cayley graphs of semigroups are isomorphic to Cayley graphs of groups, and all finite vertex-transitive Cayley graphs of inverse semigroups are isomorphic to Cayley graphs of groups. Furthermore, some related problems are proposed. [ABSTRACT FROM AUTHOR]

In interconnection networks, matching preclusion is a measure of robustness in the event of link failure. Let G be a graph of even order. The matching preclusion number m p ( G ) is defined as the minimum number of edges whose deletion results in a graph without perfect matchings. Many interconnection networks are super matched, that is, their optimal matching preclusion sets are precisely those induced by a single vertex. In this paper, we obtain general results of vertex-transitive graphs including many known networks. A k -regular connected vertex-transitive graph of even order has matching preclusion number k and is super matched except for six classes of graphs. From this many results already known can be directly obtained and matching preclusion for some other networks, such as folded k -cube graphs, Hamming graphs and halved k -cube graphs, are derived. [ABSTRACT FROM AUTHOR]

This paper concerns finite, edge-transitive direct and strong products, as well as infinite weak Cartesian products. We prove that the direct product of two connected, non-bipartite graphs is edge-transitive if and only if both factors are edge-transitive and at least one is arc-transitive, or one factor is edge-transitive and the other is a complete graph with loops at each vertex. Also, a strong product is edge-transitive if and only if all factors are complete graphs. In addition, a connected, infinite non-trivial Cartesian product graph G is edge-transitive if and only if it is vertex-transitive and if G is a finite weak Cartesian power of a connected, edge- and vertex-transitive graph H, or if G is the weak Cartesian power of a connected, bipartite, edge-transitive graph H that is not vertex-transitive. [ABSTRACT FROM AUTHOR]

Let $$G$$ and $$G'$$ be two simple connected nontrivial graphs. Denote by $$G\Box G^{'}$$ and $$G\rho G^{'}$$ the Cartesian product and the Wreath product of $$G$$ and $$G^{'}$$ , respectively. In this paper, we will show two results: (1) if $$G^{'}$$ is a triangularly connected simple graph with $$|V(G^{'})|\ge 3$$ which is neither $$K_{2,t}^{+}$$ nor one specific graph, then $$G\Box G^{'}$$ is $$Z_{3}$$ -connected; (2) if $$G^{'}$$ is a vertex-transitive graph, then $$G\rho G^{'}$$ is $$Z_{3}$$ -connected. [ABSTRACT FROM AUTHOR]

It is shown that there are infinitely many connected vertex-transitive graphs that have no Hamilton decomposition, including infinitely many Cayley graphs of valency 6, and including Cayley graphs of arbitrarily large valency. [ABSTRACT FROM AUTHOR]

We characterize vertex-transitive median graphs of non-exponential growth as the Cartesian products of finite hypercubes with finite dimensional lattice graphs. Additionally, we prove that every median graph without convex subgraphs isomorphic to K 1 , 3 or the 4-pan graph is isomorphic to the weak Cartesian product of finite paths, rays and two way infinite paths. [ABSTRACT FROM AUTHOR]

Abstract: Let , where p is a prime and is an integer. For , let P and L be two copies of the -dimensional vector spaces over the finite field . Consider the bipartite graph with partite sets P and L defined as follows: a point is adjacent to a line if and only if the following m equalities hold: for . We call the graphs Wenger graphs. In this paper, we determine all distinct eigenvalues of the adjacency matrix of and their multiplicities. We also survey results on Wenger graphs. [Copyright &y& Elsevier]

A Cayley graph (G,S) on a group G with respect to a Cayley subset S is said to be normal if the right regular representation R(G) of G is normal in the full automorphism group of (G,S). For a positive integer n, let Γn be a graph with vertex set {xi,yi|i ∈ ℤ2n} and edge set {{xi,xi+1}, {yi,yi+1}, {x2i,y2i+1}, {y2i,x2i+1}|i ∈ ℤ2n}. In this paper, it is shown that Γn is a Cayley graph and its full automorphism group is isomorphic to for n=2, and to for n > 2. Furthermore, we determine all pairs of G and S such that Γn=(G,S) is non-normal for G. Using this, all connected cubic non-normal Cayley graphs of order 8p are constructed explicitly for each prime p. [ABSTRACT FROM AUTHOR]

A cyclic edge-cut of a graph G is an edge set, the removal of which separates two cycles. If G has a cyclic edge-cut, then it is called cyclically separable. We call a cyclically separable graph super cyclically edge-connected, in short, super- λ, if the removal of any minimum cyclic edge-cut results in a component which is a shortest cycle. In [Zhang, Z., Wang, B.: Super cyclically edge-connected transitive graphs. J. Combin. Optim., 22, 549-562 (2011)], it is proved that a connected vertex-transitive graph is super- λ if G has minimum degree at least 4 and girth at least 6, and the authors also presented a class of nonsuper- λ graphs which have degree 4 and girth 5. In this paper, a characterization of k ( k ≥ 4)-regular vertex-transitive nonsuper- λ graphs of girth 5 is given. Using this, we classify all k ( k ≥ 4)-regular nonsuper- λ Cayley graphs of girth 5, and construct the first infinite family of nonsuper- λ vertex-transitive non-Cayley graphs. [ABSTRACT FROM AUTHOR]

We give necessary and sufficient conditions for various vertex-transitivity of Cayley graphs of the class of completely 0-simple semigroups and its several subclasses. Moreover, the question when the Cayley graphs of completely 0-simple semigroups are undirected is considered. [ABSTRACT FROM AUTHOR]

Abstract: Let be a reflexive relation with a transitive automorphism group. Let F be a finite subset of V containing a fixed element v. We prove that the size of (the image of F) is at least Let be finite subsets of a group G. Applied to Cayley graphs, our result reduces to the following extension of the Scherk–Kemperman Theorem, proved by Kemperman: for every . [Copyright &y& Elsevier]

Abstract: Let be a connected graph. Then is called super restricted edge-connected, in short, sup-, if every minimum edge set of such that is disconnected and every component of has at least two vertices, the set of edges being adjacent to a certain edge with minimum edge degree in . In this paper, by studying the -superatoms of , we characterize super restricted edge-connected edge-transitive graphs. As a corollary, we present a sufficient and necessary condition for connected vertex-transitive line graphs to be super vertex-connected. [Copyright &y& Elsevier]

The subject of this paper are infinite, locally finite, vertex-transitive median graphs. It is shown that the finiteness of the Θ-classes of such graphs does not guarantee finite blocks. Blocks become finite if, in addition, no finite sequence of Θ-contractions produces new cut-vertices. It is proved that there are only finitely many vertex-transitive median graphs of given finite degree with finite blocks. An infinite family of vertex-transitive median graphs with finite intransitive blocks is also constructed and the list of vertex-transitive median graphs of degree four is presented. [ABSTRACT FROM AUTHOR]

Abstract: Having presented layered hierarchies of symmetry of vertex-transitive graphs by exploring various classes of algebraic systems, in this note we extend the class of generalised Petersen graphs into higher dimensions and show which ones are Cayley and quasi-Cayley. [Copyright &y& Elsevier]

Abstract: The results of Širáň and the first author [A construction of vertex-transitive non-Cayley graphs, Australas. J. Combin. 10 (1994) 105–114; More constructions of vertex-transitive non-Cayley graphs based on counting closed walks, Australas. J. Combin. 14 (1996) 121–132] are generalized, and new formulas for the number of closed walks of length or pq, where p and q are primes, valid for all vertex-transitive graphs are found. Based on these formulas, several simple tests for vertex-transitivity are presented, as well as lower bounds on the orders of the smallest vertex- and arc-transitive groups of automorphisms for vertex-transitive graphs of given valence. [Copyright &y& Elsevier]

Abstract: The class of all connected vertex-transitive graphs forms a metric space under a natural combinatorially defined metric. In this paper we study graphs which are limit points in this metric space of the subset consisting of all finite graphs that admit a vertex-primitive group of automorphisms. A description of these limit graphs provides a useful description of the possible local structures of generic finite graphs that admit a vertex-primitive automorphism group. We give an analysis of the possible types of these limit graphs, and suggest directions for future research. Some of the analysis relies on the finite simple group classification. [Copyright &y& Elsevier]

Abstract: Let and denote the independence number and chromatic number of a graph G, respectively. Let be the direct product graph of graphs G and H. We show that if G and H are circular graphs, Kneser graphs, or powers of cycles, then and . [Copyright &y& Elsevier]

Abstract: A homogeneous factorisation is a partition of the arc set of a digraph such that there exist vertex-transitive groups such that fixes each part of setwise while acts transitively on . Homogeneous factorisations of complete graphs have previously been studied by the second and fourth authors, and are a generalisation of vertex-transitive self-complementary digraphs. In this paper we initiate the study of homogeneous factorisations of arbitrary graphs and digraphs. We give a generic group theoretic construction and show that all homogeneous factorisations can be constructed in this way. We also show that the important homogeneous factorisations to study are those where acts transitively on the set of arcs of is a normal subgroup of and is a cyclic group of prime order. [Copyright &y& Elsevier]

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. [ABSTRACT FROM AUTHOR]

Abstract: We prove that a connected vertex-transitive graph G with degree and girth is super restricted edge-connected, that is, if F is a set of edges of G such that is disconnected and every component of has at least two vertices, then F is the set of edges adjacent to a certain edge in G. We also show that neither the condition nor can be weakened. [Copyright &y& Elsevier]

Let Γ = (Ω, E) be a connected graph. Then for each i ∈ {0, 1,...,d(Γ)}, we set Γi = {(α, β)|d(α, β) = i}. For G ≤ Aut(Γ), we say that Γ; is a G-distance transitive graph if G is transitive on each of the sets Γ0,..., Γd where d = d(Γ). If G = Aut(Γ), then we say that Γ is distance transitive. In this paper we generalized this notion as follows: Let s be a positive integer, then an s-arc in a graph Γ = (Ω, E) is an (s+ 1)-tuple (α0 ..... αs) of vertices with the property that (αi - 1, αi) ∈ E for 1 ≤ i ≤ s and αi-1 ≠ αi+l for 1 ≤ i ≤ s - 1. Further, Γ is said to be (G, s)-arc transitive if G ≤ AutΓ and G is transitive on the s-arcs of Γ. Suppose that the connected (G,s)-arc transitive graph Γ containing at least one s-arc, then either G is transitive on Ω and Γ is (G,i)-arc transitive for each i satisfying 1 ≤ i ≤ s, or Γ is a tree of diameters s, and if α = (α0, α1, .... , αs) and β = (β0, β1,..., βs) are s-arcs of Γ, then for some ω ∈ {β0, βs} and ω' ∈ {α0, αs}, d(ω, ω' = s. [ABSTRACT FROM AUTHOR]

We shall define the k-isoperimetric connectivity Ak of a regular graph F as the minimum number of arcs originating in a set with cardinality not exceeding half the order of the graph and containing at least k vertices. Clearly λk ≤ dk - ek, where d is the degree of Γ and ek is the maximal number of edges induced on a set of k vertices. We shall show that Cayley graphs with a prime order and arc-transitive graphs have λk = dk-ek, provided that d ≥ 3k - 3. We describe all vertex-transitive graphs where λ2 ≤ 2d - 3. [ABSTRACT FROM AUTHOR]