On the Classification of Arc-transitive Circulant Digraphs of Order Odd-Prime-Squared

A Cayley graph F = Cay（G, S） of a group G with respect to S is called a circulant digraph of order pk if G is a cyclic group of the same order. Investigated in this paper are the normality conditions for arc-transitive circulant （di）graphs of order p^2 and the classification of all such graphs. It is proved that any connected arc-transitive circulant digraph of order p^2 is, up to a graph isomorphism, either Kp2, G（p^2,r）, or G（p,r）[pK1], where r｜p- 1.     

One-regular Normal Cayley Graphs on Dihedral Groups of Valency 4 or 6 with Cyclic Vertex Stabilizer

A graph G is one-regular if its automorphism group Aut（G） acts transitively and semiregularly on the arc set. A Cayley graph Cay（Г, S） is normal if Г is a normal subgroup of the full automorphism group of Cay（Г, S）. Xu, M. Y., Xu, J. （Southeast Asian Bulletin of Math., 25, 355-363 （2001）） classified one-regular Cayley graphs of valency at most 4 on finite abelian groups. Marusic, D., Pisanski, T. （Croat. Chemica Acta, 73, 969-981 （2000）） classified cubic one-regular Cayley graphs on a dihedral group, and all of such graphs turn out to be normal. In this paper, we classify the 4-valent one-regular normal Cayley graphs G on a dihedral group whose vertex stabilizers in Aut（G） are cyclic. A classification of the same kind of graphs of valency 6 is also discussed.     

Metric properties of the tropical Abel–Jacobi map

Let Γ be a tropical curve (or metric graph), and fix a base point p∈Γ. We define the Jacobian group J(G) of a finite weighted graph G, and show that the Jacobian J(Γ) is canonically isomorphic to the direct limit of J(G) over all weighted graph models G for Γ. This result is useful for reducing certain questions about the Abel–Jacobi map Φ _p :Γ→J(Γ), defined by Mikhalkin and Zharkov, to purely combinatorial questions about weighted graphs. We prove that J(G) is finite if and only if the edges in each 2-connected component of G are commensurable over ℚ. As an application of our direct limit theorem, we derive some local comparison formulas between ρ and \varPhi_p^*(r){\varPhi}_{p}^{*}(\rho) for three different natural “metrics” ρ on J(Γ). One of these formulas implies that Φ _p is a tropical isometry when Γ is 2-edge-connected. Another shows that the canonical measure μ _Zh on a metric graph Γ, defined by S. Zhang, measures lengths on Φ _p (Γ) with respect to the “sup-norm” on J(Γ).     

Černý’s conjecture and group representation theory

Let us say that a Cayley graph Γ of a group G of order n is a Černy Cayley graph if every synchronizing automaton containing Γ as a subgraph with the same vertex set admits a synchronizing word of length at most (n−1)². In this paper we use the representation theory of groups over the rational numbers to obtain a number of new infinite families of Černy Cayley graphs.     

On r-recognition by prime graph of Bp(3) where p is an odd prime

Let G be a finite group. The prime graph Γ(G) of G is defined as follows. The vertices of Γ(G) are the primes dividing the order of G and two distinct vertices p and p′ are joined by an edge if there is an element in G of order pp′. We denote by k(Γ(G)) the number of isomorphism classes of finite groups H satisfying Γ(G) = Γ(H). Given a natural number r, a finite group G is called r-recognizable by prime graph if k(Γ(G)) =  r. In Shen et al. (Sib. Math. J. 51(2):244–254, 2010), it is proved that if p is an odd prime, then B _p (3) is recognizable by element orders. In this paper as the main result, we show that if G is a finite group such that Γ(G) = Γ(B _p (3)), where p > 3 is an odd prime, then G @ B_p(3){G\cong B_p(3)} or C _p (3). Also if Γ(G) = Γ(B ₃(3)), then G @ B₃(3), C₃(3), D₄(3){G\cong B_3(3), C_3(3), D_4(3)}, or G/O₂(G) @ Aut(²B₂(8)){G/O_2(G)\cong {\rm Aut}(^2B_2(8))}. As a corollary, the main result of the above paper is obtained.     

Isometric embeddings of Johnson graphs in Grassmann graphs

Let V be an n-dimensional vector space (4≤n<∞) and let G_k(V){\mathcal{G}}_{k}(V) be the Grassmannian formed by all k-dimensional subspaces of V. The corresponding Grassmann graph will be denoted by Γ _k (V). We describe all isometric embeddings of Johnson graphs J(l,m), 1<m<l−1 in Γ _k (V), 1<k<n−1 (Theorem 4). As a consequence, we get the following: the image of every isometric embedding of J(n,k) in Γ _k (V) is an apartment of G_k(V){\mathcal{G}}_{k}(V) if and only if n=2k. Our second result (Theorem 5) is a classification of rigid isometric embeddings of Johnson graphs in Γ _k (V), 1<k<n−1.     

On <Emphasis Type="Italic">k</Emphasis>-pairable graphs from trees

The concept of the k-pairable graphs was introduced by Zhibo Chen (On k-pairable graphs, Discrete Mathematics 287 (2004), 11–15) as an extension of hypercubes and graphs with an antipodal isomorphism. In the same paper, Chen also introduced a new graph parameter p(G), called the pair length of a graph G, as the maximum k such that G is k-pairable and p(G) = 0 if G is not k-pairable for any positive integer k. In this paper, we answer the two open questions raised by Chen in the case that the graphs involved are restricted to be trees. That is, we characterize the trees G with p(G) = 1 and prove that p(G □ H) = p(G) + p(H) when both G and H are trees.     

Universal lattices and unbounded rank expanders

We study the representations of non-commutative universal lattices and use them to compute lower bounds of the τ-constant for the commutative universal lattices G _d,k =SL _d (ℤ[x ₁,...,x _k ]), for d≥3 with respect to several generating sets. As an application we show that the Cayley graphs of the finite groups can be made expanders with a suitable choice of generators. This provides the first example of expander families of groups of Lie type, where the rank is not bounded and provides counter examples to two conjectures of A. Lubotzky and B. Weiss.     

A Family of Nonnormal Cayley Digraphs

We call a Cayley digraph Γ = Cay(G, S) normal for G if G _R , the right regular representation of G, is a normal subgroup of the full automorphism group Aut(Γ) of Γ. In this paper we determine the normality of Cayley digraphs of valency 2 on nonabelian groups of order 2p ² (p odd prime). As a result, a family of nonnormal Cayley digraphs is found. Received February 23, 1998, Revised September 25, 1998, Accepted October 27, 1998     

On the prime graph of <Emphasis Type="Italic">PSL</Emphasis>(2, <Emphasis Type="Italic">p</Emphasis>) where <Emphasis Type="Italic">p</Emphasis> > 3 is a prime number

Let G be a finite group. We define the prime graph Γ(G) as follows. The vertices of Γ(G) are the primes dividing the order of G and two distinct vertices p, q are joined by an edge if there is an element in G of order pq. Recently M. Hagie [5] determined finite groups G satisfying Γ(G) = Γ(S), where S is a sporadic simple group. Let p > 3 be a prime number. In this paper we determine finite groups G such that Γ(G) = Γ(PSL(2, p)). As a consequence of our results we prove that if p > 11 is a prime number and p ≢ 1 (mod 12), then PSL(2, p) is uniquely determined by its prime graph and so these groups are characterizable by their prime graph. The third author was supported in part by a grant from IPM (No. 84200024).     

Algebraic invariants for right-angled Artin groups

A finite simplicial graph Γ determines a right-angled Artin group G_Γ, with generators corresponding to the vertices of Γ, and with a relation υw=wυ for each pair of adjacent vertices. We compute the lower central series quotients, the Chen quotients, and the (first) resonance variety of G_Γ, directly from the graph Γ. Partially supported by NSF grant DMS-0311142.     

Spectral Characterization of Some Generalized Odd Graphs

Suppose G is a connected, k-regular graph such that Spec(G)=Spec(Γ) where Γ is a distance-regular graph of diameter d with parameters a ₁=a ₂=⋯=a _d−1=0 and a _d>0; i.e., a generalized odd graph, we show that G must be distance-regular with the same intersection array as that of Γ in terms of the notion of Hoffman Polynomials. Furthermore, G is isomorphic to Γ if Γ is one of the odd polygon C _2d+1, the Odd graph O _d+1, the folded (2d+1)-cube, the coset graph of binary Golay code (d=3), the Hoffman-Singleton graph (d=2), the Gewirtz graph (d=2), the Higman-Sims graph (d=2), or the second subconstituent of the Higman-Sims graph (d=2). Received: March 28, 1996 / Revised: October 20, 1997     

Adjacent strong edge colorings and total colorings of regular graphs

It is conjectured that χas(G) = χt(G) for every k-regular graph G with no C5 component (k 2). This conjecture is shown to be true for many classes of graphs, including: graphs of type 1; 2-regular, 3-regular and (|V (G)| - 2)-regular graphs; bipartite graphs; balanced complete multipartite graphs; k-cubes; and joins of two matchings or cycles.     

OD-characterization of Almost Simple Groups Related to U3（5）

Let G be a finite group with order ｜G｜=p1^α1p2^α2……pk^αk, where p1 〈 p2 〈……〈 Pk are prime numbers. One of the well-known simple graphs associated with G is the prime graph （or Gruenberg- Kegel graph） denoted .by г（G） （or GK（G））. This graph is constructed as follows： The vertex set of it is π（G） = {p1,p2,…,pk} and two vertices pi, pj with i≠j are adjacent by an edge （and we write pi - pj） if and only if G contains an element of order pipj. The degree deg（pi） of a vertex pj ∈π（G） is the number of edges incident on pi. We define D（G） ：= （deg（p1）, deg（p2）,..., deg（pk））, which is called the degree pattern of G. A group G is called k-fold OD-characterizable if there exist exactly k non- isomorphic groups H such that ｜H｜ = ｜G｜ and D（H） = D（G）. Moreover, a 1-fold OD-characterizable group is simply called OD-characterizable. Let L ：= U3（5） be the projective special unitary group. In this paper, we classify groups with the same order and degree pattern as an almost simple group related to L. In fact, we obtain that L and L.2 are OD-characterizable; L.3 is 3-fold OD-characterizable; L.S3 is 6-fold OD-characterizable.     

Packing cycles with modularity constraints

We prove that for all positive integers k, there exists an integer N =N(k) such that the following holds. Let G be a graph and let Γ an abelian group with no element of order two. Let γ: E(G)→Γ be a function from the edges of G to the elements of Γ. A non-zero cycle is a cycle C such that Σ _e∈E(C) γ(e) ≠ 0 where 0 is the identity element of Γ. Then G either contains k vertex disjoint non-zero cycles or there exists a set X ⊆ V (G) with |X| ≤N(k) such that G−X contains no non-zero cycle.     

A new characterization for some linear groups

Let G be a group and π _e (G) be the set of element orders of G. Let k ? p_e(G){k\in\pi_e(G)} and m _k be the number of elements of order k in G. Let nse(G) = {m_k|k ? p_e(G)}{{\rm nse}(G) = \{m_k|k\in\pi_e(G)\}} . In Shen et al. (Monatsh Math, 2009), the authors proved that A₄ @ PSL(2, 3), A₅ @ PSL(2, 4) @ PSL(2,5){A_4\cong {\rm PSL}(2, 3), A_5\cong \rm{PSL}(2, 4)\cong \rm{PSL}(2,5)} and A₆ @ PSL(2,9){A_6\cong \rm{PSL}(2,9)} are uniquely determined by nse(G). In this paper, we prove that if G is a group such that nse(G) = nse(PSL(2, q)), where q ? {7,8,11,13}{q\in\{7,8,11,13\}} , then G @ PSL(2,q){G\cong {PSL}(2,q)} .     

On the Edge-forwarding Indices of Frobenius Graphs

A G-Frobenius graph F, as defined by Fang, Li, and Praeger, is a connected orbital graph of a Frobenius group G = K × H with Frobenius kernel K and Frobenius complement H. F is also shown to be a Cayley graph, F = Cay（K, S） for K and some subset S of the group K. On the other hand, a network N with a routing function R, written as （N, R）, is an undirected graph N together with a routing R which consists of a collection of simple paths connecting every pair of vertices in the graph. The edge-forwarding index π（N） of a network （N, R）, defined by Heydemann, Meyer, and Sotteau, is a parameter to describe tile maximum load of edges of N. In this paper, we study the edge-forwarding indices of Frobenius graphs. In particular, we obtain the edge-forwarding index of a G-Frobenius graph F with rank（G） ≤ 50.     

The spectrum of the averaging operator for a finite homogeneous graph

We give an estimate for the spectrum of the averaging operator T₁(Γ, 1) over the radius 1 for the finite (q+1)-homogeneous quotient graph Γ/X, where X is an infinite (q+1)-homogeneous tree associated with the free group G over a finite set of generators S={x₁ ..., x_p} (2p=q+1), and Γ, a subgroup of finite index in G. T₁(Γ, 1) is defined on the subspace L²(Γ/G, 1) ⊖ E_ex, where E_ex is the subspace of eigenfunctions of T₁(Γ, 1) with eigenvalue λ such that |λ|=q+1. We present a construction of some finite homogeneous graphs such that the spectrum of their adjacency matrices can be calculated explicitly. Bibliography: 11 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 205, 1993, pp. 92–109. Translated by A. M. Nikitin.     

Removable edges in cycles of a <Emphasis Type="Italic">k</Emphasis>-connected graph

An edge e of a k-connected graph G is said to be a removable edge if G ⊖ e is still k-connected, where G ⊖ e denotes the graph obtained from G by deleting e to get G − e, and for any end vertex of e with degree k − 1 in G − e, say x, delete x, and then add edges between any pair of non-adjacent vertices in N _G−e (x). The existence of removable edges of k-connected graphs and some properties of 3-connected graphs and 4-connected graphs have been investigated. In the present paper, we investigate some properties of k-connected graphs and study the distribution of removable edges on a cycle in a k-connected graph (k ≥ 4).     

Expansion in SLd(Z/qZ), q arbitrary

Let S be a fixed finite symmetric subset of SL _d (Z), and assume that it generates a Zariski-dense subgroup G. We show that the Cayley graphs of π _q (G) with respect to the generating set π _q (S) form a family of expanders, where π _q is the projection map Z→Z/q Z.