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.     

Super edge-connectivity of mixed Cayley graph

A graph X is max-λ if λ(X)=δ(X). A graph X is super-λ if X is max-λ and every minimum edge-cut set of X isolates one vertex. In this paper, we proved that for all but a few exceptions, the mixed Cayley graph which is defined as a new kind of semi-regular graph is max-λ and super-λ.     

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.     

Minimum augmentation of local edge-connectivity between vertices and vertex subsets in undirected graphs

Given an undirected multigraph G=(V,E), a family W of sets W⊆V of vertices (areas), and a requirement function r:W→Z⁺ (where Z⁺ is the set of nonnegative integers), we consider the problem of augmenting G by the smallest number of new edges so that the resulting graph has at least r(W) edge-disjoint paths between v and W for every pair of a vertex v∈V and an area W∈W. So far this problem was shown to be NP-hard in the uniform case of r(W)=1 for each W∈W, and polynomially solvable in the uniform case of r(W)=r?2 for each W∈W. In this paper, we show that the problem can be solved in time, even if r(W)?2 holds for each W∈W, where n=|V|, m=|{{u,v}|(u,v)∈E}|, p=|W|, and r^*=max{r(W)∣W∈W}.     

欧拉图的hyper-Wiener指标

ε_n表示n个顶点欧拉图的集合.通过对欧拉图hyper-Wiener指标性质的研究,刻画了ε_n中具有最小和最大hyper-Wiener指标的极图.     

Two‐connected orientations of Eulerian graphs

A graph G = (V, E) is said to be weakly four‐connected if G is 4‐edge‐connected and G – x is 2‐edge‐connected for every x ∈ V. We prove that every weakly four‐connected Eulerian graph has a 2‐connected Eulerian orientation. This verifies a special case of a conjecture of A. Frank . © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 230–242, 2006     

Eulerian pairs and Eulerian recurrence systems

In this paper, we introduce the definitions of Eulerian pair and Hermite-Biehler pair. We also characterize a duality relation between Eulerian recurrences and Eulerian recurrence systems. This generalizes and unifies Hermite-Biehler decompositions of several enumerative polynomials, including up-down run polynomials for symmetric groups, alternating run polynomials for hyperoctahedral groups, flag descent polynomials for hyperoctahedral groups and flag ascent-plateau polynomials for Stirling permutations. We derive some properties of associated polynomials. In particular, we prove the alternatingly increasing property and the interlacing property of the ascent-plateau and left ascent-plateau polynomials for Stirling permutations.     

一类循环图中的Eulerian定向数

一般的图中Eulerian定向数的计数是#P-完全问题,但对于某些特殊图中的Eulerian定向数给出精确计数是完全有可能的.通过拆分解构的方法可以找到与一类循环图中Eulerian定向数有关的递推关系,从而给出该数的精确计数.前人的工作在于给出了一些近似估计.     

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.     

On cyclic edge-connectivity of fullerenes

A graph is said to be cyclically k-edge-connected, if at least k edges must be removed to disconnect it into two components, each containing a cycle. Such a set of k edges is called a cyclic-k-edge cutset and it is called a trivial cyclic-k-edge cutset if at least one of the resulting two components induces a single k-cycle.It is known that fullerenes, that is, 3-connected cubic planar graphs all of whose faces are pentagons and hexagons, are cyclically 5-edge-connected. In this article it is shown that a fullerene F containing a nontrivial cyclic-5-edge cutset admits two antipodal pentacaps, that is, two antipodal pentagonal faces whose neighboring faces are also pentagonal. Moreover, it is shown that F has a Hamilton cycle, and as a consequence at least 15·2^n/20-1/2 perfect matchings, where n is the order of F.     

Circular flows of nearly Eulerian graphs and vertex‐splitting

The odd edge connectivity of a graph G, denoted by λ_o(G), is the size of a smallest odd edge cut of the graph. Let S be any given surface and ? be a positive real number. We proved that there is a function f_S(?) (depends on the surface S and lim_?→0 f_S(?)=∞) such that any graph G embedded in S with the odd‐edge connectivity at least f_S(?) admits a nowhere‐zero circular (2+?)‐flow. Another major result of the work is a new vertex splitting lemma which maintains the old edge connectivity and graph embedding. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 147–161, 2002     

Compatible Eulerian circuits in Eulerian (di)graphs with generalized transition systems

A transition in a graph is defined as a pair of adjacent edges. A transition system of an Eulerian graph refers to a set of partitions such that for each vertex of the graph, there corresponds to a partition of the set of edges incident to the vertex into transitions. A generalized transition system $F\left(G\right)$ over a graph $G$ defines a set of transitions over $G$. A compatible Eulerian circuit of an Eulerian graph $G$ with a generalized transition system $F\left(G\right)$ is defined as an Eulerian circuit in which no two consecutive edges form a transition defined by $F\left(G\right)$. In this paper, we further introduce the concept of weakly generalized transition system which is an extension of the generalized transition system and prove some Ore-type sufficient conditions for the existence of compatible Eulerian circuits in Eulerian graphs with (weakly) generalized transition systems and obtain corresponding results for Eulerian digraphs. Our conditions improve some previous results due to Jackson and Isaak, respectively.     

Eulerian subgraphs in 3‐edge‐connected graphs and Hamiltonian line graphs

In this paper, we show that if G is a 3‐edge‐connected graph with and , then either G has an Eulerian subgraph H such that , or G can be contracted to the Petersen graph in such a way that the preimage of each vertex of the Petersen graph contains at least one vertex in S. If G is a 3‐edge‐connected planar graph, then for any , G has an Eulerian subgraph H such that . As an application, we obtain a new result on Hamiltonian line graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 308–319, 2003     

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.     

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.     

Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs

The circumference of a graph is the length of its longest cycles. Results of Jackson, and Jackson and Wormald, imply that the circumference of a 3-connected cubic n-vertex graph is Ω(n^0.694), and the circumference of a 3-connected claw-free graph is Ω(n^0.121). We generalize and improve the first result by showing that every 3-edge-connected graph with m edges has an Eulerian subgraph with Ω(m^0.753) edges. We use this result together with the Ryjá?ek closure operation to improve the lower bound on the circumference of a 3-connected claw-free graph to Ω(n^0.753). Our proofs imply polynomial time algorithms for finding large Eulerian subgraphs of 3-edge-connected graphs and long cycles in 3-connected claw-free graphs.