Tian and Meng in [Y. Tian and J. Meng, λc -Optimally half vertex transitive graphs with regularity k, Information Processing Letters 109 (2009) 683 - 686] shown that a connected half vertex transitive graph with regu...Tian and Meng in [Y. Tian and J. Meng, λc -Optimally half vertex transitive graphs with regularity k, Information Processing Letters 109 (2009) 683 - 686] shown that a connected half vertex transitive graph with regularity k and girth g(G) ≥ 6 is cyclically optimal. In this paper, we show that a connected half vertex transitive graph G is super cyclically edge-connected if minimum degree δ(G) ≥ 6 and girth g(G) ≥ 6.展开更多
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.展开更多
This paper considers the edge-connectivity and the restricted edge-connectivity of replacement product graphs, gives some bounds on edge-connectivity and restricted edge-connectivity of replacement product graphs and ...This paper considers the edge-connectivity and the restricted edge-connectivity of replacement product graphs, gives some bounds on edge-connectivity and restricted edge-connectivity of replacement product graphs and determines the exact values for some special graphs. In particular, the authors further confirm that under certain conditions, the replacement product of two Cayley graphs is also a Cayley graph, and give a necessary and sufficient condition for such Cayley graphs to have maximum restricted edge-connectivity. Based on these results, we construct a Cayley graph with degree d whose restricted edge-connectivity is equal to d + s for given odd integer d and integer s with d 5 and 1 s d- 3, which answers a problem proposed ten years ago.展开更多
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-...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-λc, 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-λc if G has minimum degree at least 4 and girth at least 6, and the authors also presented a class of nonsuper-λc graphs which have degree 4 and girth 5. In this paper, a characterization of k （k≥4）-regular vertex-transitive nonsuper-λc graphs of girth 5 is given. Using this, we classify all k （k≥4）-regular nonsuper-λc Cayley graphs of girth 5, and construct the first infinite family of nonsuper-λc vertex-transitive non-Cayley graphs.展开更多
The h-super connectivity κh and the h-super edge-connectivity λh are more refined network reliability indices than the conneetivity and the edge-connectivity. This paper shows that for a connected balanced digraph D...The h-super connectivity κh and the h-super edge-connectivity λh are more refined network reliability indices than the conneetivity and the edge-connectivity. This paper shows that for a connected balanced digraph D and its line digraph L, if D is optimally super edge-connected, then κ1（L） = 2λ1 （D）, and that for a connected graph G and its line graph L, if one of κ1 （L） and λ（G） exists, then κ1（L） = λ2（G）. This paper determines that κ1（B（d, n） is equal to 4d- 8 for n = 2 and d ≥ 4, and to 4d-4 for n ≥ 3 and d ≥ 3, and that κ1（K（d, n）） is equal to 4d- 4 for d 〉 2 and n ≥ 2 except K（2, 2）. It then follows that B（d,n） and K（d, n） are both super connected for any d ≥ 2 and n ≥ 1.展开更多
Let G be a connected graph with order n,minimum degree δ = δ（G） and edge-connectivity λ =λ（G）. A graph G is maximally edge-connected if λ = δ, and super edge-connected if every minimum edgecut consists of ed...Let G be a connected graph with order n,minimum degree δ = δ（G） and edge-connectivity λ =λ（G）. A graph G is maximally edge-connected if λ = δ, and super edge-connected if every minimum edgecut consists of edges incident with a vertex of minimum degree. Define the zeroth-order general Randic index R_α-0（G） =Σ x∈V（G） d_G-α（x）, where dG（x） denotes the degree of the vertex x. In this paper, we present two sufficient conditions for graphs and triangle-free graphs to be super edge-connected in terms of the zeroth-order general Randic index for -1 ≤α 〈 0, respectively.展开更多
文摘Tian and Meng in [Y. Tian and J. Meng, λc -Optimally half vertex transitive graphs with regularity k, Information Processing Letters 109 (2009) 683 - 686] shown that a connected half vertex transitive graph with regularity k and girth g(G) ≥ 6 is cyclically optimal. In this paper, we show that a connected half vertex transitive graph G is super cyclically edge-connected if minimum degree δ(G) ≥ 6 and girth g(G) ≥ 6.
基金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 National Natural Science Foundation of China (Grant Nos. 61272008 and 11571044)University Natural Science Research Project of Anhui Province (Grant No. KJ2016A003)Scientific Research Fund of Anhui University of Finance & Economics (Grant No. ACKY1532)
文摘This paper considers the edge-connectivity and the restricted edge-connectivity of replacement product graphs, gives some bounds on edge-connectivity and restricted edge-connectivity of replacement product graphs and determines the exact values for some special graphs. In particular, the authors further confirm that under certain conditions, the replacement product of two Cayley graphs is also a Cayley graph, and give a necessary and sufficient condition for such Cayley graphs to have maximum restricted edge-connectivity. Based on these results, we construct a Cayley graph with degree d whose restricted edge-connectivity is equal to d + s for given odd integer d and integer s with d 5 and 1 s d- 3, which answers a problem proposed ten years ago.
基金supported by National Natural Science Foundation of China (Grant No.11271012)the Fundamental Research Funds for the Central Universities (Grant Nos.2011JBM127,2011JBZ012)+1 种基金supported by National Natural Science Foundation of China (Grant No.11101035)the Subsidy for Outstanding People of Beijing (Grant No.2011D005022000005)
文摘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-λc, 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-λc if G has minimum degree at least 4 and girth at least 6, and the authors also presented a class of nonsuper-λc graphs which have degree 4 and girth 5. In this paper, a characterization of k （k≥4）-regular vertex-transitive nonsuper-λc graphs of girth 5 is given. Using this, we classify all k （k≥4）-regular nonsuper-λc Cayley graphs of girth 5, and construct the first infinite family of nonsuper-λc vertex-transitive non-Cayley graphs.
基金Supported by the National Natural Science Foundation of China(No.10271114,No.10301031).
文摘The h-super connectivity κh and the h-super edge-connectivity λh are more refined network reliability indices than the conneetivity and the edge-connectivity. This paper shows that for a connected balanced digraph D and its line digraph L, if D is optimally super edge-connected, then κ1（L） = 2λ1 （D）, and that for a connected graph G and its line graph L, if one of κ1 （L） and λ（G） exists, then κ1（L） = λ2（G）. This paper determines that κ1（B（d, n） is equal to 4d- 8 for n = 2 and d ≥ 4, and to 4d-4 for n ≥ 3 and d ≥ 3, and that κ1（K（d, n）） is equal to 4d- 4 for d 〉 2 and n ≥ 2 except K（2, 2）. It then follows that B（d,n） and K（d, n） are both super connected for any d ≥ 2 and n ≥ 1.
基金supported by the National Natural Science Foundation of China(No.11501490,61373019,11371307)by the Natural Science Foundation of Shandong Province(No.ZR2015AM006)
文摘Let G be a connected graph with order n,minimum degree δ = δ（G） and edge-connectivity λ =λ（G）. A graph G is maximally edge-connected if λ = δ, and super edge-connected if every minimum edgecut consists of edges incident with a vertex of minimum degree. Define the zeroth-order general Randic index R_α-0（G） =Σ x∈V（G） d_G-α（x）, where dG（x） denotes the degree of the vertex x. In this paper, we present two sufficient conditions for graphs and triangle-free graphs to be super edge-connected in terms of the zeroth-order general Randic index for -1 ≤α 〈 0, respectively.
