共查询到20条相似文献,搜索用时 15 毫秒
1.
Haruko Okamura 《Journal of Combinatorial Theory, Series B》1984,37(2):151-172
Mader proved that for every k-edge-connected graph G (k ≥ 4), there exists a path joining two given vertices such that the subgraph obtained from G by deleting the edges of the path is (k - 2)-edge-connected. A generalization of this and a sufficient condition for existance of 3, 4, or 5 terminus k edge-disjoint paths in graphs are given. 相似文献
2.
W. Mader 《Graphs and Combinatorics》1985,1(1):81-89
For every pair of verticesx andy in a connected, finite, undirected graphG, there is a pathP joiningx andy such that deleting the edges ofP fromG, for every pair of vertices ofG, the local edge-connectivity decreases by at most two. 相似文献
3.
Sebastian M. Cioab? 《Linear algebra and its applications》2010,432(1):458-470
In this paper, we show that if the second largest eigenvalue of a d-regular graph is less than , then the graph is k-edge-connected. When k is 2 or 3, we prove stronger results. Let ρ(d) denote the largest root of x3-(d-3)x2-(3d-2)x-2=0. We show that if the second largest eigenvalue of a d-regular graph G is less than ρ(d), then G is 2-edge-connected and we prove that if the second largest eigenvalue of G is less than , then G is 3-edge-connected. 相似文献
4.
5.
On conditional edge-connectivity of graphs 总被引:6,自引:0,他引:6
徐俊明 《应用数学学报(英文版)》2000,16(4):414-419
1. IntroductionIn this paper, a graph G ~ (V,E) always means a simple graph (without loops andmultiple edges) with the vertex-set V and the edge-set E. We follow [1] for graph-theoreticalterllilnology and notation not defined here.It is well known that when the underlying topology of a computer interconnectionnetwork is modeled by a graph G, the edge-connectivity A(G) of G is an important measurefor fault-tolerance of the network. However, it has many deficiencies (see [2]). MotiVatedby t… 相似文献
6.
C. Balbuena 《Discrete Applied Mathematics》2007,155(18):2444-2455
The product graph Gm*Gp of two given graphs Gm and Gp 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 Gm, Gp of minimum degrees δ(Gm), δ(Gp), respectively, we show that λ(Gm*Gp) is lower bounded by both δ(Gm)+λ(Gp) and δ(Gp)+λ(Gm), an improvement of what is known for the edge-connectivity of Gm×Gp. 相似文献
7.
8.
Zoltán Szigeti 《Discrete Applied Mathematics》2008,156(7):1011-1018
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. 相似文献
9.
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. 相似文献
10.
Bing Wang 《Discrete Mathematics》2009,309(13):4555-4563
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. 相似文献
11.
Linda Lesniak 《Discrete Mathematics》1974,8(4):351-354
It is shown that if G is a graph of order p ≥ 2 such that deg u + deg v ≥ p ? 1 for all pairs u, v of nonadjacent vertices, then the edge-connectivity of G equals the minimum degree of G. Furthermore, if deg u + deg v ≥ p for all pairs u, v of nonadjacent vertices, then either p is even and G is isomorphic to or every minimum cutset of edges of G consists of the collection of edges incident with a vertex of least degree. 相似文献
12.
Xingxing Yu 《Journal of Graph Theory》2006,51(3):175-198
An infinite graph is 2‐indivisible if the deletion of any finite set of vertices from the graph results in exactly one infinite component. Let G be a 4‐connected, 2‐indivisible, infinite, plane graph. It is known that G contains a spanning 1‐way infinite path. In this paper, we prove a stronger result by showing that, for any vertex x and any edge e on a facial cycle of G, there is a spanning 1‐way infinite path in G from x and through e. Results will be used in two forthcoming papers to establish a conjecture of Nash‐Williams. © 2005 Wiley Periodicals, Inc. J Graph Theory 相似文献
13.
Carsten Thomassen 《Combinatorica》2016,36(5):601-621
We prove a decomposition result for locally finite graphs which can be used to extend results on edge-connectivity from finite to infinite graphs. It implies that every 4k-edge-connected graph G contains an immersion of some finite 2k-edge-connected Eulerian graph containing any prescribed vertex set (while planar graphs show that G need not containa subdivision of a simple finite graph of large edge-connectivity). Also, every 8k-edge connected infinite graph has a k-arc-connected orientation, as conjectured in 1989. 相似文献
14.
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. 相似文献
15.
16.
Xue-gang Chen Shinya Fujita Michitaka Furuya Moo Young Sohn 《Discrete Applied Mathematics》2012,160(4-5):488-493
A graph is said to be bicritical if the removal of any pair of vertices decreases the domination number of . For a bicritical graph with the domination number , we say that is -bicritical. Let denote the edge-connectivity of . In [2], Brigham et al. (2005) posed the following question: If is a connected bicritical graph, is it true that In this paper, we give a negative answer toward this question; namely, we give a construction of infinitely many connected -bicritical graphs with edge-connectivity for every integer . Furthermore, we give some sufficient conditions for a connected -bicritical graph to have . 相似文献
17.
18.
19.
The bounded edge-connectivity λk(G) of a connected graph G with respect to is the minimum number of edges in G whose deletion from G results in a subgraph with diameter larger than k and the edge-persistence D+(G) is defined as λd(G)(G), where d(G) is the diameter of G. This paper considers the Cartesian product G1×G2, shows λk1+k2(G1×G2)≥λk1(G1)+λk2(G2) for k1≥2 and k2≥2, and determines the exact values of D+(G) for G=Cn×Pm, Cn×Cm, Qn×Pm and Qn×Cm. 相似文献
20.
XuJunming FanYingmei 《高校应用数学学报(英文版)》2004,19(4):449-454
The super edge-connectivity of a graph is an important parameter to measure fault-tolerance of interconnection networks. This note shows that the Kautz undirected graph is super edge-connected,and provides a short proof of Lue and Zhang‘s result on super edge-connectivity of the de Bruijn undirected graph. 相似文献