共查询到7条相似文献,搜索用时 0 毫秒
1.
In this paper we give simple degree sequence conditions for the equality of edge-connectivity and minimum degree of a (di-)graph. One of the conditions implies results by Bollobás, Goldsmith and White, and Xu. Moreover, we give analogue conditions for bipartite (di-)graphs. © 1997 John Wiley & Sons, Inc. J Graph Theory 26:27–34, 1997 相似文献
2.
图的限制性边连通度等于其最小边度的一个充分条件 总被引:6,自引:1,他引:5
设G是有限简单无向图.D,g和δ分别表示G的直径,围长和顶点最小度,本文证明,如果D≤g-2,且δ≥3,那么λ'=ξ,这里λ'=λ'(G)和ξ=ξ(G)分别表示G的限制性边连通度和最小边度,它在条件和结论两个方面都改进了已有的研究结果。 相似文献
3.
C. Balbuena 《Discrete Mathematics》2007,307(6):659-667
The restricted connectivity κ′(G) of a connected graph G is defined as the minimum cardinality of a vertex-cut over all vertex-cuts X such that no vertex u has all its neighbors in X; the superconnectivity κ1(G) is defined similarly, this time considering only vertices u in G-X, hence κ1(G)?κ′(G). The minimum edge-degree of G is ξ(G)=min{d(u)+d(v)-2:uv∈E(G)}, d(u) standing for the degree of a vertex u. In this paper, several sufficient conditions yielding κ1(G)?ξ(G) are given, improving a previous related result by Fiol et al. [Short paths and connectivity in graphs and digraphs, Ars Combin. 29B (1990) 17-31] and guaranteeing κ1(G)=κ′(G)=ξ(G) under some additional constraints. 相似文献
4.
5.
Let be a set of at least two vertices in a graph . A subtree of is a -Steiner tree if . Two -Steiner trees and are edge-disjoint (resp. internally vertex-disjoint) if (resp. and ). Let (resp. ) be the maximum number of edge-disjoint (resp. internally vertex-disjoint) -Steiner trees in , and let (resp. ) be the minimum (resp. ) for ranges over all -subset of . Kriesell conjectured that if for any , then . He proved that the conjecture holds for . In this paper, we give a short proof of Kriesell’s Conjecture for , and also show that (resp. ) if (resp. ) in , where . Moreover, we also study the relation between and , where is the line graph of . 相似文献
6.
Let G be an undirected graph and Gr be its r-th power. We study different issues dealing with the number of edges in G and Gr. In particular, we answer the following question: given an integer r≥2 and all connected graphs G of order n such that Gr≠Kn, what is the minimum number of edges that are added when going from G to Gr, and which are the graphs achieving this bound? 相似文献
7.