Sufficient Conditions for Maximally Edge-connected and Super-edge-connected Digraphs Depending on the Size

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.

Super Cyclically Edge-connected Vertex-transitive Graphs of Girth at Least 5

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.

Sufficient Conditions for Maximally Edge-Connected Hypergraphs

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.

On the extra edge-connectivity of hypercubes

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].

Super Cyclically Edge Connected Half Vertex Transitive Graphs

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.

Super Edge-connectivity and Zeroth-order General Randi Index for -1≤α< 0

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.

Upper bound of the third edge-connectivity of graphs

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.

Optimization problems of the third edge-connectivity of graphs

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.

Super s-restricted edge-connectivity of vertex-transitive graphs

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.

On restricted edge-connectivity of replacement product graphs

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 general sufficient condition for a graph G with λ_m(G)≤ξ_m(G)

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.

Partitioning series-parallel multigraphs into υ*-excluding edge covers

We prove that, for any given vertexν* in a series-parallel graph G, its edge set can be partitioned into k= min{k′(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 k′(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.

On Eccentric Connectivity Index and Connectivity

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.

Super Connectivity of Line Graphs and Digraphs

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.

Bounds for the Rainbow Disconnection Numbers of Graphs

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.

k-Factors in Regular Graphs

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.

On the Sizes of k-edge-maximal r-uniform Hypergraphs

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.