The classical hypercube structure is a popular topological architecture in parallel computing environments and a large number of variations based on the hypercube were posed in the past three decades. Reliability eval...The classical hypercube structure is a popular topological architecture in parallel computing environments and a large number of variations based on the hypercube were posed in the past three decades. Reliability evaluation of systems is important to the design and maintenance of multiprocessor systems. The h-extra edge-connectivity of graph G(V, E) is a kind of measure for the reliability of interconnection systems, which is defined as the minimum cardinality of a subset of edge set, if any, whose deletion disconnects G and such that every re- maining component has at least h vertices. This paper shows that the h-extra edge-connectivity 2n-1 2n-1 of the hypercube Qn is a constant 2n-1 for 2n-1/3≤ h2n-1, and n ≥ 4, which extends the result of [Bounding the size of the subgraph induced by m vertices and extra edge-connectivity of hypercubes, Discrete Applied Mathematics, 2013, 161(16): 2753-2757].展开更多
Let G be a simple connected graph of order n ≥ 6. The third edge-connectivity of G is defined as the minimum cardinality over all the sets of edges, if any, whose deletion disconnects G and every component of the res...Let G be a simple connected graph of order n ≥ 6. The third edge-connectivity of G is defined as the minimum cardinality over all the sets of edges, if any, whose deletion disconnects G and every component of the resulting graph has at least 3 vertices. In this paper, we first characterize those graphs whose third-edge connectivity is well defined,then establish the tight upper bound for the third edge-connectivity.展开更多
The third edge-connectivity λ3(G) of a graph G is defined as the minimum cardinality over all sets of edges, if any, whose deletion disconnects G and each component of the resulting graph has at least 3 vertices. An ...The third edge-connectivity λ3(G) of a graph G is defined as the minimum cardinality over all sets of edges, if any, whose deletion disconnects G and each component of the resulting graph has at least 3 vertices. An upper bound has been established for λ3(G) whenever λ3(G) is well-defined. This paper first introduces two combinatorial optimization concepts, that is, maximality and superiority, of λ3(G), and then proves the Ore type sufficient conditions for G to be maximally and super third edge-connected. These concepts and results are useful in network reliability analysis.展开更多
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 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 D be a finite and simple digraph with vertex set V(D).The minimum degreeδof a digraph D is defined as the minimum value of its out-degrees and its in-degrees.If D is a digraph with minimum degreeδand edge-connec...Let D be a finite and simple digraph with vertex set V(D).The minimum degreeδof a digraph D is defined as the minimum value of its out-degrees and its in-degrees.If D is a digraph with minimum degreeδand edge-connectivity λ,then λ≤δ.A digraph is maximally edge-connected ifλ=δ.A digraph is called super-edge-connected if every minimum edge-cut consists of edges incident to or from a vertex of minimum degree.In this note we show that a digraph is maximally edge-connected or super-edge-connected if the number of arcs is large enough.展开更多
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 edge-connectivity of a graph or a hypergraph is defined as the minimum number of edges whose removal renders the graph or hypergraph disconnected.A graph or hypergraph is called maximally edge-connected if the edg...The edge-connectivity of a graph or a hypergraph is defined as the minimum number of edges whose removal renders the graph or hypergraph disconnected.A graph or hypergraph is called maximally edge-connected if the edge-connectivity equals its minimum degree.In this paper,we show that some classical sufficient conditions for graphs to be maximally edge-connected can be generalized to hypergraphs.展开更多
It has been shown that a λ m-connected graph G has the property λ m (G)≤ξ m (G) for m≤3.But for m≥4,Bonsma et al.pointed out that in general the inequality λ m (G)≤ξ m (G) is no longer true.Recently Ou showed...It has been shown that a λ m-connected graph G has the property λ m (G)≤ξ m (G) for m≤3.But for m≥4,Bonsma et al.pointed out that in general the inequality λ m (G)≤ξ m (G) is no longer true.Recently Ou showed that any λ 4-connected graph G with order at least 11 has the property λ 4 (G)≤ξ 4 (G).In this paper,by investigating some structure properties of a λ m-connected graph G with λ m (G) > ξ m (G),we obtain easily the above result.Furthermore,we show that every λ m-connected graph G with order greater than m(m-1) satisfies the inequality λ m (G)≤ξm (G) for m≥5.And by constructing some examples,we illustrate that our conditions are the best possible.展开更多
We prove that, for any given vertex υ* in a series-parallel graph G, its edge set can be partitioned into k = min{κ'(G) + 1,δ(G)} subsets such that each subset covers all the vertices of G possibly except for ...We prove that, for any given vertex υ* in a series-parallel graph G, its edge set can be partitioned into k = min{κ'(G) + 1,δ(G)} subsets such that each subset covers all the vertices of G possibly except for υ*, where δ(G) is the minimum degree of G and κ'(G) is the edge-connectivity of G. In addition, we show that the results in this paper are best possible and a polynomial time algorithm can be obtained for actually finding such a partition by our proof.展开更多
Let G be a finite connected graph. The eccentric connectivity index ξ^c(G) of G is defined as ξ^c(G)=∑v∈V(G)ec(υ)deg(υ), where ec(v) and deg(υ) denote the eccentricity and degree of a vertex v in G, respectivel...Let G be a finite connected graph. The eccentric connectivity index ξ^c(G) of G is defined as ξ^c(G)=∑v∈V(G)ec(υ)deg(υ), where ec(v) and deg(υ) denote the eccentricity and degree of a vertex v in G, respectively. In this paper, we give an asymptotically sharp upper bound on the eccentric connectivity index in terms of order and vertex-connectivity and in terms of order and edge-connectivity. We also improve the bounds for triangle-free 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.展开更多
An edge-cut of an edge-colored connected graph is called a rainbow cut if no two edges in the edge-cut are colored the same.An edge-colored graph is rainbow disconnected if for any two distinct vertices u and v of the...An edge-cut of an edge-colored connected graph is called a rainbow cut if no two edges in the edge-cut are colored the same.An edge-colored graph is rainbow disconnected if for any two distinct vertices u and v of the graph,there exists a rainbow cut separating u and v.For a connected graph G,the rainbow disconnection number of G,denoted by rd(G),is defined as the smallest number of colors required to make G rainbow disconnected.In this paper,we first give some upper bounds for rd(G),and moreover,we completely characterize the graphs which meet the upper bounds of the NordhausGaddum type result obtained early by us.Secondly,we propose a conjecture that for any connected graph G,either rd(G)=λ^(+)(G)or rd(G)=λ^(+)(G)+1,whereλ^(+)(G)is the upper edge-connectivity,and prove that the conjecture holds for many classes of graphs,which supports this conjecture.Moreover,we prove that for an odd integer k,if G is a k-edge-connected k-regular graph,thenχ’(G)=k if and only if rd(G)=k.It implies that there are infinitely many k-edge-connected k-regular graphs G for which rd(G)=λ^(+)(G)for odd k,and also there are infinitely many k-edge-connected k-regular graphs G for which rd(G)=λ^(+)(G)+1 for odd k.For k=3,the result gives rise to an interesting result,which is equivalent to the famous Four-Color Problem.Finally,we give the relationship between rd(G)of a graph G and the rainbow vertex-disconnection number rvd(L(G))of the line graph L(G)of G.展开更多
Plesnik in 1972 proved that an (m - 1)-edge connected m-regular graph of even order has a 1-factor containing any given edge and has another 1-factor excluding any given m - 1 edges. Alder et al. in 1999 showed that...Plesnik in 1972 proved that an (m - 1)-edge connected m-regular graph of even order has a 1-factor containing any given edge and has another 1-factor excluding any given m - 1 edges. Alder et al. in 1999 showed that if G is a regular (2n + 1)-edge-connected bipartite graph, then G has a 1-factor containing any given edge and excluding any given matching of size n. In this paper we obtain some sufficient conditions related to the edge-connectivity for an n-regular graph to have a k-factor containing a set of edges and (or) excluding a set of edges, where 1 ≤ k ≤n/2. In particular, we generalize Plesnik's result and the results obtained by Liu et al. in 1998, and improve Katerinis' result obtained 1993. Furthermore, we show that the results in this paper are the best possible.展开更多
Let H=(V,E)be a hypergraph,where V is a set of vertices and E is a set of non-empty subsets of V called edges.If all edges of H have the same cardinality r,then H is an r-uniform hypergraph;if E consists of all r-subs...Let H=(V,E)be a hypergraph,where V is a set of vertices and E is a set of non-empty subsets of V called edges.If all edges of H have the same cardinality r,then H is an r-uniform hypergraph;if E consists of all r-subsets of V,then H is a complete r-uniform hypergraph,denoted by K_(n)^(r),where n=|V|.A hypergraph H′=(V′,E′)is called a subhypergraph of H=(V,E)if V′⊆V and E′⊆E.The edge-connectivity of a hypergraph H is the cardinality of a minimum edge set F⊆E such that H−F is not connected,where H−F=(V,E\F).An r-uniform hypergraph H=(V,E)is k-edge-maximal if every subhypergraph of H has edge-connectivity at most k,but for any edge e∈E(K_(n)^(r))\E(H),H+e contains at least one subhypergraph with edge-connectivity at least k+1.Let k and r be integers with k≥2 and r≥2,and let t=t(k,r)be the largest integer such that(t−1 r−1)≤k.That is,t is the integer satisfying(t−1 r−1)≤k<(t r−1).We prove that if H is an r-uniform k-edge-maximal hypergraph such that n=|V(H)|≥t,then(i)|E(H)|≤(t r)+(n−t)k,and this bound is best possible;(ii)|E(H)|≥(n−1)k−((t−1)k−(t r))[n/t],and this bound is best possible.展开更多
基金Supported by the National Natural Science Foundation of China(11171283,11471273,11461038,11301440)Natural Sciences Foundation of Shanxi Province(2014021010-2)
文摘The classical hypercube structure is a popular topological architecture in parallel computing environments and a large number of variations based on the hypercube were posed in the past three decades. Reliability evaluation of systems is important to the design and maintenance of multiprocessor systems. The h-extra edge-connectivity of graph G(V, E) is a kind of measure for the reliability of interconnection systems, which is defined as the minimum cardinality of a subset of edge set, if any, whose deletion disconnects G and such that every re- maining component has at least h vertices. This paper shows that the h-extra edge-connectivity 2n-1 2n-1 of the hypercube Qn is a constant 2n-1 for 2n-1/3≤ h2n-1, and n ≥ 4, which extends the result of [Bounding the size of the subgraph induced by m vertices and extra edge-connectivity of hypercubes, Discrete Applied Mathematics, 2013, 161(16): 2753-2757].
基金This work was supported by Zhejiang Provincial Natural Science Foundation of China(Grant No.102055)the Natural Science Foundation of Zhejiang Normal UniversityThe second author was supported by the National Natural Science Foundation of China(Grant No.19971056).
文摘Let G be a simple connected graph of order n ≥ 6. The third edge-connectivity of G is defined as the minimum cardinality over all the sets of edges, if any, whose deletion disconnects G and every component of the resulting graph has at least 3 vertices. In this paper, we first characterize those graphs whose third-edge connectivity is well defined,then establish the tight upper bound for the third edge-connectivity.
基金This work was supported by the National Natural Science Foundation of China(Grant No.10471131)the Natural Science Foundation of Zhejiang Province(Grant No.102055).
文摘The third edge-connectivity λ3(G) of a graph G is defined as the minimum cardinality over all sets of edges, if any, whose deletion disconnects G and each component of the resulting graph has at least 3 vertices. An upper bound has been established for λ3(G) whenever λ3(G) is well-defined. This paper first introduces two combinatorial optimization concepts, that is, maximality and superiority, of λ3(G), and then proves the Ore type sufficient conditions for G to be maximally and super third edge-connected. These concepts and results are useful in network reliability analysis.
基金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.
文摘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 D be a finite and simple digraph with vertex set V(D).The minimum degreeδof a digraph D is defined as the minimum value of its out-degrees and its in-degrees.If D is a digraph with minimum degreeδand edge-connectivity λ,then λ≤δ.A digraph is maximally edge-connected ifλ=δ.A digraph is called super-edge-connected if every minimum edge-cut consists of edges incident to or from a vertex of minimum degree.In this note we show that a digraph is maximally edge-connected or super-edge-connected if the number of arcs is large enough.
基金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.
基金This research was partially supported by the National Natural Science Foundation of China(Nos.11571222 and 11871329).
文摘The edge-connectivity of a graph or a hypergraph is defined as the minimum number of edges whose removal renders the graph or hypergraph disconnected.A graph or hypergraph is called maximally edge-connected if the edge-connectivity equals its minimum degree.In this paper,we show that some classical sufficient conditions for graphs to be maximally edge-connected can be generalized to hypergraphs.
基金supported by National Natural Science Foundation of China (Grant No.10831001)
文摘It has been shown that a λ m-connected graph G has the property λ m (G)≤ξ m (G) for m≤3.But for m≥4,Bonsma et al.pointed out that in general the inequality λ m (G)≤ξ m (G) is no longer true.Recently Ou showed that any λ 4-connected graph G with order at least 11 has the property λ 4 (G)≤ξ 4 (G).In this paper,by investigating some structure properties of a λ m-connected graph G with λ m (G) > ξ m (G),we obtain easily the above result.Furthermore,we show that every λ m-connected graph G with order greater than m(m-1) satisfies the inequality λ m (G)≤ξm (G) for m≥5.And by constructing some examples,we illustrate that our conditions are the best possible.
基金This work was partially supported by the National Natural Science Foundation of China(Grant No.10471078)the Special Research Foundation for the Doctoral Program of Higher Education of China(Grant No.20040422004)Hong Kong Research Grants Council(Grant No.CityU 1056/01E).
文摘We prove that, for any given vertex υ* in a series-parallel graph G, its edge set can be partitioned into k = min{κ'(G) + 1,δ(G)} subsets such that each subset covers all the vertices of G possibly except for υ*, where δ(G) is the minimum degree of G and κ'(G) is the edge-connectivity of G. In addition, we show that the results in this paper are best possible and a polynomial time algorithm can be obtained for actually finding such a partition by our proof.
文摘Let G be a finite connected graph. The eccentric connectivity index ξ^c(G) of G is defined as ξ^c(G)=∑v∈V(G)ec(υ)deg(υ), where ec(v) and deg(υ) denote the eccentricity and degree of a vertex v in G, respectively. In this paper, we give an asymptotically sharp upper bound on the eccentric connectivity index in terms of order and vertex-connectivity and in terms of order and edge-connectivity. We also improve the bounds for triangle-free 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 National Natural Science Foundation of China(Grant No.11871034)。
文摘An edge-cut of an edge-colored connected graph is called a rainbow cut if no two edges in the edge-cut are colored the same.An edge-colored graph is rainbow disconnected if for any two distinct vertices u and v of the graph,there exists a rainbow cut separating u and v.For a connected graph G,the rainbow disconnection number of G,denoted by rd(G),is defined as the smallest number of colors required to make G rainbow disconnected.In this paper,we first give some upper bounds for rd(G),and moreover,we completely characterize the graphs which meet the upper bounds of the NordhausGaddum type result obtained early by us.Secondly,we propose a conjecture that for any connected graph G,either rd(G)=λ^(+)(G)or rd(G)=λ^(+)(G)+1,whereλ^(+)(G)is the upper edge-connectivity,and prove that the conjecture holds for many classes of graphs,which supports this conjecture.Moreover,we prove that for an odd integer k,if G is a k-edge-connected k-regular graph,thenχ’(G)=k if and only if rd(G)=k.It implies that there are infinitely many k-edge-connected k-regular graphs G for which rd(G)=λ^(+)(G)for odd k,and also there are infinitely many k-edge-connected k-regular graphs G for which rd(G)=λ^(+)(G)+1 for odd k.For k=3,the result gives rise to an interesting result,which is equivalent to the famous Four-Color Problem.Finally,we give the relationship between rd(G)of a graph G and the rainbow vertex-disconnection number rvd(L(G))of the line graph L(G)of G.
基金FRGHong Kong Baptist University NSFC (60673047)SRFDP (20040422004) of China
文摘Plesnik in 1972 proved that an (m - 1)-edge connected m-regular graph of even order has a 1-factor containing any given edge and has another 1-factor excluding any given m - 1 edges. Alder et al. in 1999 showed that if G is a regular (2n + 1)-edge-connected bipartite graph, then G has a 1-factor containing any given edge and excluding any given matching of size n. In this paper we obtain some sufficient conditions related to the edge-connectivity for an n-regular graph to have a k-factor containing a set of edges and (or) excluding a set of edges, where 1 ≤ k ≤n/2. In particular, we generalize Plesnik's result and the results obtained by Liu et al. in 1998, and improve Katerinis' result obtained 1993. Furthermore, we show that the results in this paper are the best possible.
基金supported by the National Natural Science Foundation of China(Nos.11861066,11531011)Tianshan Youth Project of Xinjiang(2018Q066)。
文摘Let H=(V,E)be a hypergraph,where V is a set of vertices and E is a set of non-empty subsets of V called edges.If all edges of H have the same cardinality r,then H is an r-uniform hypergraph;if E consists of all r-subsets of V,then H is a complete r-uniform hypergraph,denoted by K_(n)^(r),where n=|V|.A hypergraph H′=(V′,E′)is called a subhypergraph of H=(V,E)if V′⊆V and E′⊆E.The edge-connectivity of a hypergraph H is the cardinality of a minimum edge set F⊆E such that H−F is not connected,where H−F=(V,E\F).An r-uniform hypergraph H=(V,E)is k-edge-maximal if every subhypergraph of H has edge-connectivity at most k,but for any edge e∈E(K_(n)^(r))\E(H),H+e contains at least one subhypergraph with edge-connectivity at least k+1.Let k and r be integers with k≥2 and r≥2,and let t=t(k,r)be the largest integer such that(t−1 r−1)≤k.That is,t is the integer satisfying(t−1 r−1)≤k<(t r−1).We prove that if H is an r-uniform k-edge-maximal hypergraph such that n=|V(H)|≥t,then(i)|E(H)|≤(t r)+(n−t)k,and this bound is best possible;(ii)|E(H)|≥(n−1)k−((t−1)k−(t r))[n/t],and this bound is best possible.