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.     

Edge fault tolerance analysis of super k-restricted connected networks

An edge cut X of a connected graph G is a k-restricted edge cut if G-X is disconnected and every component of G-X has at least k vertices. Additionally, if the deletion of a minimum k-restricted edge cut isolates a connected component of k vertices, then the graph is said to be super-λ_k. In this paper, several sufficient conditions yielding super-λ_k graphs are given in terms of the girth and the diameter.     

On cyclic edge-connectivity of transitive graphs

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 said to be cyclically separable. For a cyclically separable graph G, the cyclic edge-connectivity cλ(G) is the cardinality of a minimum cyclic edge-cut of G. In this paper, we first prove that for any cyclically separable graph G, , where ω(X) is the number of edges with one end in X and the other end in V(G)?X. A cyclically separable graph G with cλ(G)=ζ(G) is said to be cyclically optimal. The main results in this paper are: any connected k-regular vertex-transitive graph with k≥4 and girth at least 5 is cyclically optimal; any connected edge-transitive graph with minimum degree at least 4 and order at least 6 is cyclically optimal.     

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 k5 and girth g5 is super-λs for any positive integer s with s 2g or s 10 if k=g=6.     

Superconnectivity of regular graphs with small diameter

A graph is superconnected, for short super-κ, if all minimum vertex-cuts consist of the vertices adjacent with one vertex. In this paper we prove for any r-regular graph of diameter D and odd girth g that if D≤g−2, then the graph is super-κ when g≥5 and a complete graph otherwise.     

Topological-algebraic properties of function spaces with set-open topologies

For a Tychonoff space X, we denote by Cλ(X) the space of all real-valued continuous functions on X with set-open topology. In this paper, we study the topological-algebraic properties of Cλ(X). Our main results state that (1) Cλ(X) is a topological vector space (a topological group) iff λ is a family of C-compact sets and Cλ(X)=Cλ^′(X), where λ^′ consists of all C-compact subsets of every set of λ. In particular, if Cλ(X) is a topological group, then the set-open topology coincides with the topology of uniform convergence on a family λ; (2) a topological group Cλ(X) is ω-narrow iff λ is a family of metrizable compact subsets of X.     

On the edge-connectivity and restricted edge-connectivity of a product of graphs

The product graph G_m*G_p of two given graphs G_m and G_p was defined by Bermond et al. [Large graphs with given degree and diameter II, J. Combin. Theory Ser. B 36 (1984) 32-48]. For this kind of graphs we provide bounds for two connectivity parameters (λ and λ^′, edge-connectivity and restricted edge-connectivity, respectively), and state sufficient conditions to guarantee optimal values of these parameters. Moreover, we compare our results with other previous related ones for permutation graphs and cartesian product graphs, obtaining several extensions and improvements. In this regard, for any two connected graphs G_m, G_p of minimum degrees δ(G_m), δ(G_p), respectively, we show that λ(G_m*G_p) is lower bounded by both δ(G_m)+λ(G_p) and δ(G_p)+λ(G_m), an improvement of what is known for the edge-connectivity of G_m×G_p.     

Edge-splittings preserving local edge-connectivity of graphs

Let G=(V+s,E) be a 2-edge-connected graph with a designated vertex s. A pair of edges rs,st is called admissible if splitting off these edges (replacing rs and st by rt) preserves the local edge-connectivity (the maximum number of pairwise edge disjoint paths) between each pair of vertices in V. The operation splitting off is very useful in graph theory, it is especially powerful in the solution of edge-connectivity augmentation problems as it was shown by Frank [Augmenting graphs to meet edge-connectivity requirements, SIAM J. Discrete Math. 5(1) (1992) 22-53]. Mader [A reduction method for edge-connectivity in graphs, Ann. Discrete Math. 3 (1978) 145-164] proved that if d(s)≠3 then there exists an admissible pair incident to s. We generalize this result by showing that if d(s)?4 then there exists an edge incident to s that belongs to at least ⌊d(s)/3⌋ admissible pairs. An infinite family of graphs shows that this bound is best possible. We also refine a result of Frank [On a theorem of Mader, Discrete Math. 101 (1992) 49-57] by describing the structure of the graph if an edge incident to s belongs to no admissible pairs. This provides a new proof for Mader's theorem.     

Generalized bi-circular projections

Recall that a projection P on a complex Banach space X is a generalized bi-circular projection if P+λ(I−P) is a (surjective) isometry for some λ such that |λ|=1 and λ≠1. It is easy to see that every hermitian projection is generalized bi-circular. A generalized bi-circular projection is said to be nontrivial if it is not hermitian. Botelho and Jamison showed that a projection P on C([0,1]) is a nontrivial generalized bi-circular projection if and only if P−(I−P) is a surjective isometry. In this article, we prove that if P is a projection such that P+λ(I−P) is a (surjective) isometry for some λ, then either P is hermitian or λ is an nth unit root of unity. We also show that for any nth unit root λ of unity, there are a complex Banach space X and a nontrivial generalized bi-circular projection P on X such that P+λ(I−P) is an isometry.     

Graphical convergence of continuous functions

Let X and Y be metrizable spaces. We show that convergence of a net of continuous functions 〈f _λ 〉 to a continuous function f in the graph topology for C(X,Y) is equivalent to the uniform convergence of the net of associated distance functionals for the graphs with respect to each compatible metric on X×Y. Remarkably, no weaker convergence results if uniform convergence is replaced by pointwise convergence in the last statement.