共查询到20条相似文献,搜索用时 312 毫秒
1.
Matthias Kriesell 《Journal of Graph Theory》2009,62(2):188-198
A set A of vertices of an undirected graph G is called k‐edge‐connected in G if for all pairs of distinct vertices a, b∈A, there exist k edge disjoint a, b‐paths in G. An A‐tree is a subtree of G containing A, and an A‐bridge is a subgraph B of G which is either formed by a single edge with both end vertices in A or formed by the set of edges incident with the vertices of some component of G ? A. It is proved that (i) if A is k·(? + 2)‐edge‐connected in G and every A‐bridge has at most ? vertices in V(G) ? A or at most ? + 2 vertices in A then there exist k edge disjoint A‐trees, and that (ii) if A is k‐edge‐connected in G and B is an A‐bridge such that B is a tree and every vertex in V(B) ? A has degree 3 then either A is k‐edge‐connected in G ? e for some e∈E(B) or A is (k ? 1)‐edge‐connected in G ? E(B). © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 188–198, 2009 相似文献
2.
Matthias Kriesell 《Journal of Graph Theory》2001,36(1):35-51
A noncomplete graph G is called an (n, k)‐graph if it is n‐connected and G − X is not (n − |X| + 1)‐connected for any X ⊆ V(G) with |X| ≤ k. Mader conjectured that for k ≥ 3 the graph K2k + 2 − (1‐factor) is the unique (2k, k)‐graph. We settle this conjecture for strongly regular graphs, for edge transitive graphs, and for vertex transitive graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 35–51, 2001 相似文献
3.
The central observation of this paper is that if εn random arcs are added to any n‐node strongly connected digraph with bounded degree then the resulting graph has diameter 𝒪(lnn) with high probability. We apply this to smoothed analysis of algorithms and property testing. Smoothed Analysis: Recognizing strongly connected digraphs is a basic computational task in graph theory. Even for digraphs with bounded degree, it is NL‐complete. By XORing an arbitrary bounded degree digraph with a sparse random digraph R ∼ 𝔻n,ε/n we obtain a “smoothed” instance. We show that, with high probability, a log‐space algorithm will correctly determine if a smoothed instance is strongly connected. We also show that if NL ⫅̸ almost‐L then no heuristic can recognize similarly perturbed instances of (s,t)‐connectivity. Property Testing: A digraph is called k‐linked if, for every choice of 2k distinct vertices s1,…,sk,t1,…,tk, the graph contains k vertex disjoint paths joining sr to tr for r = 1,…,k. Recognizing k‐linked digraphs is NP‐complete for k ≥ 2. We describe a polynomial time algorithm for bounded degree digraphs, which accepts k‐linked graphs with high probability, and rejects all graphs that are at least εn arcs away from being k‐linked. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007 相似文献
4.
Let G be a 2‐edge‐connected undirected graph, A be an (additive) abelian group and A* = A?{0}. A graph G is A‐connected if G has an orientation D(G) such that for every function b: V(G)?A satisfying , there is a function f: E(G)?A* such that for each vertex v∈V(G), the total amount of f values on the edges directed out from v minus the total amount of f values on the edges directed into v equals b(v). For a 2‐edge‐connected graph G, define Λg(G) = min{k: for any abelian group A with |A|?k, G is A‐connected }. In this article, we prove the following Ramsey type results on group connectivity:
- Let G be a simple graph on n?6 vertices. If min{δ(G), δ(Gc)}?2, then either Λg(G)?4, or Λg(Gc)?4.
- Let Z3 denote the cyclic group of order 3, and G be a simple graph on n?44 vertices. If min{δ(G), δ(Gc)}?4, then either G is Z3‐connected, or Gc is Z3‐connected. © 2011 Wiley Periodicals, Inc. J Graph Theory
5.
For a connected simple graph G, the eccentricity ec(v) of a vertex v in G is the distance from v to a vertex farthest from v, and d(v) denotes the degree of a vertex v. The eccentric connectivity index of G, denoted by ξc(G), is defined as v∈V(G)d(v)ec(v). In this paper, we will determine the graphs with maximal eccentric connectivity index among the connected graphs with n vertices and m edges(n ≤ m ≤ n + 4), and propose a conjecture on the graphs with maximal eccentric connectivity index among the connected graphs with n vertices and m edges(m ≥ n + 5). 相似文献
6.
Given a hypergraph, a partition of its vertex set, and a nonnegative integer k, find a minimum number of graph edges to be added between different members of the partition in order to make the hypergraph k‐edge‐connected. This problem is a common generalization of the following two problems: edge‐connectivity augmentation of graphs with partition constraints (J. Bang‐Jensen, H. Gabow, T. Jordán, Z. Szigeti, SIAM J Discrete Math 12(2) (1999), 160–207) and edge‐connectivity augmentation of hypergraphs by adding graph edges (J. Bang‐Jensen, B. Jackson, Math Program 84(3) (1999), 467–481). We give a min–max theorem for this problem, which implies the corresponding results on the above‐mentioned problems, and our proof yields a polynomial algorithm to find the desired set of edges. 相似文献
7.
Y-Chuang Chen Jimmy J. M. Tan Lih-Hsing Hsu Shin-Shin Kao 《Applied mathematics and computation》2003,140(2-3):245-254
Let G=(V,E) be a k-regular graph with connectivity κ and edge connectivity λ. G is maximum connected if κ=k, and G is maximum edge connected if λ=k. Moreover, G is super-connected if it is a complete graph, or it is maximum connected and every minimum vertex cut is {x|(v,x)E} for some vertex vV; and G is super-edge-connected if it is maximum edge connected and every minimum edge disconnecting set is {(v,x)|(v,x)E} for some vertex vV. In this paper, we present three schemes for constructing graphs that are super-connected and super-edge-connected. Applying these construction schemes, we can easily discuss the super-connected property and the super-edge-connected property of hypercubes, twisted cubes, crossed cubes, möbius cubes, split-stars, and recursive circulant graphs. 相似文献
8.
Edward A. Bender E. Rodney Canfield Brendan D. McKay 《Random Structures and Algorithms》1990,1(2):127-169
Let c(n, q) be the number of connected labeled graphs with n vertices and q ≤ N = (2n ) edges. Let x = q/n and k = q ? n. We determine functions wk ? 1. a(x) and φ(x) such that c(n, q) ? wk(qN)enφ(x)+a(x) uniformly for all n and q ≥ n. If ? > 0 is fixed, n→ ∞ and 4q > (1 + ?)n log n, this formula simplifies to c(n, q) ? (Nq) exp(–ne?2q/n). on the other hand, if k = o(n1/2), this formula simplifies to c(n, n + k) ? 1/2 wk (3/π)1/2 (e/12k)k/2nn?(3k?1)/2. 相似文献
9.
Let G = (V,E) be a graph or digraph and r : V → Z+. An r‐detachment of G is a graph H obtained by ‘splitting’ each vertex ν ∈ V into r(ν) vertices. The vertices ν1,…,νr(ν) obtained by splitting ν are called the pieces of ν in H. Every edge uν ∈ E corresponds to an edge of H connecting some piece of u to some piece of ν. Crispin Nash‐Williams 9 gave necessary and sufficient conditions for a graph to have a k‐edge‐connected r‐detachment. He also solved the version where the degrees of all the pieces are specified. In this paper, we solve the same problems for directed graphs. We also give a simple and self‐contained new proof for the undirected result. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 67–77, 2003 相似文献
10.
In 1950s, Tutte introduced the theory of nowhere-zero flows as a tool to investigate the coloring problem of maps, together
with his most fascinating conjectures on nowhere-zero flows. These have been extended by Jaeger et al. in 1992 to group connectivity,
the nonhomogeneous form of nowhere-zero flows. Let G be a 2-edge-connected undirected graph, A be an (additive) abelian group and A* = A − {0}. The graph G is A-connected if G has an orientation D(G) such that for every map b: V (G) ↦ A satisfying Σ
v∈V(G)
b(v) = 0, there is a function f: E(G) ↦ A* such that for each vertex v ∈ V (G), the total amount of f-values on the edges directed out from v minus the total amount of f-values on the edges directed into v is equal to b(v). The group coloring of a graph arises from the dual concept of group connectivity. There have been lots of investigations
on these subjects. This survey provides a summary of researches on group connectivity and group colorings of graphs. It contains
the following sections.
1. |
Nowhere-zero Flows and Group Connectivity of Graphs 相似文献
11.
We consider random walks on several classes of graphs and explore the likely structure of the vacant set, i.e. the set of unvisited vertices. Let Γ(t) be the subgraph induced by the vacant set of the walk at step t. We show that for random graphs Gn,p (above the connectivity threshold) and for random regular graphs Gr,r ≥ 3, the graph Γ(t) undergoes a phase transition in the sense of the well‐known ErdJW‐RSAT1100590x.png ‐Renyi phase transition. Thus for t ≤ (1 ‐ ε)t*, there is a unique giant component, plus components of size O(log n), and for t ≥ (1 + ε)t* all components are of size O(log n). For Gn,p and Gr we give the value of t*, and the size of Γ(t). For Gr, we also give the degree sequence of Γ(t), the size of the giant component (if any) of Γ(t) and the number of tree components of Γ(t) of a given size k = O(log n). We also show that for random digraphs Dn,p above the strong connectivity threshold, there is a similar directed phase transition. Thus for t ≤ (1 ‐ ε)t*, there is a unique strongly connected giant component, plus strongly connected components of size O(log n), and for t ≥ (1 + ε)t* all strongly connected components are of size O(log n). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012 相似文献
12.
For a graph G we define a graph T(G) whose vertices are the triangles in G and two vertices of T(G) are adjacent if their corresponding triangles in G share an edge. Kawarabayashi showed that if G is a k‐connected graph and T(G) contains no edge, then G admits a k‐contractible clique of size at most 3, generalizing an earlier result of Thomassen. In this paper, we further generalize Kawarabayashi's result by showing that if G is k‐connected and the maximum degree of T(G) is at most 1, then G admits a k‐contractible clique of size at most 3 or there exist independent edges e and f of G such that e and f are contained in triangles sharing an edge and G/e/f is k‐connected. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 121–136, 2007 相似文献
13.
LetF(W) be a Wiener functional defined byF(W)=I
n(f) whereI
n(f) denotes the multiple Wiener-Ito integral of ordern of the symmetricL
2([0, 1]
n
) kernelf. We show that a necessary and sufficient condition for the existence of a continuous extension ofF, i.e. the existence of a function ø(·) from the continuous functions on [0, 1] which are zero at zero to which is continuous in the supremum norms and for which ø(W)=F(W) a.s, is that there exists a multimeasure (dt
1,...,dt
n
) on [0, 1]
n
such thatf(t
1, ...,t
n
) = ((t
1, 1]), ..., (t
n
, 1]) a.e. Lebesgue on [0, 1]
n
. Recall that a multimeasure (A
1,...,A
n
) is for every fixedi and every fixedA
i,...,Ai-1, Ai+1,...,An a signed measure inA
i
and there exists multimeasures which are not measures. It is, furthermore, shown that iff(t
1,t
2, ...,t
n
) = ((t
1, 1], ..., (t
n
, 1]) then all the tracesf
(k),
off exist, eachf(k) induces ann–2k multimeasure denoted by (k), the following relation holds
|
设为首页 | 免责声明 | 关于勤云 | 加入收藏 |
Copyright©北京勤云科技发展有限公司 京ICP备09084417号 |