P Kulasinghe and S Bettayeb showed that any multiply-twisted hypercube withfive or more dimensions is not vertex-transitive. This note shows that any multiply-twistedhypercube with four or less dimensions is vertex-tr...P Kulasinghe and S Bettayeb showed that any multiply-twisted hypercube withfive or more dimensions is not vertex-transitive. This note shows that any multiply-twistedhypercube with four or less dimensions is vertex-transitive, and that any multiply-twistedhypercube with three or larger dimensions is not edge-transitive.展开更多
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 siz...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 k>5 and girth g>5 is super-λs for any positive integer s with s 2g or s 10 if k=g=6.展开更多
Abstract Let X be a 4-valent connected vertex-transitive graph with odd-prime-power order p^k (kS1), and let A be the full automorphism group of X. In this paper, we prove that the stabilizer Av of a vertex v in A is ...Abstract Let X be a 4-valent connected vertex-transitive graph with odd-prime-power order p^k (kS1), and let A be the full automorphism group of X. In this paper, we prove that the stabilizer Av of a vertex v in A is a 2-group if p p 5, or a {2,3}-group if p = 5. Furthermore, if p = 5 |Av| is not divisible by 3^2. As a result, we show that any 4-valent connected vertex-transitive graph with odd-prime-power order p^k (kS1) is at most 1-arc-transitive for p p 5 and 2-arc-transitive for p = 5.展开更多
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 ...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 12 p, 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.展开更多
We investigate the family of vertex-transitive graphs with diameter 2.LetΓbe such a graph.Suppose that its automorphism group is transitive on the set of ordered non-adjacent vertex pairs.Then eitherΓis distance-tra...We investigate the family of vertex-transitive graphs with diameter 2.LetΓbe such a graph.Suppose that its automorphism group is transitive on the set of ordered non-adjacent vertex pairs.Then eitherΓis distance-transitive orΓhas girth at most 4.Moreover,ifΓhas valency 2,thenΓ≌C4 or C5;and for any integer n≥3,there exist such graphsΓof valency n such that its automorphism group is not transitive on the set of arcs.Also,we determine this family of graphs of valency less than 5.Finally,the family of diameter 2 circulants is characterized.展开更多
We classify the family of pentavalent vertex-transitive graphs F with diameter 2. Suppose that the automorphism group of F is transitive on the set of ordered distance 2 vertex pairs. Then we show that either F is dis...We classify the family of pentavalent vertex-transitive graphs F with diameter 2. Suppose that the automorphism group of F is transitive on the set of ordered distance 2 vertex pairs. Then we show that either F is distancetransitive or F is one of C8-, K5 K2, C5[K2], 2C4, or K3 K4.展开更多
Let Circ（r, n） be a circular graph. It is well known that its independence number α（Circ（r, n）） = r. In this paper we prove that for every vertex transitive graph H, and describe the structure of maximum indepe...Let Circ（r, n） be a circular graph. It is well known that its independence number α（Circ（r, n）） = r. In this paper we prove that for every vertex transitive graph H, and describe the structure of maximum independent sets in Circ（r, n） × H. As consequences, we prove for G being Kneser graphs, and the graphs defined by permutations and partial permutations, respectively. The structure of maximum independent sets in these direct products is also described.展开更多
Since many large graphs are composed from some existing smaller graphs by using graph operations, say, the Cartesian product, the Lexicographic product and the Strong product. Many properties of such large graphs are ...Since many large graphs are composed from some existing smaller graphs by using graph operations, say, the Cartesian product, the Lexicographic product and the Strong product. Many properties of such large graphs are closely related to those of the corresponding smaller ones. In this short note, we give some properties of the Strong product of vertex-transitive graphs. In particular, we show that the Strong product of Cayley graphs is still a Cayley graph.展开更多
Let G be a k-regular connected graph of order at least six. If G has girth three, its 3-restricted edge connectivity λ3(G) ≤3k-6. The equality holds when G is a cubic or 4-regular connected vertex-transitive graph w...Let G be a k-regular connected graph of order at least six. If G has girth three, its 3-restricted edge connectivity λ3(G) ≤3k-6. The equality holds when G is a cubic or 4-regular connected vertex-transitive graph with the only exception that G is a 4-regular graph with λ3(G) = 4. Furthermore, λ3(G) = 4 if and only if G contains K4 as its subgraph.展开更多
The relative xity of a permutation group is the maximum proportion of the points xed by a non-trivial element of the group,and the relative xity of a graph is the relative xity of its automorphism group,viewed as a pe...The relative xity of a permutation group is the maximum proportion of the points xed by a non-trivial element of the group,and the relative xity of a graph is the relative xity of its automorphism group,viewed as a permutation group on the vertex-set of the graph.We prove in this paper that the relative xity of connected 2-arc-transitive graphs of a xed valence tends to 0 as the number of vertices grows to in nity.We prove the same result for the class of arc-transitive graphs of a xed prime valence,and more generally,for any class of arc-transitive locally-L graphs,where L is a xed quasiprimitive graph-restrictive permutation group.展开更多
基金Supported by ANSF(01046102)Supported by the NNSF of China(10271114)
文摘P Kulasinghe and S Bettayeb showed that any multiply-twisted hypercube withfive or more dimensions is not vertex-transitive. This note shows that any multiply-twistedhypercube with four or less dimensions is vertex-transitive, and that any multiply-twistedhypercube with three or larger dimensions is not edge-transitive.
基金supported by National Natural Science Foundation of China(Grant No.61073046)
文摘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 k>5 and girth g>5 is super-λs for any positive integer s with s 2g or s 10 if k=g=6.
基金Supported by the NNSFC (No.19831050),RFDP (No.97000141), SRF for ROCS,EYTP in China and Com~2MaC-KOSEF in Korea.
文摘Abstract Let X be a 4-valent connected vertex-transitive graph with odd-prime-power order p^k (kS1), and let A be the full automorphism group of X. In this paper, we prove that the stabilizer Av of a vertex v in A is a 2-group if p p 5, or a {2,3}-group if p = 5. Furthermore, if p = 5 |Av| is not divisible by 3^2. As a result, we show that any 4-valent connected vertex-transitive graph with odd-prime-power order p^k (kS1) is at most 1-arc-transitive for p p 5 and 2-arc-transitive for p = 5.
基金supported by National Natural Science Foundation of China(Grant Nos.11671030,11171020 and 11231008)the Fundamental Research Funds for the Central Universities(Grant No.2015JBM110)
文摘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 12 p, 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.
基金supported by the National Natural Science Foundation of China(12061034,12071484,11661039)Natural Science Foundation of Jiangxi(20212BAB201010,GJJ190273,20192ACBL21007,2018ACB21001)+1 种基金Natural Science Foundation of Hunan(2020JJ4675)China Postdoctoral Science Foundation(2019T120563)。
文摘We investigate the family of vertex-transitive graphs with diameter 2.LetΓbe such a graph.Suppose that its automorphism group is transitive on the set of ordered non-adjacent vertex pairs.Then eitherΓis distance-transitive orΓhas girth at most 4.Moreover,ifΓhas valency 2,thenΓ≌C4 or C5;and for any integer n≥3,there exist such graphsΓof valency n such that its automorphism group is not transitive on the set of arcs.Also,we determine this family of graphs of valency less than 5.Finally,the family of diameter 2 circulants is characterized.
基金Acknowledgements This work was supported by the National Natural Science Foundation of China （Grant Nos. 11561027, 11661039, 61563018）, the Natural Science Foundation of Jiangxi Province （20161BAB211018, 20151BAB201001）, the Jiangxi Education Department Grant （G J J150460, G J J150444）, and the China Postdoctoral Science Foundation （2016M590604）.
文摘We classify the family of pentavalent vertex-transitive graphs F with diameter 2. Suppose that the automorphism group of F is transitive on the set of ordered distance 2 vertex pairs. Then we show that either F is distancetransitive or F is one of C8-, K5 K2, C5[K2], 2C4, or K3 K4.
基金supported by National Natural Foundation of China(Grant No.10731040)supported by National Natural Foundation of China(Grant No.11001249)+1 种基金Ph.D.Programs Foundation of Ministry of Education of China (Grant No.20093127110001)Zhejiang Innovation Project(Grant No.T200905)
文摘Let Circ（r, n） be a circular graph. It is well known that its independence number α（Circ（r, n）） = r. In this paper we prove that for every vertex transitive graph H, and describe the structure of maximum independent sets in Circ（r, n） × H. As consequences, we prove for G being Kneser graphs, and the graphs defined by permutations and partial permutations, respectively. The structure of maximum independent sets in these direct products is also described.
基金Supported by the National Natural Science Foundation of China(61164005,11161037,11101232,61440005,11461054)Supported by the Program for Changjiang Scholars and Innovative Research Team in Universities(IRT1068)+1 种基金Supported by the Research Fund for the Chunhui Program of Ministry of Education of China(Z2014022)Supported by the Nature Science Foundation from Qinghai Province(2014-ZJ-721,2014-ZJ-907,2015-ZJ-905)
文摘Since many large graphs are composed from some existing smaller graphs by using graph operations, say, the Cartesian product, the Lexicographic product and the Strong product. Many properties of such large graphs are closely related to those of the corresponding smaller ones. In this short note, we give some properties of the Strong product of vertex-transitive graphs. In particular, we show that the Strong product of Cayley graphs is still a Cayley graph.
文摘Let G be a k-regular connected graph of order at least six. If G has girth three, its 3-restricted edge connectivity λ3(G) ≤3k-6. The equality holds when G is a cubic or 4-regular connected vertex-transitive graph with the only exception that G is a 4-regular graph with λ3(G) = 4. Furthermore, λ3(G) = 4 if and only if G contains K4 as its subgraph.
基金supported by the Austrian Science Fund(FWF)Project W1230-N13.The second author was supported by the Research Programme P1-0294the Research Project J1-1691,both funded by the Slovenian Research Agency(ARRS).
文摘The relative xity of a permutation group is the maximum proportion of the points xed by a non-trivial element of the group,and the relative xity of a graph is the relative xity of its automorphism group,viewed as a permutation group on the vertex-set of the graph.We prove in this paper that the relative xity of connected 2-arc-transitive graphs of a xed valence tends to 0 as the number of vertices grows to in nity.We prove the same result for the class of arc-transitive graphs of a xed prime valence,and more generally,for any class of arc-transitive locally-L graphs,where L is a xed quasiprimitive graph-restrictive permutation group.
