Packing paths in planar graphs

A generalization of P. Seymour's theorem on planar integral 2-commodity flows is given when the underlying graphG together with the demand graphH (a graph having edges that connect the corresponding terminal pairs) form a planar graph and the demand edges are on two faces ofG.     

More orthogonal double covers of complete graphs by Hamiltonian paths

An orthogonal double cover (ODC) of the complete graph K_n by a graph G is a collection G of n spanning subgraphs of K_n, all isomorphic to G, such that any two members of G share exactly one edge and every edge of K_n is contained in exactly two members of G. In the 1980s Hering posed the problem to decide the existence of an ODC for the case that G is an almost-Hamiltonian cycle, i.e. a cycle of length n-1. It is known that the existence of an ODC of K_n by a Hamiltonian path implies the existence of ODCs of K_4n and of K_16n, respectively, by almost-Hamiltonian cycles. Horton and Nonay introduced two-colorable ODCs and showed: If there are an ODC of K_n by a Hamiltonian path for some n?3 and a two-colorable ODC of K_q by a Hamiltonian path for some prime power q?5, then there is an ODC of K_qn by a Hamiltonian path. In [U. Leck, A class of 2-colorable orthogonal double covers of complete graphs by hamiltonian paths, Graphs Combin. 18 (2002) 155-167], two-colorable ODCs of K_n and K_2n, respectively, by Hamiltonian paths were constructed for all odd square numbers n?9. Here we continue this work and construct cyclic two-colorable ODCs of K_n and K_2n, respectively, by Hamiltonian paths for all n of the form n=4k²+1 or n=(k²+1)/2 for some integer k.     

A note on strong embeddings of maximal planar graphs on non-orientable sufraces

Abstract. In this paper, it is shown that for every maximal planar graph     

A nine point theorem for 3-connected graphs

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

Edge-reconstruction of minimally 3-connected planar graphs

Summary It is shown that minimally 3-connected planar graphs are edge-reconstructible.     

The gallai-younger conjecture for planar graphs

Younger conjectured that for everyk there is ag(k) such that any digraphG withoutk vertex disjoint cycles contains a setX of at mostg(k) vertices such thatG–X has no directed cycles. Gallai had previously conjectured this result fork=1. We prove this conjecture for planar digraphs. Specifically, we show that ifG is a planar digraph withoutk vertex disjoint directed cycles, thenG contains a set of at mostO(klog(k)log(log(k))) vertices whose removal leaves an acyclic digraph. The work also suggests a conjecture concerning an extension of Vizing's Theorem for planar graphs.     

Cycles through ten vertices in 3-connected cubic graphs

It is known that there exists a cycle through any nine vertices of a 3-connected cubic graphG. Here we show that if an edge is removed from such a graph, then there is still a cycle through any five vertices. Furthermore, we characterise the circumstances in which there fails to be a cycle through six. As corollaries we are able to prove that a 3-connected cubic graph has a cycle through any specified five vertices and one edge, and to classify the conditions under which it has a cycle through four chosen vertices and two edges. We are able to use the five and six vertex results to show that a 3-connected cubic graph has a cycle which passes through any ten given vertices if and only if the graph is not contractible to the Petersen graph in such a way that the ten vertices each map to a distinct vertex of the Petersen graph.     

Small covers over prisms

In this paper we calculate the number of equivariant diffeomorphism classes of small covers over a prism.     

Pairs of edge disjoint Hamiltonian circuits in 5-connected planar graphs

Summary A variety of examples of 4-connected 4-regular graphs with no pair of disjoint Hamiltonian circuits were constructed in response to Nash-Williams conjecture that every 4-connected 4-regular graph is Hamiltonian and also admits a pair of edge-disjoint Hamiltonian circuits. Nash-Williams's problem is especially interesting for planar graphs since 4-connected planar graphs are Hamiltonian. Examples of 4-connected 4-regular planar graphs in which every pair of Hamiltonian circuits have edges in common are included in the above mentioned examples.B. Grünbaum asked whether 5-connected planar graphs always admit a pair of disjoint Hamiltonian circuits. In this paper we introduce a technique that enables us to construct infinitely many examples of 5-connected planar graphs, 5-regular and non regular, in which every pair of Hamiltonian circuits have edges in common.     

Regular odd rings and non-planar graphs

In a previous paper we have announced that a graph is non-planar if and only if it contains a maximal, strict, compact, odd ring. Little has conjectured that the compactness condition may be removed. Chernyak has now published a proof of this conjecture. However, it is difficult to test a ring for maximality. In this paper we show that for odd rings of size five or greater, the condition of maximality may be replaced by a new one called regularity. Regularity is an easier condition to diagnose than is maximality.     

On translations of double rays in graphs

Let be an infinite graph, let be a double ray in , and letd andd denote the distance functions in and in , respectively. One calls anaxis ifd(x,y)=d (x,y) and aquasi-axis if lim infd(x,y)/d (x,y)>0 asx, y range over the vertex set of andd (x,y). The present paper brings together in greater generality results of R. Halin concerning invariance of double rays under the action of translations (i.e., graph automorphisms all of whose vertex-orbits are infinite) and results of M. E. Watkins concerning existence of axes in locally finite graphs. It is shown that if is a translation whose directionD() is a thin end, then there exists an axis inD() andD(^–1) invariant under ^r for somer not exceeding the maximum number of disjoint rays inD().The thinness ofD() is necessary. Further results give necessary conditions and sufficient conditions for a translation to leave invariant a quasi-axis.     

Venn diagrams and planar graphs

Using graph theory, we develop procedures for the construction of Venn diagrams. This allows us to determine the number of Venn diagrams on three sets, and to address further questions on enumeration of Venn diagrams. In so doing, we obtain examples of Venn diagrams which yield answers to several problems and conjectures of Grünbaum.Supported in part by a Purdue Research Foundation Summer Faculty Grant.     

On the sum of the reciprocals of cycle lengths in sparse graphs

For a graphG let ℒ(G)=Σ{1/k contains a cycle of lengthk}. Erdős and Hajnal [1] introduced the real functionf(α)=inf {ℒ (G)|E(G)|/|V(G)|≧α} and suggested to study its properties. Obviouslyf(1)=0. We provef (k+1/k)≧(300k logk)⁻¹ for all sufficiently largek, showing that sparse graphs of large girth must contain many cycles of different lengths.     

4-regular claw-free IM-extendable graphs

A graph G is induced matching extendable (shortly, IM-extendable), if every induced matching of G is included in a perfect matching of G. A graph G is claw-free, if G does not contain any induced subgraph isomorphic to K_1,3. The kth power of a graph G, denoted by G^k, is the graph with vertex set V(G) in which two vertices are adjacent if and only if the distance between them in G is at most k. In this paper, the 4-regular claw-free IM-extendable graphs are characterized. It is shown that the only 4-regular claw-free connected IM-extendable graphs are , and T_r, r?2, where T_r is the graph with 4r vertices u_i,v_i,x_i,y_i, 1?i?r, such that for each i with 1?i?r, {u_i,v_i,x_i,y_i} is a clique of T_r and . We also show that a 4-regular strongly IM-extendable graph must be claw-free. As a consequence, the only 4-regular strongly IM-extendable graphs are K₄×K₂, and .     

Global cycle properties in graphs with large minimum clustering coefficient

Let 𝒫 be a graph property. A graph G is said to be locally 𝒫 (closed locally 𝒫) if the subgraph induced by the open neighbourhood (closed neighbourhood, respectively) of every vertex in G has property 𝒫. The clustering coefficient of a vertex is the proportion of pairs of its neighbours that are themselves neighbours. The minimum clustering coefficient of G is the smallest clustering coefficient among all vertices of G. Let H be a subgraph of a graph G and let S ? V (H). We say that H is a strongly induced subgraph of G with attachment set S, if H is an induced subgraph of G and the vertices of V (H) ? S are not incident with edges that are not in H. A graph G is fully cycle extendable if every vertex of G lies in a triangle and for every nonhamiltonian cycle C of G, there is a cycle of length |V (C)|?+?1 that contains the vertices of C. A complete characterization, of those locally connected graphs with minimum clustering coefficient 1/2 and maximum degree at most 6 that are fully cycle extendable, is given in terms of forbidden strongly induced subgraphs (with specified attachment sets). Moreover, it is shown that all locally connected graphs with Δ?≤?6 and sufficiently large minimum clustering coefficient are weakly pancylic, thereby proving Ryj´ǎcek’s conjecture for this class of graphs.     

Circle boundaries of planar graphs

Letg be an infinite, connected, planar graph with bounded vertex degree, which obeys a strong isoperimetric inequality and which can be embedded in the plane so that each cycle surrounds only finitely many vertices. We investigate a certain class of compactifications ofg; one of which has boundary homemorophic to a circle. We shall show that ifg is a tree or, more generally, ifg is hyperbolic, then this circle boundary supports an integral representation of any given bounded harmonic function. We further show that in the specific case of a triangulation of the plane, the graph is hyperbolic and therefore the Martin boundary is a circle.     

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

Minimum cycle bases of graphs on surfaces

In this paper we study the cycle base structures of embedded graphs on surfaces. We first give a sufficient and necessary condition for a set of facial cycles to be contained in a minimum cycle base (or MCB in short) and then set up a 1-1 correspondence between the set of MCBs and the set of collections of nonseparating cycles which are in general positions on surfaces and are of shortest total length. This provides a way to enumerate MCBs in a graph via nonseparating cycles. In particular, some known results such as P.F. Stadler's work on Halin graphs [Minimum cycle bases of Halin graphs, J. Graph Theory 43 (2003) 150-155] and Leydold and Stadler's results on outer-planar graphs [Minimum cycle bases of outerplanar graphs, Electronic J. Combin. 5(16) (1998) 14] are concluded. As applications, the number of MCBs in some types of graphs embedded in lower surfaces (with arbitrarily high genera) is found. Finally, we present an interpolation theorem for the number of one-sided cycles contained in MCB of an embedded graph.