Ramsey theory for graph connectivity

r_c(k) Denotes the smallest integer such that any c-edge-coloring of the r_c(k) vertex complete graph has a monochromatic k-connected subgraph. For any c, k ≧ 2, we show 2c(k – 1) + 1 ≦ r_c(k) < 10/3 c(k – 1) + 1, and further that 4(k – 1) + 1 ≧ r₂(k) < (3 + √ (k – 1) + 1. Some exact values for various Ramsey connectivity numbers are also computed.     

Mader’s Conjecture On Extremely Critical Graphs

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 K_2k+2−(1−factor) is the unique (2k,k)-graph(up to isomorphism). Here we prove this conjecture.     

On 2-Connected Spanning Subgraphs with Bounded Degree in K 1,r -Free Graphs

For any integer r > 1, an r-trestle of a graph G is a 2-connected spanning subgraph F with maximum degree Δ(F) ≤ r. A graph G is called K _1,r -free if G has no K _1,r as an induced subgraph. Inspired by the work of Ryjáček and Tkáč, we show that every 2-connected K _1,r -free graph has an r-trestle. The paper concludes with a corollary of this result for the existence of k-walks.     

Global Connectivity And Expansion: Long Cycles and Factors In f-Connected Graphs

Given a function f : ℕ→ℝ, call an n-vertex graph f-connected if separating off k vertices requires the deletion of at least f(k) vertices whenever k≤(n−f(k))/2. This is a common generalization of vertex connectivity (when f is constant) and expansion (when f is linear). We show that an f-connected graph contains a cycle of length linear in n if f is any linear function, contains a 1-factor and a 2-factor if f(k)≥2k+1, and contains a Hamilton cycle if f(k)≥2(k+1)². We conjecture that linear growth of f suffices to imply hamiltonicity.     

Cycles intersecting a prescribed vertex set

A graph is said to have property P(k,l)(k ? l) if for any X ∈ (^G_k) there exists a cycle such that |X ∩ V(C)| = l. Obviously an n-connected graph (n ? 2) satisfies P(n,n). In this paper, we study parameters k and l such that every n-connected graph satisfies P(k,l). We show that for r = 1 or 2 every n-connected graph satisfies P(n + r,n). For r = 3, there are infinitely many 3-connected graphs that do not satisfy P(6,3). However, if n ? max{3,(2r ?1)(r + 1)}, then every n-connected graph satisfies P(n + r,n).     

On spanning connected graphs

A k-containerC(u,v) of G between u and v is a set of k internally disjoint paths between u and v. A k-container C(u,v) of G is a k^*-container if the set of the vertices of all the paths in C(u,v) contains all the vertices of G. A graph G is k^*-connected if there exists a k^*-container between any two distinct vertices. Therefore, a graph is 1^*-connected (respectively, 2^*-connected) if and only if it is hamiltonian connected (respectively, hamiltonian). In this paper, a classical theorem of Ore, providing sufficient conditional for a graph to be hamiltonian (respectively, hamiltonian connected), is generalized to k^*-connected graphs.     

On k -diameter of k -connected graphs

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).     

The Erdős–Pósa Property for Odd Cycles in Graphs of Large Connectivity

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     

Degree Bounded Spanning Trees

In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set ${S \subseteq V(G)}In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set S í V(G){S \subseteq V(G)} of cardinality n(k−1) + c + 2, there exists a vertex set X í S{X \subseteq S} of cardinality k such that the degree sum of vertices in X is at least |V(G)| − c −1. Then G has a spanning tree T with maximum degree at most k+éc/nù{k+\lceil c/n\rceil} and ?_{v ? V(T)}max{d_T(v)-k,0} ￡ c{\sum_{v\in V(T)}\max\{d_T(v)-k,0\}\leq c} .     

Structures and Chromaticity of Extremal 3-Colourable Sparse Graphs

 Assume that G is a 3-colourable connected graph with e(G) = 2v(G) −k, where k≥ 4. It has been shown that s ₃(G) ≥ 2 ^{k −3}, where s _r (G) = P(G,r)/r! for any positive integer r and P(G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s ₃(G) < 2 ^{k −2}, then G contains at most v(G) −k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle C _k by a 2-tree. By using this result, we settle the problem of determining if W(n, s) is χ-unique, where W(n, s) is the graph obtained from the wheel W _n by deleting all but s consecutive spokes. Received: January 29, 1999 Final version received: April 8, 2000     

Bonds Intersecting Cycles In A Graph

Let G be a k-connected graph G having circumference c ≥ 2k. It is shown that for k ≥ 2, then there is a bond B which intersects every cycle of length c-k + 2 or greater.     

Characterization of polyanalytic functions by meromorphic extensions from chains of circles

Let C _t = {z ∈ ℂ: |z − c(t)| = r(t), t ∈ (0, 1)} be a C ¹-family of circles in the plane such that lim _t→0+ C _t = {a}, lim _t→1− C _t = {b}, a ≠ b, and |c′(t)|² + |r′(t)|² ≠ 0. The discriminant set S of the family is defined as the closure of the set {c(t) + r(t)w(t), t ∈ [0, 1]}, where w = w(t) is the root of the quadratic equation ̅c′(t)w ² + 2r′(t)w + c′(t) = 0 with |w| < 1, if such a root exists.     

The milnor-moore theorem in tame homotopy theory

LetX be a 1-connected space with Moore loop space ΩX. By a well-known theorem of J. W. Milnor and J. C. Moore [7] the Hurewicz homomorphism induces an isomorphism of Hopf algebrasU(π_*(ΩX) ⊗Q)→H _*(ΩX;Q). HereU(−) denotes the universal enveloping algebra and the Lie bracket on π_*(ΩX) ⊗Q is given by the Samelson product. Assume now thatX is the geometric realization of anr-reduced simplicial set,r≥3. LetL _X be a differential graded free Lie algebra over ℤ describing the tame homotopy type ofX according to the theory of [4]. Then the main result of the present paper is the construction of a sequence of morphisms of differential graded algebras betwenU(L _X ) and the algebraC U _*(ΩX)z of normalized cubical chains on ΩX such that the induced morphisms on homology with coefficientsR _k are isomorphismsH _r-1+l (U(L _x );R _k ) ≅H _r-1+l C U _*(ΩX);R _k ) forl≤k; hereR ₀⊆R ₁⊆… is a tame ring system, i. e.R _k )⊑Q and each primep with 2p−3≤k is invertible inR _k . However, it is no longer true that the Pontrjagin algebraH _≤r−1+k (ΩX; R _k ) of ΩX in degrees ≤r−1+k is determined by π_*(ΩX) or by a cofibrant (-fibrant) modelM of π_*(ΩX) as will be shown by an example. But there is a filtration onH _≤r−1+k (ΩX; R _k ) such that the associated graded algebra is isomorphic toH _≤r−1+k (U(M); R _k ).This will be proved by using a filtered Lie algebra model ofX constructed from a bigraded model of π_*(ΩX). Supported by a CNRS grant and PROCOPE Supported by PROCOPE     

Contractible edges in triangle-free graphs

An edge of a graph is calledk-contractible if the contraction of the edge results in ak-connected graph. Thomassen [5] proved that everyk-connected graph of girth at least four has ak-contractible edge. In this paper, we study the distribution ofk-contractible edges in triangle-free graphs and show the following: Whenk≧2, everyk-connected graph of girth at least four and ordern≧3k, hasn+(3/2)k ²-3k or morek-contractible edges.     

Bounds on the number of cycles of length three in a planar graph

LetG be ap-vertex planar graph having a representation in the plane with nontriangular facesF ₁,F ₂, …,F _r. Letf ₁,f ₂, …,f _r denote the lengths of the cycles bounding the facesF ₁,F ₂, …,F _r respectively. LetC ₃(G) be the number of cycles of length three inG. We give bounds onC ₃(G) in terms ofp,f ₁,f ₂, …,f _r. WhenG is 3-connected these bounds are bounds for the number of triangles in a polyhedron. We also show that all possible values ofC ₃(G) between the maximum and minimum value are actually achieved. This research was supported in part by the U.S.A.F. Office of Scientific Research, Systems Command, under Grant AFOSR-76-3017 and the National Science Foundation under Grant ENG79-09724.     

Highly parity linked graphs

A graph G is k-linked if G has at least 2k vertices, and for any 2k vertices x ₁,x ₂, …, x _k ,y ₁,y ₂, …, y _k , G contains k pairwise disjoint paths P ₁, …, P _k such that P _i joins x _i and y _i for i = 1,2, …, k. We say that G is parity-k-linked if G is k-linked and, in addition, the paths P ₁, …, P _k can be chosen such that the parities of their length are prescribed. Thomassen [22] was the first to prove the existence of a function f(k) such that every f(k)-connected graph is parity-k-linked if the deletion of any 4k-3 vertices leaves a nonbipartite graph. In this paper, we will show that the above statement is still valid for 50k-connected graphs. This is the first result that connectivity which is a linear function of k guarantees the Erdős-Pósa type result for parity-k-linked graphs. Research partly supported by the Japan Society for the Promotion of Science for Young Scientists, by Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research and by Inoue Research Award for Young Scientists.     

Weakly Cycle Complementary 3-Partite Tournaments

The vertex set of a digraph D is denoted by V(D). A c-partite tournament is an orientation of a complete c-partite graph. Let V ₁, V ₂, . . . ,V _c be the partite sets of D. If there exist two vertex disjoint cycles C and C′ in D such that V_i?(V(C)èV(C￠)) 1 ?{V_{\mathrm{i}}\cap(V(C)\cup V(C'))\neq\emptyset} for all i = 1, 2, . . . , c, then D is weakly cycle complementary. In 2008, Volkmann and Winzen gave the above definition of weakly complementary cycles and proved that all 3-connected c-partite tournaments with c ≥ 3 are weakly cycle complementary. In this paper, we characterize multipartite tournaments are weakly cycle complementary. Especially, we show that all 2-connected 3-partite tournaments that are weakly cycle complementary, unless D is isomorphic to D _3,2, D _3,2,2 or D _3,3,1.     

On vertex-coloring edge-weighting of graphs

A k-edge-weighting w of a graph G is an assignment of an integer weight, w(e) ∈ {1,…,k}, to each edge e. An edge-weighting naturally induces a vertex coloring c by defining c(u) = Σ _e∋u w(e) for every u ∈ V (G). A k-edge-weighting of a graph G is vertex-coloring if the induced coloring c is proper, i.e., c(u) ≠ c(v) for any edge uv ∈ E(G). When k ≡ 2 (mod 4) and k ⩾ 6, we prove that if G is k-colorable and 2-connected, δ(G) ⩾ k − 1, then G admits a vertex-coloring k-edge-weighting. We also obtain several sufficient conditions for graphs to be vertex-coloring k-edge-weighting.      

Closed Separator Sets

A smallest separator in a finite, simple, undirected graph G is a set S ⊆ V (G) such that G–S is disconnected and |S|=κ(G), where κ(G) denotes the connectivity of G. A set S of smallest separators in G is defined to be closed if for every pair S,T ∈ S, every component C of G–S, and every component S of G–T intersecting C either X(C,D) := (V (C) ∩ T) ∪ (T ∩ S) ∪ (S ∩ V (D)) is in S or |X(C,D)| > κ(G). This leads, canonically, to a closure system on the (closed) set of all smallest separators of G. A graph H with is defined to be S-augmenting if no member of S is a smallest separator in G ∪ H:=(V (G) ∪ V (H), E(G) ∪ E(H)). It is proved that if S is closed then every minimally S-augmenting graph is a forest, which generalizes a result of Jordán. Several applications are included, among them a generalization of a Theorem of Mader on disjoint fragments in critically k-connected graphs, a Theorem of Su on highly critically k-connected graphs, and an affirmative answer to a conjecture of Su on disjoint fragments in contraction critically k-connected graphs of maximal minimum degree.