共查询到20条相似文献,搜索用时 31 毫秒
1.
Non-Separating Paths in 4-Connected Graphs 总被引:2,自引:0,他引:2
In 1975, Lovász conjectured that for any positive integer k, there exists a minimum positive integer f(k) such that, for any two vertices x, y in any f(k)-connected graph G, there is a path P from x to y in G such that G–V(P) is k-connected. A result of Tutte implies f(1) = 3. Recently, f(2) = 5 was shown by Chen et al. and, independently, by Kriesell. In this paper, we show that f(2) = 4 except for double wheels.Received October 17, 2003 相似文献
2.
Arc-disjoint in-trees in directed graphs 总被引:2,自引:0,他引:2
Given a directed graph D = (V,A) with a set of d specified vertices S = {s
1,…, s
d
} ⊆ V and a function f: S → ℕ where ℕ denotes the set of natural numbers, we present a necessary and sufficient condition such that there exist Σ
i=1
d
f(s
i
) arc-disjoint in-trees denoted by T
i,1,T
i,2,…, for every i = 1,…,d such that T
i,1,…, are rooted at s
i
and each T
i,j
spans the vertices from which s
i
is reachable. This generalizes the result of Edmonds [2], i.e., the necessary and sufficient condition that for a directed
graph D=(V,A) with a specified vertex s∈V, there are k arc-disjoint in-trees rooted at s each of which spans V. Furthermore, we extend another characterization of packing in-trees of Edmonds [1] to the one in our case.
Supported by JSPS Research Fellowships for Young Scientists.
Supported by the project New Horizons in Computing, Grand-in-Aid for Scientific Research on Priority Areas, MEXT Japan. 相似文献
3.
A k-tree of a graph is a spanning tree with maximum degree at most k. We give sufficient conditions for a graph G to have a k-tree with specified leaves: Let k,s, and n be integers such that k≥2, 0≤s≤k, and n≥s+1. Suppose that (1) G is (s+1)-connected and the degree sum of any k independent vertices of G is at least |G|+(k−1)s−1, or (2) G is n-connected and the independence number of G is at most (n−s)(k−1)+1. Then for any s specified vertices of G, G has a k-tree containing them as leaves. We also discuss the sharpness of the results.
This research was partially supported by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Encouragement
of Young Scientists, 15740077, 2005
This research was partially supported by the Japan Society for the Promotion of Science for Young Scientists. 相似文献
4.
Carsten Thomassen 《Combinatorica》2001,21(2):321-333
Dedicated to the memory of Paul Erdős
A graph G is k-linked if G has at least 2k vertices, and, for any vertices , , ..., , , , ..., , G contains k pairwise disjoint paths such that joins for i = 1, 2, ..., k. We say that G is k-parity-linked if G is k-linked and, in addition, the paths can be chosen such that the parities of their lengths are prescribed. We prove the existence of a function g(k) such that every g(k)-connected graph is k-parity-linked if the deletion of any set of less than 4k-3 vertices leaves a nonbipartite graph. As a consequence, we obtain a result of Erdős–Pósa type for odd cycles in graphs
of large connectivity. Also, every -connected graph contains a totally odd -subdivision, that is, a subdivision of in which each edge of corresponds to an odd path, if and only if the deletion of any vertex leaves a nonbipartite graph.
Received May 13, 1999/Revised June 19, 2000 相似文献
5.
Akira Saito 《Combinatorica》1996,16(3):433-437
A graphG is said to bek-path-connected if every pair of distinct vertices inG are joined by a path of length at leastk. We prove that if max{deg
G
x
, deg
G
y
}k for every pair of verticesx,y withd
G
(x,y)=2 in a 2-connected graphG, whered
G
(x,y) is the distance betweenx andy inG, thenG isk-path-connected. 相似文献
6.
Very Asymmetric Marking Games 总被引:1,自引:0,他引:1
We investigate a competitive version of the coloring number of a graph G = (V, E). For a fixed linear ordering L of V let s (L) be one more than the maximum outdegree of G when G is oriented so that x ← y if x <
L
y. The coloring number of G is the minimum of s (L) over all such orderings. The (a, b)-marking game is played on a graph G = (V, E) as follows. At the start all vertices are unmarked. The players, Alice and Bob, take turns playing. A play consists of Alice
marking a unmarked vertices or Bob marking b unmarked vertices. The game ends when there are no remaining unmarked vertices. Together the players create a linear ordering
L of V defined by x < y if x is marked before y. The score of the game is s (L). The (a, b)-game coloring number of G is the minimum score that Alice can obtain regardless of Bob’s strategy. The usual (1, 1)-marking game is well studied and
there are many interesting results. Our main result is that if G has an orientation with maximum outdegree k then the (k, 1)-game coloring number of G is at most 2k + 2. This extends a fundamental result on the (1, 1)-game coloring number of trees. We also construct examples to show that
this bound is tight for many classes of graphs. Finally we prove bounds on the (a, 1)-game coloring number when a < k. 相似文献
7.
Claude Berge 《Combinatorica》1982,2(3):213-222
Gallai and Milgram have shown that the vertices of a directed graph, with stability number α(G), can be covered by exactly α(G) disjoint paths. However, the various proofs of this result do not imply the existence of a maximum stable setS and of a partition of the vertex-set into paths μ1, μ2, ..., μk such tht |μi ∩S|=1 for alli.
Later, Gallai proved that in a directed graph, the maximum number of vertices in a path is at least equal to the chromatic
number; here again, we do not know if there exists an optimal coloring (S
1,S
2, ...,S
k) and a path μ such that |μ ∩S
i|=1 for alli.
In this paper we show that many directed graphs, like the perfect graphs, have stronger properties: for every maximal stable
setS there exists a partition of the vertex set into paths which meet the stable set in only one point. Also: for every optimal
coloring there exists a path which meets each color class in only one point. This suggests several conjecties similar to the
perfect graph conjecture.
Dedicated to Tibor Gallai on his seventieth birthday 相似文献
8.
An edge e of a k-connected graph G is said to be a removable edge if G ⊖ e is still k-connected, where G ⊖ e denotes the graph obtained from G by deleting e to get G − e, and for any end vertex of e with degree k − 1 in G − e, say x, delete x, and then add edges between any pair of non-adjacent vertices in N
G−e
(x). The existence of removable edges of k-connected graphs and some properties of 3-connected graphs and 4-connected graphs have been investigated. In the present
paper, we investigate some properties of k-connected graphs and study the distribution of removable edges on a cycle in a k-connected graph (k ≥ 4). 相似文献
9.
The k-th power of a graph G is the graph whose vertex set is V(G)
k
, where two distinct k-tuples are adjacent iff they are equal or adjacent in G in each coordinate. The Shannon capacity of G, c(G), is lim
k→∞
α(G
k
)1/k
, where α(G) denotes the independence number of G. When G is the characteristic graph of a channel C, c(G) measures the effective alphabet size of C in a zero-error protocol. A sum of channels, C = Σ
i
C
i
, describes a setting when there are t ≥ 2 senders, each with his own channel C
i
, and each letter in a word can be selected from any of the channels. This corresponds to a disjoint union of the characteristic
graphs, G = Σ
i
G
i
. It is well known that c(G) ≥ Σ
i
c(G
i
), and in [1] it is shown that in fact c(G) can be larger than any fixed power of the above sum.
We extend the ideas of [1] and show that for every F, a family of subsets of [t], it is possible to assign a channel C
i
to each sender i ∈ [t], such that the capacity of a group of senders X ⊂ [t] is high iff X contains some F ∈ F. This corresponds to a case where only privileged subsets of senders are allowed to transmit in a high rate. For instance,
as an analogue to secret sharing, it is possible to ensure that whenever at least k senders combine their channels, they obtain a high capacity, however every group of k − 1 senders has a low capacity (and yet is not totally denied of service). In the process, we obtain an explicit Ramsey construction
of an edge-coloring of the complete graph on n vertices by t colors, where every induced subgraph on exp vertices contains all t colors.
Research supported in part by a USA-Israeli BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva
Center for Geometry at Tel Aviv University.
Research partially supported by a Charles Clore Foundation Fellowship. 相似文献
10.
It is proved that for every positive integer k, every n-connected graph G of sufficiently large order contains a set W of k vertices such that G—W is (n-2)-connected. It is shown that this does not remain true if we add the condition that G(W) is connected. 相似文献
11.
A graph is k-linked if for every set of 2k distinct vertices {s1,…,sk,t1,…,tk} there exist disjoint paths P1,…,Pk such that the endpoints of Pi are si and ti. We prove every 6-connected graph on n vertices with 5n−14 edges is 3-linked. This is optimal, in that there exist 6-connected graphs on n vertices with 5n−15 edges that are not 3-linked for arbitrarily large values of n. 相似文献
12.
Highly linked graphs 总被引:6,自引:0,他引:6
A graph with at least 2k vertices is said to bek-linked if, for any choices
1,...,s
k
,t
1,...,t
k
of 2k distinct vertices there are vertex disjoint pathsP
1,...,P
k
withP
i
joinings
i
tot
i
, 1ik. Recently Robertson and Seymour [16] showed that a graphG isk-linked provided its vertex connectivityk(G) exceeds
. We show here thatk(G)22k will do. 相似文献
13.
Graph Connectivity After Path
Removal 总被引:1,自引:0,他引:1
Let G be a graph and
u, v be two distinct vertices of
G. A u—v path P is called nonseparating if
G—V(P) is connected. The purpose of this
paper is to study the number of nonseparating
u—v path for two arbitrary
vertices u and
v of a given graph. For a
positive integer k, we will
show that there is a minimum integer (k) so that if G is an (k)-connected graph and
u and v are two arbitrary vertices in
G, then there exist
k vertex disjoint paths
P
1[u,v], P
2[u,v], . . ., P
k
[u,v], such that G—V (P
i
[u,v]) is connected for every
i (i = 1, 2, ..., k). In fact, we will prove that
(k) 22k+2. It is known that (1) = 3.. A
result of Tutte showed that (2) = 3. We show that (3) = 6. In
addition, we prove that if G
is a 5-connected graph, then for every pair of vertices
u and v there exists a path
P[u, v] such that G—V(P[u,
v]) is 2-connected.* Supported by NSF grant No.
DMS-0070059 Supported by ONR grant
N00014-97-1-0499 Supported by NSF grant No. 9531824 相似文献
14.
Let G be a k-connected simple graph with order n. The k-diameter, combining connectivity with diameter, of G is the minimum integer d
k
(G) for which between any two vertices in G there are at least k internally vertex-disjoint paths of length at most d
k
(G). For a fixed positive integer d, some conditions to insure d
k
(G)⩽d are given in this paper. In particular, if d⩾3 and the sum of degrees of any s (s=2 or 3) nonadjacent vertices is at least n+(s−1)k+1−d, then d
k
(G)⩽d. Furthermore, these conditions are sharp and the upper bound d of k-diameter is best possible.
Supported by NNSF of China (19971086). 相似文献
15.
Dr. Matthias Kriesell 《Combinatorica》2006,26(3):277-314
A non-complete graph G is called an (n,k)-graph if it is n-connected but 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(up to isomorphism).
Here we prove this conjecture. 相似文献
16.
We prove that each 3-connected plane graph G without triangular or quadrangular faces either contains a k-path P
k
, a path on k vertices, such that each of its k vertices has degree ≤5/3k in G or does not contain any k-path. We also prove that each 3-connected pentagonal plane graph G which has a k-cycle, a cycle on k vertices, k∈ {5,8,11,14}, contains a k-cycle such that all its vertices have, in G, bounded degrees. Moreover, for all integers k and m, k≥ 3, k∉ {5,8,11,14} and m≥ 3, we present a graph in which every k-cycle contains a vertex of degree at least m.
Received: June 29, 1998 Final version received: April 11, 2000 相似文献
17.
G. R. T. Hendry 《Periodica Mathematica Hungarica》1990,21(3):205-218
A pathP in a graphG is said to beextendable if there exists a pathP’ inG with the same endvertices asP such thatV(P)⊆V (P’) and |V(P’)|=|V(P)|+1. A graphG ispath extendable if every nonhamiltonian path inG is extendable. We investigate the extent to which known sufficient conditions for a graph to be hamiltonian-connected imply
the extendability of paths in the graph. Several theorems are proved: for example, it is shown that ifG is a graph of orderp in which the degree sum of each pair of non-adjacent vertices is at leastp+1 andP is a nonextendable path of orderk inG thenk≤(p+1)/2 and 〈V (P)〉≅K
k
orK
k
−e. As corollaries of this we deduce that if δ(G)≥(p+2)/2 or if the degree sum of each pair of nonadjacent vertices inG is at least (3p−3)/2 thenG is path extendable, which strengthen results of Williamson [13]. 相似文献
18.
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). 相似文献
19.
Let G be a connected graph. We denote by σ(G,x) and δ(G) respectively the σ-polynomial and the edge-density of G, where
. If σ(G,x) has at least an unreal root, then G is said to be a σ-unreal graph. Let δ(n) be the minimum edgedensity over all n vertices graphs with σ-unreal roots. In this paper, by using the theory of adjoint polynomials, a negative answer to a problem posed by Brenti et
al. is given and the following results are obtained: For any positive integer a and rational number 0≤c≤1, there exists at least a graph sequence {G
i}1≤i≤a
such that G
i is σ-unreal and δ(G
i)→c as n→∞ for all 1 ≤i≤a, and moreover, δ(n)→0 as n→∞.
Supported by the National Natural Science Foundation of China (10061003) and the Science Foundation of the State Education
Ministry of China. 相似文献
20.
Mekkia Kouider 《Combinatorica》2000,20(2):219-226
G =(V,E) is a 2-connected graph, and X is a set of vertices of G such that for every pair x,x' in X, , and the minimum degree of the induced graph <X> is at least 3, then X is covered by one cycle.
This result will be in fact generalised by considering tuples instead of pairs of vertices.
Let be the minimum degree in the induced graph <X>. For any ,
.
If , and , then X is covered by at most (p-1) cycles of G. If furthermore , (p-1) cycles are sufficient.
So we deduce the following:
Let p and t () be two integers.
Let G be a 2-connected graph of order n, of minimum degree at least t. If , and , then V is covered by at most cycles, where k is the connectivity of G.
If furthermore , (p-1) cycles are sufficient.
In particular, if and , then G is hamiltonian.
Received April 3, 1998 相似文献