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.展开更多
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.展开更多
一个图Г称为G-对称的(symmetric).如果其同构群Aut(r)的一个子群G在图r的有向孤集(set of ordered pairs of adjacent vertices)上的作用是传递的(transitive).本文主要结果是:设图Г是4度对称图.全自同构群Aut(r)=A_5,则图r是且仅是...一个图Г称为G-对称的(symmetric).如果其同构群Aut(r)的一个子群G在图r的有向孤集(set of ordered pairs of adjacent vertices)上的作用是传递的(transitive).本文主要结果是:设图Г是4度对称图.全自同构群Aut(r)=A_5,则图r是且仅是如下图之一:(1)Г是15个点的完全图K_5的三维覆盖(3-fold cover)图.(2)Г是完全图K_5.展开更多
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.展开更多
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.展开更多
基金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.
基金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.
文摘一个图Г称为G-对称的(symmetric).如果其同构群Aut(r)的一个子群G在图r的有向孤集(set of ordered pairs of adjacent vertices)上的作用是传递的(transitive).本文主要结果是:设图Г是4度对称图.全自同构群Aut(r)=A_5,则图r是且仅是如下图之一:(1)Г是15个点的完全图K_5的三维覆盖(3-fold cover)图.(2)Г是完全图K_5.
基金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.
基金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.
