An m-restricted edge cut is an edge cut that separates a connected graph into a disconnected one with no components having order less than m. m-restricted edge connectivity λ<SUB> m </SUB>is the c...An m-restricted edge cut is an edge cut that separates a connected graph into a disconnected one with no components having order less than m. m-restricted edge connectivity λ<SUB> m </SUB>is the cardinality of a minimum m-restricted edge cut. Let G be a connected k-regular graph of order at least 2m that contains m-restricted edge cuts and X be a subgraph of G. Let ∂(X) denote the number of edges with one end in X and the other not in X and ξ<SUB> m </SUB>= min{∂(X) : X is a connected vertex-induced subgraph of order m}. It is proved in this paper that if G has girth at least m/2+ 2, then λ<SUB> m </SUB>≤ ξ<SUB> m </SUB>. The upper bound of λ<SUB> m </SUB>is sharp.展开更多
The k-component edgeconnectivity cλk(G)of anon-completegraph G is themini mum number of edges whose deletion results in a graph with at least k components In this paper,we extend some results by Guo et al.(Appl Math ...The k-component edgeconnectivity cλk(G)of anon-completegraph G is themini mum number of edges whose deletion results in a graph with at least k components In this paper,we extend some results by Guo et al.(Appl Math Comput 334:401-406,2018)by determining the component edge connectivity of the locally twisted cubes LTQn,i.e.,cλk+1(LTQn)=kn-exk/2for 1≤2[n/2],n≥7,where exk=∑si=0ti2ti+∑si=02·i·2ti,and k is a positive integer with decomposition k=∑si=02ti such that to="log2k"and ti="log2(k-∑i-1 r=02tr)"for i≥1.As a by-product,we characterize the corresponding optimal solutions.展开更多
By Petersen＇s Theorem, a bridgeless cubic graph has a 2-factor. Fleischner （Discrete Math., 101, 33-37 （1992）） has extended this result to bridgeless graphs of minimum degree at least three by showing that every ...By Petersen＇s Theorem, a bridgeless cubic graph has a 2-factor. Fleischner （Discrete Math., 101, 33-37 （1992）） has extended this result to bridgeless graphs of minimum degree at least three by showing that every such graph has an even factor without isolated vertices. Let me〉 0 be even and mo〉 0 be odd. In this paper, we prove that every me-edge-connected graph with minimum degree at least me ＋ 1 contains an even factor with minimum degree at least me and every （mo ＋ 1）- edge-connected graph contains an odd factor with minimum degree at least too, which further extends Fleischner＇s result. Moreover, we show that our results are best possible.展开更多
Let G =（V, E） be a connected graph and m be a positive integer, the conditional edge connectivity λ;is the minimum cardinality of a set of edges,if it exists, whose deletion disconnects G and leaves each remaining ...Let G =（V, E） be a connected graph and m be a positive integer, the conditional edge connectivity λ;is the minimum cardinality of a set of edges,if it exists, whose deletion disconnects G and leaves each remaining component with minimum degree δ no less than m. This study shows that λ;(Q;) = 2 n,λ;(Q;) = 4 n-4（2 ≤ k ≤ n-1, n ≥ 3） for n-dimensional enhanced hypercube Q;. Meanwhile, another easy proof about λ;（Q;） = 4 n-8, for n ≥ 3 is proposed. The results of enhanced hypercube include the cases of folded hypercube.展开更多
A graph G is super-edge-connected,for short super-λ,if every minimum edge-cut consists of edges adjacent to a vertex of minimum degree.Alphabet overlap graph G（k,d,s）is undirected,simple graph with vertex set V={v...A graph G is super-edge-connected,for short super-λ,if every minimum edge-cut consists of edges adjacent to a vertex of minimum degree.Alphabet overlap graph G（k,d,s）is undirected,simple graph with vertex set V={v｜v=1（）kv…v;vi∈{1,2,…,d},i=1,…,k}.Two vertices u=（u1…uk）and v=（v1…vk）are adjacent if and only if us＋i=vi or vs＋i=ui（i=1,…,k-s）.In particular G（k,d,1）is just an undirected de Bruijn graph.In this paper,we show that the diameter of G（k,d,s）is k s,the girth is 3.Finally,we prove that G（k,d,s）（s≥k/2）is super-λ.展开更多
In this paper, we determine the neighbor connectivity κNB of two kinds of Cayley graphs： alter- nating group networks ANn and star graphs Sn; and give the exact values of edge neighbor connectivity λNB of ANn and C...In this paper, we determine the neighbor connectivity κNB of two kinds of Cayley graphs： alter- nating group networks ANn and star graphs Sn; and give the exact values of edge neighbor connectivity λNB of ANn and Cayley graphs generated by transposition trees Fn. Those are κNB（ANn） = n-1, λNB（ANn） = n-2 and κNB（Sn） = λNB（Гn） = n - 1.展开更多
Robustness of the network topology is a key aspect in the design of computer networks. Residual closeness is a new graph-theoretic concept defined as a measure of network robustness due to the failure of individual ve...Robustness of the network topology is a key aspect in the design of computer networks. Residual closeness is a new graph-theoretic concept defined as a measure of network robustness due to the failure of individual vertices. We identify those graphs with maximum residual closeness among connected graphs with fixed connectivity, edge connectivity and bipartiteness, respectively.展开更多
基金National Natural Science Foundation of China (Grant No.10271105) and Doctoral Fund of Zhangzhou Normal College.
文摘An m-restricted edge cut is an edge cut that separates a connected graph into a disconnected one with no components having order less than m. m-restricted edge connectivity λ<SUB> m </SUB>is the cardinality of a minimum m-restricted edge cut. Let G be a connected k-regular graph of order at least 2m that contains m-restricted edge cuts and X be a subgraph of G. Let ∂(X) denote the number of edges with one end in X and the other not in X and ξ<SUB> m </SUB>= min{∂(X) : X is a connected vertex-induced subgraph of order m}. It is proved in this paper that if G has girth at least m/2+ 2, then λ<SUB> m </SUB>≤ ξ<SUB> m </SUB>. The upper bound of λ<SUB> m </SUB>is sharp.
基金the National Natural Science Foundation of China(No.11531011).
文摘The k-component edgeconnectivity cλk(G)of anon-completegraph G is themini mum number of edges whose deletion results in a graph with at least k components In this paper,we extend some results by Guo et al.(Appl Math Comput 334:401-406,2018)by determining the component edge connectivity of the locally twisted cubes LTQn,i.e.,cλk+1(LTQn)=kn-exk/2for 1≤2[n/2],n≥7,where exk=∑si=0ti2ti+∑si=02·i·2ti,and k is a positive integer with decomposition k=∑si=02ti such that to="log2k"and ti="log2(k-∑i-1 r=02tr)"for i≥1.As a by-product,we characterize the corresponding optimal solutions.
基金Supported by National Natural Science Foundation of China(Grant Nos.11471257 and 11101329)
文摘By Petersen＇s Theorem, a bridgeless cubic graph has a 2-factor. Fleischner （Discrete Math., 101, 33-37 （1992）） has extended this result to bridgeless graphs of minimum degree at least three by showing that every such graph has an even factor without isolated vertices. Let me〉 0 be even and mo〉 0 be odd. In this paper, we prove that every me-edge-connected graph with minimum degree at least me ＋ 1 contains an even factor with minimum degree at least me and every （mo ＋ 1）- edge-connected graph contains an odd factor with minimum degree at least too, which further extends Fleischner＇s result. Moreover, we show that our results are best possible.
文摘Let G =（V, E） be a connected graph and m be a positive integer, the conditional edge connectivity λ;is the minimum cardinality of a set of edges,if it exists, whose deletion disconnects G and leaves each remaining component with minimum degree δ no less than m. This study shows that λ;(Q;) = 2 n,λ;(Q;) = 4 n-4（2 ≤ k ≤ n-1, n ≥ 3） for n-dimensional enhanced hypercube Q;. Meanwhile, another easy proof about λ;（Q;） = 4 n-8, for n ≥ 3 is proposed. The results of enhanced hypercube include the cases of folded hypercube.
文摘A graph G is super-edge-connected,for short super-λ,if every minimum edge-cut consists of edges adjacent to a vertex of minimum degree.Alphabet overlap graph G（k,d,s）is undirected,simple graph with vertex set V={v｜v=1（）kv…v;vi∈{1,2,…,d},i=1,…,k}.Two vertices u=（u1…uk）and v=（v1…vk）are adjacent if and only if us＋i=vi or vs＋i=ui（i=1,…,k-s）.In particular G（k,d,1）is just an undirected de Bruijn graph.In this paper,we show that the diameter of G（k,d,s）is k s,the girth is 3.Finally,we prove that G（k,d,s）（s≥k/2）is super-λ.
基金Supported by the National Natural Science Foundation of China(No.11371052,11731002,11571035)
文摘In this paper, we determine the neighbor connectivity κNB of two kinds of Cayley graphs： alter- nating group networks ANn and star graphs Sn; and give the exact values of edge neighbor connectivity λNB of ANn and Cayley graphs generated by transposition trees Fn. Those are κNB（ANn） = n-1, λNB（ANn） = n-2 and κNB（Sn） = λNB（Гn） = n - 1.
基金supported by the National Natural Science Foundation of China(No.12071158).
文摘Robustness of the network topology is a key aspect in the design of computer networks. Residual closeness is a new graph-theoretic concept defined as a measure of network robustness due to the failure of individual vertices. We identify those graphs with maximum residual closeness among connected graphs with fixed connectivity, edge connectivity and bipartiteness, respectively.
