The Classification of Connected Imprimitive Arc-transitive Graphs on Zp × Zp

The term (di)graph is employed to mean that a graph in question is either a directed graph or an undirected graph. The symbol G(p, r) represents the digraph defined by Chao[1]:V(G(p,r)) = Zp, E(G(p,r)) = {(x,y)|x - y ∈ Hr}, where p is a prime, r is a positive divisor of p - 1 and Hr is the unique subgroup of order r in Aut(Zp).     

On semisymmetric cubic graphs of order 6p~2

A graph r is said to be G-semisymmetric if it is regular and there exists a subgroup G of A := Aut(Г) acting transitively on its edge set but not on its vertex set. In the case of G. = A, we call r a semisymmetric graph. The aim of this paper is to investigate (G-)semisymmetric graphs of prime degree. We give a group-theoretical construction of such graphs, and give a classification of semisymmetric cubic graphs of order 6p2 for an odd prime p.     

Tetravalent Edge-transitive Cayley Graphs of PGL （2, p）

t Let F = Cay（G, S）, R（G） be the right regular representation of G. The graph Г is called normal with respect to G, if R（G） is normal in the full automorphism group Aut（F） of F. Г is called a bi-normal with respect to G if R（G） is not normal in Aut（Г）, but R（G） contains a subgroup of index 2 which is normal in Aut（F）. In this paper, we prove that connected tetravalent edge-transitive Cayley graphs on PGL（2,p） are either normal or bi-normal when p ≠ 11 is a prime.     

Graphs on which a group of order pq acts edge-transitively

Let Γ be a finite simple undirected graph with no isolated vertices. Let p, q be prime numbers with p ≥ q. We complete the classification of the graphs on which a group of order pq acts edge-transitively. The results are the following. If Aut(Γ) contains a subgroup G of order pq that acts edge-transitively on Γ, then Γ is one of the following graphs: (1) pK 1,1 ; (2) pqK 1,1 ; (3) pK q,1 ; (4) qK p,1 (p q); (5) pC q (q 2); (6) qC p (p q); (7) C p (p q = 2); (8) C pq ; (9) (Z p , C) where C = {±rμ | μ∈ Z q } with q 2, q|(p-1) and r ≡ 1 ≡ r q (mod p); (10) K p,1 (p q); (11) a double Cayley graph B(G, C) with C = {1-r μ | μ∈ Z q } and r ≡ 1 ≡ r q (mod p); (12) K pq,1 ; or (13) K p,q .     

The automorphism group of a generalized extraspecial p-group

In this paper, the automorphism group of a generalized extraspecial p-group G is determined, where p is a prime number. Assume that |G| = p 2n+m and |ζG| = p m , where n 1 and m 2. (1) When p is odd, let Aut G G = {α∈ AutG | α acts trivially on G }. Then Aut G G⊿AutG and AutG/Aut G G≌Z p-1 . Furthermore, (i) If G is of exponent p m , then Aut G G/InnG≌Sp(2n, p) × Z p m-1 . (ii) If G is of exponent p m+1 , then Aut G G/InnG≌ (K Sp(2n-2, p))×Z p m-1 , where K is an extraspecial p-group of order p 2n-1 . In particular, Aut G G/InnG≌ Z p × Z p m-1 when n = 1. (2) When p = 2, then, (i) If G is of exponent 2 m , then AutG≌ Sp(2n, 2) × Z 2 × Z 2 m-2 . In particular, when n = 1, |AutG| = 3 · 2 m+2 . None of the Sylow subgroups of AutG is normal, and each of the Sylow 2-subgroups of AutG is isomorphic to H K, where H = Z 2 × Z 2 × Z 2 × Z 2 m-2 , K = Z 2 . (ii) If G is of exponent 2 m+1 , then AutG≌ (I Sp(2n-2, 2)) × Z 2 × Z 2 m-2 , where I is an elementary abelian 2-group of order 2 2n-1 . In particular, when n = 1, |AutG| = 2 m+2 and AutG≌ H K, where H = Z 2 × Z 2 × Z 2 m-1 , K = Z 2 .     

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.     

Typical Frobenius coverings

A covering p from a Cayley graph Cay（G, X） onto another Cay（H, Y） is called typical Frobenius if G is a Frobenius group with H as a Frobenius complement and the map p ： G →H is a group epimorphism. In this paper, we emphasize on the typical Frobenius coverings of Cay（H, Y）. We show that any typical Frobenius covering Cay（G, X） of Cay（H, Y） can be derived from an epimorphism /from G to H which is determined by an automorphism f of H. If Cay（G, X1） and Cay（G, X2） are two isomorphic typical Frobenius coverings under a graph isomorphism Ф, some properties satisfied by Фare given.     

HAMILTONIAN DECOMPOSITION OF CAYLEY GRAPHS OF ORDERS p~2 AND pq

1. IntroductionLet G be a finite group and S a subset of G such that S--1 ~ S, and 1 f S. The Cayleygraph Cay (G, S) is defined as the simple graph with V ~ G, and E = {glgZ I g,'g, or g,'g,6 S, gi, gi E G}. Cay (G, S) is vertex-transitive, and it is connected if and only if (S) = G,i.e. S is a generating set of G[1]. If G = Zn, then Cay (Zn, S) is called a circulant graph. Ithas been proved that any connected Cayley graph on a finite abelian group is hamiltonianl2].Furthermore, …     

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.     

Enumerating Abelian Typical Cube-Free Fold Coverings of a Circulant Graph

Enumerating the isomorphism or equivalence classes of several types of graph coverings is one of the central research topics in enumerative topological graph theory.A covering projection p from a Cayley graph Cay(Г,X)onto another Cayley graph Cay(Q,y)is called typical if the function p:Г→Q on the vertex sets is a group epimorphism.A typical covering is called abelian(or circulant,respectively)if its covering graph is a Cayley graph on an abelism(or a cyclic,respectively)group.Recently,the equivalence classes of connected abelian typical prime-fold coverings of a circulant graph are enumerated.As a continuation of this work,we enumerate the equivalence classes of connected abelian typical cube-free fold coverings of a circulant graph.     

RESEARCH ANNOUNCEMENTS Galos Correspondence in Field Algebra of G—spin Model

A C*-system is a pair (B, G) consisting of a unital C*-algebra B and a continuous group homomorphism α: G → Aut(B) where G is a compact group and Aut(B) the group of automor-phisms of B. If K is a normal subgroup of G and BK = {B∈ B: k(B) = B, k ∈ K}, then BK is a G-invariant C*-subalgebra of B. On the other hand, if A is a G-invariant C*-algebra with BG A B, set G (A) = {g ∈ G: g(A) = A, A ∈ A}, G (A) is a normal subgroup of G. Clearly K G(BK) and we call K Galois closed ifK = G(BK). Similarly, A BG(A) and we call A Galois closed if A = BG(A).     

Conjecture on Self Hamiltonian Path Graph

The Hamiltonian path graph H(G) of a graph G isa that graph having the samevertex set as G and in which two vertices u and v are adjacent if and only if Gcontains a Hamiltonian u - v path. A graph G is a self-Hamiltonian path graph ifG≌H(G).G. Chartrand conjecture: A graph G of order p is a self-Hamiltonian path:graph if and only if G is chord additive or G is isomorphic to one of the graphsK_p, (?)_p, C_p(p≥3),K((1/2)p, (1/2)p), and K_(p/2) (?)_(p/2),the last two for even P.     

On the spectral spread of bicyclic graphs with given girth

The spectral spread of a graph is defined to be the difference between the largest and the least eigenvalue of the adjacency matrix of the graph. A graph G is said to be bicyclic, if G is connected and |E(G)| = |V(G)|+ 1. Let B(n, g) be the set of bicyclic graphs on n vertices with girth g. In this paper some properties about the least eigenvalues of graphs are given, by which the unique graph with maximal spectral spread in B(n, g) is determined.     

Constructive characterizations of (γp,γ)- and (γp,γpr)-trees

Let G = (V,E) be a graph without isolated vertices.A set S V is a domination set of G if every vertex in V - S is adjacent to a vertex in S,that is N[S] = V.The domination number of G,denoted by γ(G),is the minimum cardinality of a domination set of G.A set S C V is a paired-domination set of G if S is a domination set of G and the induced subgraph G[S] has a perfect matching.The paired-domination number,denoted by γpr(G),is defined to be the minimum cardinality of a paired-domination set S in G.A subset S V is a power domination set of G if all vertices of V can be observed recursively by the following rules: (i) all vertices in N[S] are observed initially,and (ii) if an observed vertex u has all neighbors observed except one neighbor v,then v is observed (by u).The power domination number,denoted by γp(G),is the minimum cardinality of a power domination set of G.In this paper,the constructive characterizations for trees with γp = γ and γpr = γp are provided respectively.     

Normal edge-transitive Cayley graphs on non-abelian groups of order 4p, where p is a prime number

We determine all connected normal edge-transitive Cayley graphs on non-abelian groups with order 4p,where p is a prime number.As a consequence we prove if |G|=2δp,δ=0,1,2 and p prime,then Γ=Cay(G,S) is a connected normal 1/2 arc-transitive Cayley graph only if G=F4p,where S is an inverse closed generating subset of G which does not contain the identity element of G and F 4p is a group with presentation F4p = a,b|ap=b4=1,b-1ab=aλ,where λ2≡-1(mod p).     

Graphs on which a group of order <Emphasis Type="Italic">pq</Emphasis> acts edge-transitively

Let F be a finite simple undirected graph with no isolated vertices. Let p, q be prime numbers with p≥q. We complete the classification of the graphs on which a group of order pq acts edge-transitively. The results are the following. If Aut（Г） contains a subgroup G of order pq that acts edge-transitively on F, then F is one of the following graphs： （1） pK1,1; （2） pqK1,1; （3） pgq,1; （4） qKp,1 （p 〉 q）; （5） pCq （q 〉 2）; （6） qCp （p 〉 q）; （7） Cp （p 〉 q = 2）; （8） Cpq; （9） （Zp, C） whereC={±r^μ ｜μ∈Zq} withq〉2, q｜（p-1） and r≠1≡r^q （modp）; （10） Kp,1 （p 〉 q）; （11） a double Cayley graph B（G,C） with C = {1-r^μ ｜ μ ∈ Zq} and r≠1≡r^q （modp）; （12） Kpq,1;or （13） Kp,q.     

The Automorphism Group of a Class of Nilpotent Groups with Infinite Cyclic Derived Subgroups

The automorphism group of a class of nilpotent groups with infinite cyclic derived subgroups is determined. Let G be the direct product of a generalized extraspecial Z-group E and a free abelian group A with rank m, where E ={(1 kα_1 kα_2 ··· kα_nα_(n+1) 0 1 0 ··· 0 α_(n+2)...............000...1 α_(2n+1)000...01|αi∈ Z, i = 1, 2,..., 2 n + 1},where k is a positive integer. Let AutG G be the normal subgroup of Aut G consisting of all elements of Aut G which act trivially on the derived subgroup G of G, and AutG/ζ G,ζ GG be the normal subgroup of Aut G consisting of all central automorphisms of G which also act trivially on the center ζ G of G. Then(i) The extension 1→ Aut_(G') G→ AutG→ Aut(G')→ 1 is split.(ii) Aut_(G') G/Aut_(G/ζ G,ζ G)G≌Sp(2 n, Z) ×(GL(m, Z)■(Z~)m).(iii) Aut_(G/ζ G,ζ GG/Inn G)≌(Z_k)~(2n)⊕(Z)~(2nm).     

A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs

The metric dimension dim(G)of a graph G is the minimum number of vertices such that every vertex of G is uniquely determined by its vector of distances to the chosen vertices.The zero forcing number Z(G)of a graph G is the minimum cardinality of a set S of black vertices(whereas vertices in V(G)\S are colored white)such that V(G)is turned black after finitely many applications of"the color-change rule":a white vertex is converted black if it is the only white neighbor of a black vertex.We show that dim(T)≤Z(T)for a tree T,and that dim(G)≤Z(G)+1 if G is a unicyclic graph;along the way,we characterize trees T attaining dim(T)=Z(T).For a general graph G,we introduce the"cycle rank conjecture".We conclude with a proof of dim(T)-2≤dim(T+e)≤dim(T)+1 for e∈E(T).     

完全图与完全n部图的完全多部图分解

§ 1　IntroductionLet V(G) and E(G) be the vertex setand the edge setof a graph G,respectively.Fori=1 ,...,p,if V(Gi) V(G) ,E(Gi)∩ E(Gj) = for i≠ j,and∪pi=1 E(Gi) =E(G) ,then wecall{ G1 ,...,GP} a decomposition of G.Let[i,j] be the integer interval including i and j.Let Knbe a complete graph with the vertex set[1 ,n] .For m disjointsubsets A1 ,...Amof[1 ,n] ,let K(A1 ,...,Am) be a complete m-partite graph having partite-sets A1 ,...,Am.If| Ai| =1 ,Ai is called a S-set;otherwi…     

中心对称本原矩阵的k点指数集

Let G = (V, E) be a primitive digraph. The vertex exponent of G at a vertex v ∈ V, denoted by expG(v), is the least integer p such that there is a v → u walk of length p for each u ∈ V. We choose to order the vertices of G in the k-point exponent of G and is denoted by expG(k), 1 ≤ k ≤ n. We define the k-point exponent set E(n, k) := {expG(k)| G = G(A) with A ∈ CSP(n)}, where CSP(n) is the set of all n × n central symmetric primitive matrices and G(A) is the associated graph of the matrix A. In this paper, we describe E(n,k) for all n, k with 1 ≤ k ≤ n except n ≡ 1(mod 2) and 1 ≤ k ≤ n - 4. We also characterize the extremal graphs when k = 1.