Existence of proportional graphs

The notion of p-proportional graphs comes from the study of subgraph counts in random graphs, where the p-proportional graphs occur as exceptional cases in a central limit theorem. In this paper we show that p-proportional graphs exist for all rational p, 0 < p < 1, and thereby proving a conjecture from [3]. © 1993 John Wiley & Sons, Inc.     

Existence of graphs with prescribed mean distance

It is shown that for each rational number t ≥ 1 there exist infinitely many graphs with mean distance equal to t. For a graph G, define the mean distance μ(G) by . In an earlier issue of this journal, J. Plesník [3, Theorem 9] showed that, given real numbers t ≥ 1 and ? > 0, there exists a graph G with |μ(G)?t| < ?. Furthermore, he asked [3, p. 19]: Given a rational number t ≥ 1, does there exist a graph G with μ(G) = t? We answer this question in the affirmative by proving:     

Existence of rainbow matchings in properly edge-colored graphs

Let G be a properly edge-colored graph. A rainbow matching of G is a matching in which no two edges have the same color. Let δ denote the minimum degree of G. We show that if |V(G)| > (δ ² + 14δ + 1)/4, then G has a rainbow matching of size δ, which answers a question asked by G. Wang [Electron. J. Combin., 2011, 18: #N162] affirmatively. In addition, we prove that if G is a properly colored bipartite graph with bipartition (X, Y) and max{|X|, |Y|} > (δ ² + 4δ − 4)/4, then G has a rainbow matching of size δ.     

Existence of prescribed mean curvature graphs in hyperbolic space

In this paper we are concerned with questions of existence and uniqueness of graph-like prescribed mean curvature hypersurfaces in hyperbolic space ?ⁿ⁺¹. In the half-space setting, we will study radial graphs over the totally geodesic hypersurface . We prove the following existence result: Let be a bounded domain of class and let . If everywhere on , where denotes the hyperbolic mean curvature of the cylinder over , then for every there is a unique graph over with mean curvature attaining the boundary values on . Further we show the existence of smooth boundary data such that no solution exists in case of for some under the assumption that has a sign.     

Existence of constant mean curvature graphs in hyperbolic space

We give an existence result for constant mean curvature graphs in hyperbolic space . Let be a compact domain of a horosphere in whose boundary is mean convex, that is, its mean curvature (as a submanifold of the horosphere) is positive with respect to the inner orientation. If H is a number such that , then there exists a graph over with constant mean curvature H and boundary . Umbilical examples, when is a sphere, show that our hypothesis on H is the best possible. Received July 18, 1997 / Accepted April 24, 1998     

Finding thet-join structure of graphs

t-joins are generalizations of postman tours, matchings, and paths;t-cuts contain planar multicommodity flows as a special case. In this paper we present a polynomial time combinatorial algorithm that determines a minimumt-join and a maximum packing oft-cuts and that ends up with a Gallai-Edmonds type structural decompostion of (G, t) pairs, independent of the running of the algorithm. It only uses simple combinatorial steps such as the symmetric difference of two sets of edges and does not use any shrinking operations.     

On the structure of unbreakable graphs

A nonempty set C of vertices is a star-cutset in a graph G if G – C is disconnected and some vertex in C is adjacent to all the remaining vertices in C. Va?ek Chvátal proposed to call a graph G unbreakable if neither G nor its complement G has a star-cutset. A path with four vertices and three edges will be termed a P₄. An edge uv of a graph G is called a wing, if for some vertices x, y, {u,v,x,y} induces a P₄ in G. We define recursively the coercion class C_uv of a wing uv as follows:

• 1 uv ∈ C_uv, and
• 1 if xy ∈ C_uv and xy, x'y' are wings of a same P₄ in G, then x'y' ∈ C_uv.

The purpose of this work is to present new results concerning unbreakable graphs, using the notion of coercion class. These results include a theorem asserting that every unbreakable graph contains at most two distinct coercion classes and a structure theorem for those unbreakable graphs that contain precisely two coercion classes. These results generalize several previously known results about unbreakable graphs.     

Existence of graphs with a given set of r-neighborhoods

The problem of whether there exists a graph satisfying a particular set of local constraints can often be reduced to questions of the following sort: given a finite collection Φ of graphs, is there a graph G such that the set of r-neighborhoods of the vertices of G is precisely Φ? It is shown that, although such a question is in general recursively unsolvable, it becomes solvable when a bound on cycle length is imposed on G, even when G is required to be connected or arbitrarily large. This result is used to demonstrate the solvability of a problem from hypergraph theory involving degree sets of k-trees.     

On the structure of linear graphs

Denote byG(n; m) a graph ofn vertices andm edges. We prove that everyG(n; [n ²/4]+1) contains a circuit ofl edges for every 3 ≦l<c ₂ n, also that everyG(n; [n ²/4]+1) contains ak _e(u _n, u_n) withu _n=[c ₁ logn] (for the definition ofk _e(u _n, u_n) see the introduction). Finally fort>t ₀ everyG(n; [tn ^3/2]) contains a circuit of 2l edges for 2≦l<c ₃ t ². This work was done while the author received support from the National Science Foundation, N.S.F. G.88.     

Connectivity and tree structure in finite graphs

Considering systems of separations in a graph that separate every pair of a given set of vertex sets that are themselves not separated by these separations, we determine conditionsunder which such a separation system contains a nested subsystem that still separates those sets and is invariant under the automorphisms of the graph. As an application, we show that the k-blocks — the maximal vertex sets that cannot be separated by at most k vertices — of a graph G live in distinct parts of a suitable treedecomposition of G of adhesion at most k, whose decomposition tree is invariant under the automorphisms of G. This extends recent work of Dunwoody and Krön and, like theirs, generalizes a similar theorem of Tutte for k=2. Under mild additional assumptions, which are necessary, our decompositions can be combined into one overall tree-decomposition that distinguishes, for all k simultaneously, all the k-blocks of a finite graph.     

Quasi-isometries between non-locally-finite graphs and structure trees

We prove several criteria for quasi-isometry between non-locally-finite graphs and their structure trees. Results ofMöller in [11] for locally finite and transitive graphs are generalized. We also give a criterion in terms of correspondence between the ends of the graph and the ends of the structure tree.