The dominating set problem is fixed parameter tractable for graphs of bounded genus

We describe an algorithm for the dominating set problem with time complexity O((4g+40)^kn²) for graphs of bounded genus g1, where k is the size of the set. It has previously been shown that this problem is fixed parameter tractable for planar graphs. We give a simpler proof for the previous O(8^kn²) result for planar graphs. Our method is a refinement of the earlier techniques.     

A uniqueness theorem for Delaunay graphs

We establish a necessary and sufficient condition for the congruence of two isomorphic Delaunay graphs.     

A panconnectivity theorem for bipartite graphs

Let $G$ be a simple $m\times n$ bipartite graph with $m\ge n$. We prove that if the minimum degree of $G$ satisfies $\delta \left(G\right)\ge m∕2+1$, then $G$ is bipanconnected: for every pair of vertices $x,y$, and for every appropriate integer $2\le ?\le 2n$, there is an $x,y$-path of length $?$ in $G$.     

A Ramsey-type theorem for traceable graphs

A graph G is traceable if there is a path passing through all the vertices of G. It is proved that every infinite traceable graph either contains arbitrarily large finite chordless paths, or contains a subgraph isomorphic to graph A, illustrated in the text. A corollary is that every finitely generated infinite lattice of length 3 contains arbitrarily large finite fences. It is also proved that every infinite traceable graph containing no chordless four-point path contains a subgraph isomorphic to K_ω,ω. The versions of these results for finite graphs are discussed.     

A dirac-type theorem for squares of graphs

We prove that if G is a connected graph with p vertices and minimum degree greater than max (p/4 ? 1,3) then G² is pancyclic. The result is best possible of its kind.     

A fixed point theorem for exponentially bounded groups

A fixed point property for linear actions of locally compact groups is presented. It is shown, in particular, that if G is either a finitely generated, discrete solvable group or a connected group then G has this fixed point property if, and only if, G is exponentially bounded.     

A min-max theorem for plane bipartite graphs

We consider a partitioning problem, defined for bipartite and 2-connected plane graphs, where each node should be covered exactly once by either an edge or by a cycle surrounding a face. The objective is to maximize the number of face boundaries in the partition. This problem arises in mathematical chemistry in the computation of the Clar number of hexagonal systems. In this paper we establish that a certain minimum weight covering problem of faces by cuts is a strong dual of the partitioning problem. Our proof relies on network flow and linear programming duality arguments, and settles a conjecture formulated by Hansen and Zheng in the context of hexagonal systems [P. Hansen, M. Zheng, Upper Bounds for the Clar Number of Benzenoid Hydrocarbons, Journal of the Chemical Society, Faraday Transactions 88 (1992) 1621-1625].     

A Bernstein theorem for special Lagrangian graphs

We obtain a Bernstein theorem for special Lagrangian graphs in for arbitrary n only assuming bounded slope but no quantitative restriction. Received: 18 January 2001 / Accepted: 7 June 2001 / Published online: 12 October 2001 The second-named author is grateful to the Max Planck Institute for Mathematics in the Sciences in Leipzig for its hospitality and support and also 973 project in China.     

A local characterization of bounded clique-width for line graphs

It is shown that a line graph G has clique-width at most 8k+4 and NLC-width at most 4k+3, if G contains a vertex whose non-neighbours induce a subgraph of clique-width k or NLC-width k in G, respectively. This relation implies that co-gem-free line graphs have clique-width at most 14 and NLC-width at most 7.It is also shown that in a line graph the neighbours of a vertex induce a subgraph of clique-width at most 4 and NLC-width at most 2.     

A Helly theorem for convexity in graphs

It is shown that for chordless path convexity in any graph, the Helly number equals the size of a maximum clique.     

Sparse partition universal graphs for graphs of bounded degree

In 1983, Chvátal, Trotter and the two senior authors proved that for any Δ there exists a constant B such that, for any n, any 2-colouring of the edges of the complete graph KN with N?Bn vertices yields a monochromatic copy of any graph H that has n vertices and maximum degree Δ. We prove that the complete graph may be replaced by a sparser graph G that has N vertices and edges, with N=⌈B^′n⌉ for some constant B^′ that depends only on Δ. Consequently, the so-called size-Ramsey number of any H with n vertices and maximum degree Δ is . Our approach is based on random graphs; in fact, we show that the classical Erd?s–Rényi random graph with the numerical parameters above satisfies a stronger partition property with high probability, namely, that any 2-colouring of its edges contains a monochromatic universal graph for the class of graphs on n vertices and maximum degree Δ.The main tool in our proof is the regularity method, adapted to a suitable sparse setting. The novel ingredient developed here is an embedding strategy that allows one to embed bounded degree graphs of linear order in certain pseudorandom graphs. Crucial to our proof is the fact that regularity is typically inherited at a scale that is much finer than the scale at which it is assumed.     

A nine point theorem for 3-connected graphs

We prove that a 3-connected cubic graph contains a cycle through any nine points.     

A sharp Bernstein-type theorem for entire minimal graphs

We consider entire solutions u to the minimal surface equation in \(\mathbb {R}^N\), with \( N\ge 8,\) and we prove the following sharp result: if \(N-7\) partial derivatives \( \frac{\partial u }{\partial {x_j}}\) are bounded on one side (not necessarily the same), then u is necessarily an affine function.