共查询到20条相似文献,搜索用时 15 毫秒
1.
Andrew Thomason 《Discrete Mathematics》2008,308(19):4370-4377
Given integers r and s, and n large compared to r and s, we determine the maximum size of a graph of order n having no minor isomorphic to sKr, the union of s disjoint copies of Kr.The extremal function depends on the relative sizes of r and s. If s is small compared to r the extremal function is essentially independent of s. On the other hand, if s is large compared to r, there is a unique extremal graph ; this assertion is a generalization of the case r=3 which is a classical result of Erd?s and Pósa. 相似文献
2.
The path-width of a graph is the minimum value ofk such that the graph can be obtained from a sequence of graphsG1,…,Gr each of which has at mostk + 1 vertices, by identifying some vertices ofGi pairwise with some ofGi+1 (1 ≤ i < r). For every forestH it is proved that there is a numberk such that every graph with no minor isomorphic toH has path-width?k. This, together with results of other papers, yields a “good” algorithm to test for the presence of any fixed forest as a minor, and implies that ifP is any property of graphs such that some forest does not have propertyP, then the set of minor-minimal graphs without propertyP is finite. 相似文献
3.
Disjoint paths in a rectilinear grid 总被引:2,自引:0,他引:2
A Frank 《Combinatorica》1982,2(4):361-371
We give a good characterization and a good algorithm for a special case of the integral multicommodity flow problem when the graph is defined by a rectangle on a rectilinear grid. The problem was raised by engineers motivated by some basic questions of constructing printed circuit boards. 相似文献
4.
Given k pairs of vertices (si,ti)(1≤i≤k) of a digraph G, how can we test whether there exist k vertex-disjoint directed paths from si to ti for 1≤i≤k? This is NP-complete in general digraphs, even for k=2 [2], but for k=2 there is a polynomial-time algorithm when G is a tournament (or more generally, a semicomplete digraph), due to Bang-Jensen and Thomassen [1]. Here we prove that for all fixed k there is a polynomial-time algorithm to solve the problem when G is semicomplete. 相似文献
5.
6.
The “tree-width” of a graph is defined and it is proved that for any fixed planar graph H, every planar graph with sufficiently large tree-width has a minor isomorphic to H. This result has several applications which are described in other papers in this series. 相似文献
8.
Cdric Bentz 《Discrete Applied Mathematics》2009,157(17):3558-3568
We generalize all the results obtained for maximum integer multiflow and minimum multicut problems in trees by Garg, Vazirani and Yannakakis [N. Garg, V.V. Vazirani, M. Yannakakis, Primal-dual approximation algorithms for integral flow and multicut in trees, Algorithmica 18 (1997) 3–20] to graphs with a fixed cyclomatic number, while this cannot be achieved for other classical generalizations of trees. We also introduce thek-edge-outerplanar graphs, a class of planar graphs with arbitrary (but bounded) tree-width that generalizes the cacti, and show that the integrality gap of the maximum edge-disjoint paths problem is bounded in these graphs. 相似文献
9.
Given a number of requests ?, we propose a polynomial-time algorithm for finding ? disjoint paths in a symmetric directed graph. It is known that the problem of finding ?≥2 disjoint paths in a directed graph is NP-hard [S. Fortune, J. Hopcroft, J. Wyllie, The directed subgraph homeomorphism problem, Journal of Theoretical Computer Science 10 (2) (1980) 111-121]. However, by studying minimal solutions it turns out that only a finite number of configurations are possible in a symmetric digraph. We use Robertson and Seymour’s polynomial-time algorithm [N. Robertson, P. D. Seymour, Graph minors xiii. The disjoint paths problem, Journal of Combinatorial Theory B (63) (1995) 65-110] to check the feasibility of each configuration. 相似文献
10.
It is an interesting problem that how much connectivity ensures the existence ofn disjoint paths joining givenn pairs of vertices, but to get a sharp bound seems to be very difficult. In this paper, we study how muchgeodetic connectivity ensures the existence ofn disjointgeodesics joining givenn pairs of vertices, where a graph is calledk-geodetically connected if the removal of anyk−1 vertices does not change the distance between any remaining vertices. 相似文献
11.
Bollobás and Thomason showed that every 22k‐connected graph is k‐linked. Their result used a dense graph minor. In this paper, we investigate the ties between small graph minors and linkages. In particular, we show that a 6‐connected graph with a K minor is 3‐linked. Further, we show that a 7‐connected graph with a K minor is (2,5)‐linked. Finally, we show that a graph of order n and size at least 7n?29 contains a K minor. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 75–91, 2005 相似文献
12.
A. Schrijver 《Discrete and Computational Geometry》1991,6(1):527-574
In this paper we describe a polynomial-time algorithm for the following problem:given: a planar graphG embedded in ℝ2, a subset {I
1, …,I
p} of the faces ofG, and pathsC
1, …,C
k inG, with endpoints on the boundary ofI
1 ∪ … ∪I
p; find: pairwise disjoint simple pathsP
1, …,P
k inG so that, for eachi=1, …,k, P
i is homotopic toC
i in the space ℝ2\(I
1 ∪ … ∪I
p).
Moreover, we prove a theorem characterizing the existence of a solution to this problem. Finally, we extend the algorithm
to disjoint homotopic trees. As a corollary we derive that, for each fixedp, there exists a polynormial-time algorithm for the problem:given: a planar graphG embedded in ℝ2 and pairwise disjoint setsW
1, …,W
k of vertices, which can be covered by the boundaries of at mostp faces ofG;find: pairwise vertex-disjoint subtreesT
1, …,T
k ofG whereT
i
(i=1, …, k). 相似文献
13.
《Journal of Algorithms in Cognition, Informatics and Logic》1986,7(3):309-322
We introduce an invariant of graphs called the tree-width, and use it to obtain a polynomially bounded algorithm to test if a graph has a subgraph contractible to H, where H is any fixed planar graph. We also nonconstructively prove the existence of a polynomial algorithm to test if a graph has tree-width ≤ w, for fixed w. Neither of these is a practical algorithm, as the exponents of the polynomials are large. Both algorithms are derived from a polynomial algorithm for the DISJOINT CONNECTING PATHS problem (with the number of paths fixed), for graphs of bounded tree-width. 相似文献
14.
Hikoe Enomoto 《Combinatorica》1998,18(4):487-492
G is a graph of order at least 3k with . Then G contains k vertex-disjoint cycles.
Received: April 23, 1998 相似文献
15.
S Gallivan 《Journal of Combinatorial Theory, Series A》1985,39(1):112-115
A Gale diagram technique is used to show that if d is positive integer greater than one, then there is a d-polytope P such that there are [] pairs of distinct vertices of P which cannot all be joined by disjoint paths in the graph of P. 相似文献
16.
Xingxing Yu 《Transactions of the American Mathematical Society》1997,349(4):1333-1358
We study the existence of certain disjoint paths in planar graphs and generalize a theorem of Thomassen on planarizing cycles in surfaces. Results are used to prove that every 5-connected triangulation of a surface with sufficiently large representativity is hamiltonian, thus verifying a conjecture of Thomassen. We also obtain results about spanning walks in graphs embedded in a surface with large representativity.
17.
There are three general lower bound techniques for the crossing numbers of graphs, all of which can be traced back to Leighton's work on applications of crossing number in VLSI: the Crossing Lemma, the Bisection Method, and the Embedding Method. In this contribution, we sketch their adaptations to the minor crossing number. 相似文献
18.
A. Hiraki 《European Journal of Combinatorics》1998,19(8):953-965
In this paper we give a sufficient condition for the existence of a strongly closed subgraph which is (cq+aq)-regular of diameterqcontaining a given pair of vertices at distanceqin a distance-regular graph. Moreover we show that a distance-regular graph withr = max {j| (cj,aj,bj) = (c1,a1,b1)} ,bq − 1>bqandcq+r = 1 satisfies our sufficient condition. 相似文献
19.
20.
G. R. Vijayakumar 《Graphs and Combinatorics》2011,27(1):143-148
A collection of nontrivial paths in a graph G is called a path pile of G, if every edge of G is on exactly one path and no two paths have a common internal vertex. The least number that can be the cardinality of a
path pile of G is called the path piling number of G. It can be shown that ε ≤ ν + η where ε, ν and η are respectively the size, the order and the path piling number of G. In this note we characterize structurally the class of all graphs for which the equality of this relation holds. 相似文献