Density theorems for bipartite graphs and related Ramsey-type results

In this paper, we present several density-type theorems which show how to find a copy of a sparse bipartite graph in a graph of positive density. Our results imply several new bounds for classical problems in graph Ramsey theory and improve and generalize earlier results of various researchers. The proofs combine probabilistic arguments with some combinatorial ideas. In addition, these techniques can be used to study properties of graphs with a forbidden induced subgraph, edge intersection patterns in topological graphs, and to obtain several other Ramsey-type statements. Research supported by an NSF Graduate Research Fellowship and a Princeton Centennial Fellowship. Research supported in part by NSF CAREER award DMS-0812005 and by USA-Israeli BSF grant.     

Arbitrarily traceable graphs and digraphs

The work in this paper extends and generalizes earlier work by Ore on arbitrarily traceable Euler graphs, by Harary on arbitrarily traceable digraphs, by Chartrand and White on randomly n-traversable graphs, and by Chartrand and Lick on randomly Eulerian digraphs. Arbitrarily traceable graphs of mixed type are defined and characterized in terms of a class of forbidden graphs. Arbitrarily traceable digraphs of mixed type are also defined and a simply applied characterization is given for them.     

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 uniqueness theorem for Delaunay graphs

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

可迹图的谱充分条件

设G是一个简单图,A(G),Q(G)以及Q(G)分别为G的邻接矩阵,无符号拉普拉斯矩阵以及距离无符号拉普拉斯矩阵,其最大特征值分别称为G的谱半径,无符号拉普拉斯谱半径以及距离无符号拉普拉斯谱半径.如果图G中有一条包含G中所有顶点的路,则称这条路为哈密顿路;如果图G含有哈密顿路,则称G为可迹图;如果图G含有从任意一点出发的哈密顿路,则称G从任意一点出发都是可迹的.主要研究利用图G的谱半径,无符号拉普拉斯谱半径,以及距离无符号拉普拉斯谱半径,分别给出图G从任意一点出发都是可迹的充分条件.     

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.     

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 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 separator theorem for graphs of bounded genus

Many divide-and-conquer algorithms on graphs are based on finding a small set of vertices or edges whose removal divides the graph roughly in half. Most graphs do not have the necessary small separators, but some useful classes do. One such class is planar graphs: If an n-vertex graph can be drawn on the plane, then it can be bisected by removal of O(sqrt(n)) vertices (R. J. Lipton and R. E. Tarjan, SIAM J. Appl. Math.36 (1979), 177–189). The main result of the paper is that if a graph can be drawn on a surface of genus g, then it can be bisected by removal of O(sqrt(gn)) vertices. This bound is best possible to within a constant factor. An algorithm is given for finding the separator that takes time linear in the number of edges in the graph, given an embedding of the graph in its genus surface. Some extensions and applications of these results are discussed.     

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.     

A nine point theorem for 3-connected graphs

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

Bandwidth theorem for random graphs

A graph G is said to have bandwidth at most b, if there exists a labeling of the vertices by 1,2,…,n, so that |i−j|?b whenever {i,j} is an edge of G. Recently, Böttcher, Schacht, and Taraz verified a conjecture of Bollobás and Komlós which says that for every positive r, Δ, γ, there exists β such that if H is an n-vertex r-chromatic graph with maximum degree at most Δ which has bandwidth at most βn, then any graph G on n vertices with minimum degree at least (1−1/r+γ)n contains a copy of H for large enough n. In this paper, we extend this theorem to dense random graphs. For bipartite H, this answers an open question of Böttcher, Kohayakawa, and Taraz. It appears that for non-bipartite H the direct extension is not possible, and one needs in addition that some vertices of H have independent neighborhoods. We also obtain an asymptotically tight bound for the maximum number of vertex disjoint copies of a fixed r-chromatic graph H₀ which one can find in a spanning subgraph of G(n,p) with minimum degree (1−1/r+γ)np.