A sufficient condition for graphs to be weaklyk-linked

We consider graphs, which are finite, undirected, without loops and in which multiple edges are possible. For each natural numberk letg(k) be the smallest natural numbern, so that the following holds:LetG be ann-edge-connected graph and lets ₁,...,s _k,t ₁,...,t _k be vertices ofG. Then for everyi {1,..., k} there existsa pathP _i froms _i tot _i, so thatP ₁,...,P _k are pairwise edge-disjoint. We prove      

Independent cycles with limited size in a graph

Letk and s be two positive integers with s≥3. LetG be a graph of ordern ≥sk. Writen =qk + r, 0 ≤r ≤k - 1. Suppose thatG has minimum degree at least (s - l)k. Then G containsk independent cyclesC ₁,C ₂,...,C _k such thats ≤l(C _i ) ≤q for 1 ≤i ≤r arnds ≤l(C _i ) ≤q + 1 fork -r <i ≤k, where l(C_i) denotes the length ofC _i .     

On k-ordered Hamiltonian graphs

A Hamiltonian graph G of order n is k-ordered, 2 ≤ k ≤ n, if for every sequence v₁, v₂, …, v_k of k distinct vertices of G, there exists a Hamiltonian cycle that encounters v₁, v₂, …, v_k in this order. Define f(k, n) as the smallest integer m for which any graph on n vertices with minimum degree at least m is a k-ordered Hamiltonian graph. In this article, answering a question of Ng and Schultz, we determine f(k, n) if n is sufficiently large in terms of k. Let g(k, n) = − 1. More precisely, we show that f(k, n) = g(k, n) if n ≥ 11k − 3. Furthermore, we show that f(k, n) ≥ g(k, n) for any n ≥ 2k. Finally we show that f(k, n) > g(k, n) if 2k ≤ n ≤ 3k − 6. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 17–25, 1999     

Some Bistar Bipartite Ramsey Numbers

For bipartite graphs G ₁, G ₂, . . . ,G _k , the bipartite Ramsey number b(G ₁, G ₂, . . . , G _k ) is the least positive integer b so that any colouring of the edges of K _b,b with k colours will result in a copy of G _i in the ith colour for some i. A tree of diameter three is called a bistar, and will be denoted by B(s, t), where s ≥ 2 and t ≥ 2 are the degrees of the two support vertices. In this paper we will obtain some exact values for b(B(s, t), B(s, t)) and b(B(s, s), B(s, s)). Furtermore, we will show that if k colours are used, with k ≥ 2 and s ≥ 2, then \({b_{k}(B(s, s)) \leq \lceil k(s - 1) + \sqrt{(s - 1)^{2}(k^{2} - k) - k(2s - 4)} \rceil}\) . Finally, we show that for s ≥ 3 and k ≥ 2, the Ramsey number \({r_{k}(B(s, s)) \leq \lceil 2k(s - 1)+ \frac{1}{2} + \frac{1}{2} \sqrt{(4k(s - 1) + 1)^{2} - 8k(2s^{2} - s - 2)} \rceil}\) .     

The extremal function for 3-linked graphs

A graph is k-linked if for every set of 2k distinct vertices {s₁,…,s_k,t₁,…,t_k} there exist disjoint paths P₁,…,P_k such that the endpoints of P_i are s_i and t_i. 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.     

Paths,cycles, and arc-connectivity in digraphs

In this paper we prove the following theorem: Let D be a k-arcconnected digraph (multiple arcs allowed). If x is a vertex of D and / is an integer with / ≤ k, then for any / disjoint arc pairs {f₁, g₁}, ?, {f₁, g₁}, where f₁, ?, f₁ are arcs with head at x and g₁, ?, g₁ are arcs with tail at x, there exist in D / arc-disjoint cycles C₁, ?, C₁ such that {f_i, g_i} ? E(C_i) for each i (E(C_i) denotes the arc set of C_i) and such that D - ∪ E(C_i) is (k - 1)-arc-connected. Several interesting results are deduced from this theorem. Our results generalize the early works of Mader (“On a Property of n-Edge-Connected Digraphs,” Combinatorica, vol. 1 [1981], pp. 385-386) and Shiloach (“Edge-Disjoint Branching in Directed Multigraphs,” Information Processing Letters, vol. 8 [1979], pp. 24-27). An extension of Mader's theorem about admissible liftings of digraphs is also obtained in this paper. © 1995 John Wiley & Sons, Inc.     

Covering the vertices of a graph by cycles of prescribed length

The main theorem of that paper is the following: let G be a graph of order n, of size at least (n² - 3n + 6)/2. For any integers k, n₁, n₂,…,n_k such that n = n₁ + n₂ +. + n_k and n_i ? 3, there exists a covering of the vertices of G by disjoint cycles (C_i) =l…k with |C_i| = ni, except when n = 6, n₁ = 3, n₂ = 3, and G is isomorphic to G₁, the complement of G₁ consisting of a C₃ and a stable set of three vertices, or when n = 9, n₁ = n₂ = n₃ = 3, and G is isomorphic to G₂, the complement of G₂ consisting of a complete graph on four vertices and a stable set of five vertices. We prove an analogous theorem for bipartite graphs: let G be a bipartite balanced graph of order 2n, of size at least n² - n + 2. For any integers s, n₁, n₂,…,n_s with n_i ? 2 and n = n₁ + n₂ + ? + n_s, there exists a covering of the vertices of G by s disjoint cycles C_i, with |C_i| = 2n_i.     

Covering a graph with cycles passing through given edges

We propose a conjecture: for each integer k ≥ 2, there exists N(k) such that if G is a graph of order n ≥ N(k) and d(x) + d(y) ≥ n + 2k - 2 for each pair of non-adjacent vertices x and y of G, then for any k independent edges e₁, …, e_k of G, there exist k vertex-disjoint cycles C₁, …, C_k in G such that e_i ∈ E(C_i) for all i ∈ {1, …, k} and V(C₁ ∪ ···∪ C_k) = V(G). If this conjecture is true, the condition on the degrees of G is sharp. We prove this conjecture for the case k = 2 in the paper. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 105–109, 1997     

On degrees of maps between Grassmannians

Let G_n,k denote the oriented grassmann manifold of orientedk-planes in ℝⁿ. It is shown that for any continuous mapf: G_n,k → G_n,k, dim G_n,k = dim G_m,l = l(m −l), the Brouwer’s degree is zero, providedl > 1,n ≠ m. Similar results for continuous mapsg: ℂG_m,l → ℂG_n,k,h: ℍG_m,l → ℍG_n,k, 1 ≤ l < k ≤ n/2, k(n — k) = l(m — l) are also obtained.     

Multicommodity flows in graphs

Suppose that G is a graph, and (s_i,t_i) (1≤i≤k) are pairs of vertices; and that each edge has a integer-valued capacity (≥0), and that q_i≥0 (1≤i≤k) are integer-valued demands. When is there a flow for each i, between s_i and t_i and of value q_i, such that the total flow through each edge does not exceed its capacity? Ford and Fulkerson solved this when k=1, and Hu when k=2. We solve it for general values of k, when G is planar and can be drawn so that s₁,…, s_l, t₁, …, t_l,…,t_l are all on the boundary of a face and s_l+1, …,S_k, t_l+1,…,t_k are all on the boundary of the infinite face or when t₁=?=t_l and G is planar and can be drawn so that s_l+1,…,s_k, t₁,…,t_k are all on the boundary of the infinite face. This extends a theorem of Okamura and Seymour.     

Disjoint homotopic paths and trees in a planar graph

In this paper we describe a polynomial-time algorithm for the following problem:given: a planar graphG embedded in ℝ², a subset {I ₁, …,I _p} of the faces ofG, and pathsC ₁, …,C _k inG, with endpoints on the boundary ofI ₁ ∪ … ∪I _p; find: pairwise disjoint simple pathsP ₁, …,P _k inG so that, for eachi=1, …,k, P _i is homotopic toC _i in the space ℝ²\(I ₁ ∪ … ∪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 ℝ² and pairwise disjoint setsW ₁, …,W _k of vertices, which can be covered by the boundaries of at mostp faces ofG;find: pairwise vertex-disjoint subtreesT ₁, …,T _k ofG whereT _i (i=1, …, k).     

An improved linear edge bound for graph linkages

A graph is said to be k-linked if it has at least 2k vertices and for every sequence s₁,…,s_k,t₁,…,t_k of distinct vertices there exist disjoint paths P₁,…,P_k such that the ends of P_i are s_i and t_i. Bollobás and Thomason showed that if a simple graph G on n vertices is 2k-connected and G has at least 11kn edges, then G is k-linked. We give a relatively simple inductive proof of the stronger statement that 8kn edges and 2k-connectivity suffice, and then with more effort improve the edge bound to 5kn.     

A sufficient condition for a graph to be weakly k-linked

For a pair (s, t) of vertices of a graph G, let λ_G(s, t) denote the maximal number of edge-disjoint paths between s and t. Let (s₁, t₁), (s₂, t₂), (s₃, t₃) be pairs of vertices of G and k > 2. It is shown that if λ_G(s_i, t_i) ≥ 2k + 1 for each i = 1, 2, 3, then there exist 2k + 1 edge-disjoint paths such that one joins s₁ and t₁, another joins s₂ and t₂ and the others join s₃ and t₃. As a corollary, every (2k + 1)-edge-connected graph is weakly (k + 2)-linked for k ≥ 2, where a graph is weakly k-linked if for any k vertex pairs (s_i, t_i), 1 ≤ i ≤ k, there exist k edge-disjoint paths P₁, P₂,…, P_k such that P_i joins s_i and t_i for i = 1, 2,…, k.     

Edge-colored saturated graphs

A graph G is (k₁, k₂, …, k_t)-saturated if there exists a coloring C of the edges of G in t colors 1, 2, …, t in such a way that there is no monochromatic complete k_i-subgraph K of color i, 1 ? i ? t, but the addition of any new edge of color i, joining two nonadjacent vertices in G, with C, creates a monochromatic K of color i, 1 ? i ? t. We determine the maximum and minimum number of edges in such graphs and characterize the unique extremal graphs.     

Copositive pointwise approximation

We prove that if a functionf ∈C ⁽¹⁾ (I),I: = [?1, 1], changes its signs times (s ∈ ?) within the intervalI, then, for everyn > C, whereC is a constant which depends only on the set of points at which the function changes its sign, andk ∈ ?, there exists an algebraic polynomialP _n =P _n (x) of degree ≤n which locally inherits the sign off(x) and satisfies the inequality $$\left| {f\left( x \right) - P_n \left( x \right)} \right| \leqslant c\left( {s,k} \right)\left( {\frac{1}{{n^2 }} + \frac{{\sqrt {1 - x^2 } }}{n}} \right)\omega _k \left( {f'; \frac{1}{{n^2 }} + \frac{{\sqrt {1 - x^2 } }}{n}} \right), x \in I$$ , where ω _k (f′;t) is thekth modulus of continuity of the functionf’. It is also shown that iff ∈C (I) andf(x) ≥ 0,x ∈I then, for anyn ≥k ? 1, there exists a polynomialP _n =P _n (x) of degree ≤n such thatP _n (x) ≥ 0,x ∈I, and |f(x) ?P _n (x)| ≤c(k)ω _k (f;n ^?2 +n ^?1 √1 ?x ²),x ∈I.     

Nonsingular Equations over Groups II

Let G be a group, t an element distinct from G, and r(t) = g ₁ t ^{l ₁} …g _k t ^{l _k}  ∈ G* ?t?, where each g _i is an element of G order greater than 2, and the l _i are nonzero integers such that l ₁ + l ₂+…+l _k  ≠ 0 and |l _i | ≠ |l _j | for i ≠ j. We prove that if k = 4, then the natural map from G to the one-relator product ?G*t | r(t)? is injective. This together with previous results show that the natural map from G is injective for k ≥ 1.     

Two comments on Dvoretzky’s sphericity theorem

For any two positive integersk, l and anyɛ>0 there exists anN(k, l, ɛ) so that given anyl convex bodiesC ₁, …,C _l symmetric about the origin inE ⁿ withn≧N there exists a subspaceE ^k so that eachC _i intersectsE ^k, or has a projection intoE ^k, in a set which is nearly spherical (asphericity <ɛ). The measure of the totality ofE ^k which intersect a given body inE ⁿ in a nearly ellipsoidal set is considered and an affine invariant measure is introduced for that purpose.     

Mixed ramsey numbers: Chromatic numbers versus graphs

For positive integers n₁, n₂, …, n_I and graphs G_I+1, G_I+2, …, G_k, 1 ≤ / < k, the mixed Ramsey number _χ(n₁, …, n₁, G_I+1, …, G_k) is define as the least positive integer p such that for each factorization K_p = F₁⊕ … ⊕ F_⊕ F_I+1⊕ … ⊕ F_k, it it follows that χ(F_i) ≥ n_i for some i, 1 ? i ? l, or G_i is a subgraph of F_i for some i, l < i ? k. Formulas are presented for maxed Ramsey numbers in which the graphs G_I+1, G_I+2, …, G_k are connected, and in which k = I+1 and G_I+1 is arbitray.     

Highly linked graphs

A graph with at least 2k vertices is said to bek-linked if, for any choices ₁,...,s _k ,t ₁,...,t _k of 2k distinct vertices there are vertex disjoint pathsP ₁,...,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.