Coarser connected metrizable topologies

We show that every metric space, X, with w(X)?c has a coarser connected metrizable topology.     

An example of a nonarcwise connected rim-countable locally connected continuum

An example of a rim-countable, locally connected, but nonarcwise connected continuum is constructed, which is important for the classification of locally connected continua. The point of interest in this result is that there are no metrizable locally connected continua with the above properties. Translated fromMatematicheskie Zametki, Vol. 65, No. 5, pp. 659–666, May, 1999.     

Long paths through four vertices in a 2‐connected graph

Let G be a 2‐connected graph, let u and v be distinct vertices in V(G), and let X be a set of at most four vertices lying on a common (u, v)‐path in G. If deg(x) ≥ d for all x ∈ V(G) \ {u, v}, then there is a (u, v)‐path P in G with X ⊂ V(P) and |E(P)| ≥ d. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 55–65, 2000     

Relative length of longest paths and cycles in 3‐connected graphs

For a graph G, let p(G) denote the order of a longest path in G and c(G) the order of a longest cycle in G, respectively. We show that if G is a 3‐connected graph of order n such that for every independent set {x₁, x₂, x₃, x₄}, then G satisfies c(G) ≥ p(G) ? 1. Using this result, we give several lower bounds to the circumference of a 3‐connected graph. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 137–156, 2001     

Weaker connected and weaker nowhere locally compact topologies for metrizable and similar spaces

We prove that any metrizable non-compact space has a weaker metrizable nowhere locally compact topology. As a consequence, any metrizable non-compact space has a weaker Hausdorff connected topology. The same is established for any Hausdorff space X with a σ-locally finite base whose weight w(X) is a successor cardinal.     

Subdivisions of large complete bipartite graphs and long induced paths in k‐connected graphs

It is proved that for every positive integers k, r and s there exists an integer n = n(k,r,s) such that every k‐connected graph of order at least n contains either an induced path of length s or a subdivision of the complete bipartite graph K_k,r. © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 270–274, 2004     

A limit theorem for randomly stopped independent increment processes on separable metrizable groups

In the spirit of the classical random central limit theorem a general limit theorem for random stopping in the scheme of infinitesimal triangular arrays on a separable metrizable group is presented. The approach incorporates and generalizes earlier results for normalized sequences of independent random variables on both separable Banach spaces and simply connected nilpotent Lie groups originated by Siegel and Hazod, respectively. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On relative length of longest paths and cycles

For a graph G, p(G) and c(G) denote the order of a longest path and a longest cycle of G, respectively. In this paper, we prove that if G is a 3 ‐connected graph of order n such that the minimum degree sum of four independent vertices is at least n+ 6, then p(G)?c(G)?2. By considering our result and the results in [J Graph Theory 20 (1995), 213–225; Amer Math Monthly 67 (1950), 55], we propose a conjecture which is a generalization of Bondy's conjecture. Furthermore, using our result, for a graph satisfying the above conditions, we obtain a new lower bound of the circumference and establish Thomassen's conjecture. © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 279–291, 2009     

Locally connected hereditarily Lindelöf compacta

It is consistent with MA+¬CH that there is a locally connected hereditarily Lindelöf compact space which is not metrizable.     

Halin图中的Hamilton路径

本文证明了所有的Ｈａｌｉｎ图都是Ｈａｍｉｌｔｏｎ连通的，并给出反例，说明Ｈａｌｉｎ图中存在两条独立边不包含在任何Ｈａｍｉｌｔｏｎ圈中。     

Neither first countable nor Cech-complete spaces are maximal Tychonoff connected

A connected Tychonoff space is called maximal Tychonoff connected if there is no strictly finer Tychonoff connected topology on . We show that if is a connected Tychonoff space and locally separable spaces, locally \v{C}ech-complete spaces, first countable spaces, then is not maximal Tychonoff connected. This result is new even in the cases where is compact or metrizable.

     

Connectivity keeping paths in k‐connected graphs

A result of G. Chartrand, A. Kaugars, and D. R. Lick [Proc Amer Math Soc 32 (1972), 63–68] says that every finite, k‐connected graph G of minimum degree at least ?3k/2? contains a vertex x such that G?x is still k‐connected. We generalize this result by proving that every finite, k‐connected graph G of minimum degree at least ?3k/2?+m?1 for a positive integer m contains a path P of length m?1 such that G?V(P) is still k‐connected. This has been conjectured in a weaker form by S. Fujita and K. Kawarabayashi [J Combin Theory Ser B 98 (2008), 805–811]. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 61–69, 2010.     

On (co)homology locally connected spaces

We prove that there exists a cohomology locally connected compact metrizable space which is not homology locally connected. In the category of compact Hausdorff spaces a similar result was proved earlier by G.E. Bredon.     

Connected Domatic Number in Planar Graphs

A dominating set in a graph G is a connected dominating set of G if it induces a connected subgraph of G. The connected domatic number of G is the maximum number of pairwise disjoint, connected dominating sets in V(G). We establish a sharp lower bound on the number of edges in a connected graph with a given order and given connected domatic number. We also show that a planar graph has connected domatic number at most 4 and give a characterization of planar graphs having connected domatic number 3.     

Infinite paths in planar graphs V, 3‐indivisible graphs

We prove Nash‐Williams' conjecture that every 4‐connected, 3‐indivisible, infinite, planar graph contains a spanning 2‐way infinite path. A graph is said to be 3‐indivisible if the deletion of any finite set of vertices results in at most two infinite components. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 275–312, 2008     

Almost disjoint families of connected sets

We investigate the question which (separable metrizable) spaces have a ‘large’ almost disjoint family of connected (and locally connected) sets. Every compact space of dimension at least 2 as well as all compact spaces containing an ‘uncountable star’ have such a family. Our results show that the situation for 1-dimensional compacta is unclear.     

Triangle-free graphs with no six-vertex induced path

The graphs with no five-vertex induced path are still not understood. But in the triangle-free case, we can do this and one better; we give an explicit construction for all triangle-free graphs with no six-vertex induced path. Here are three examples: the 16-vertex Clebsch graph, the graph obtained from an 8-cycle by making opposite vertices adjacent, and the graph obtained from a complete bipartite graph by subdividing a perfect matching. We show that every connected triangle-free graph with no six-vertex induced path is an induced subgraph of one of these three (modulo some twinning and duplication).     

Paths, trees and matchings under disjunctive constraints

We study the minimum spanning tree problem, the maximum matching problem and the shortest path problem subject to binary disjunctive constraints: A negative disjunctive constraint states that a certain pair of edges cannot be contained simultaneously in a feasible solution. It is convenient to represent these negative disjunctive constraints in terms of a so-called conflict graph whose vertices correspond to the edges of the underlying graph, and whose edges encode the constraints.We prove that the minimum spanning tree problem is strongly NP-hard, even if every connected component of the conflict graph is a path of length two. On the positive side, this problem is polynomially solvable if every connected component is a single edge (that is, a path of length one). The maximum matching problem is NP-hard for conflict graphs where every connected component is a single edge.Furthermore we will also investigate these graph problems under positive disjunctive constraints: In this setting for certain pairs of edges, a feasible solution must contain at least one edge from every pair. We establish a number of complexity results for these variants including APX-hardness for the shortest path problem.     

Hamilton paths and cycles in vertex-transitive graphs of order

It is shown that every connected vertex-transitive graph of order 6p, where p is a prime, contains a Hamilton path. Moreover, it is shown that, except for the truncation of the Petersen graph, every connected vertex-transitive graph of order 6p which is not genuinely imprimitive contains a Hamilton cycle.     

Infinite paths in planar graphs II,structures and ladder nets

A graph is k‐indivisible, where k is a positive integer, if the deletion of any finite set of vertices results in at most k – 1 infinite components. In 1971, Nash‐Williams conjectured that a 4‐connected infinite planar graph contains a spanning 2‐way infinite path if and only if it is 3‐indivisible. In this paper, we prove a structural result for 2‐indivisible infinite planar graphs. This structural result is then used to prove Nash‐Williams conjecture for all 4‐connected 2‐indivisible infinite planar graphs. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 247–266, 2005