The number of contractible edges in 3-connected graphs

An edge of a 3-connected graph is calledcontractible if its contraction results in a 3-connected graph. Ando, Enomoto and Saito proved that every 3-connected graph of order at least five has |G|/2 or more contractible edges. As another lower bound, we prove that every 3-connected graph, except for six graphs, has at least (2|E(G)| + 12)/7 contractible edges. We also determine the extremal graphs. Almost all of these extremal graphsG have more than |G|/2 contractible edges.     

On the number of hamiltonian cycles in a maximal planar graph

We consider the problem of the minimum number of Hamiltonian cycles that could be present in a Hamiltonian maximal planar graph on p vertices. In particular, we construct a p-vertex maximal planar graph containing exactly four Hamiltonian cycles for every p ≥ 12. We also prove that every 4-connected maximal planar graph on p vertices contains at least p/(log₂ p) Hamiltonian cycles.     

Long cycles and spanning subgraphs of locally maximal 1-planar graphs

A graph is 1-planar if it has a drawing in the plane such that each edge is crossed at most once by another edge. Moreover, if this drawing has the additional property that for each crossing of two edges the end vertices of these edges induce a complete subgraph, then the graph is locally maximal 1-planar. For a 3-connected locally maximal 1-planar graph G, we show the existence of a spanning 3-connected planar subgraph and prove that G is Hamiltonian if G has at most three 3-vertex-cuts, and that G is traceable if G has at most four 3-vertex-cuts. Moreover, infinitely many nontraceable 5-connected 1-planar graphs are presented.     

Edge proximity and matching extension in punctured planar triangulations

A matching $M$ in a graph $G$ is said to be extendable if there exists a perfect matching of $G$ containing $M$. In 1989, it was shown that every connected planar graph with at least $8$ vertices has a matching of size three which is not extendable. In contrast, the study of extending certain matchings of size three or more has made progress in the past decade when the given graph is $5$-connected planar triangulation or $5$-connected plane graphs with few non-triangular faces.In this paper, we prove that if $G$ is a $5$-connected plane graph of even order in which at most two faces are not triangular and $M$ is a matching of size four in which the edges lie pairwise distance at least three apart, then $M$ is extendable. A related result concerning perfect matching with proscribed edges is shown as well.     

An Extremal Problem on Contractible Edges in 3-Connected Graphs

An edge e in a 3-connected graph G is contractible if the contraction G/e is still 3-connected. The existence of contractible edges is a very useful induction tool. Let G be a simple 3-connected graph with at least five vertices. Wu [7] proved that G has at most vertices that are not incident to contractible edges. In this paper, we characterize all simple 3-connected graphs with exactly vertices that are not incident to contractible edges. We show that all such graphs can be constructed from either a single vertex or a 3-edge-connected graph (multiple edges are allowed, but loops are not allowed) by a simple graph operation. Research partially supported by an ONR grant under grant number N00014-01-1-0917     

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.     

CYCLE SPACES OF GRAPHS ON THE SPHERE AND THE PROJECTIVE PLANE

Cycle base theory of a graph has been well studied in abstract mathematical field such matroid theory as Whitney and Tutte did and found many applications in pratical uses such as electric circuit theory and structure analysis, etc. In this paper graph embedding theory is used to investigate cycle base structures of a 2-(edge)-connected graph on the sphere and the projective plane and it is shown that short cycles do generate the cycle spaces in the case of ““““small face-embeddings““““. As applications the authors find the exact formulae for the minimum lengthes of cycle bases of some types of graphs and present several known results. Infinite examples shows that the conditions in their main results are best possible and there are many 3-connected planar graphs whose minimum cycle bases can not be determined by the planar formulae but may be located by re-embedding them into the projective plane.     

A Characterization of Graphs with No Cube Minor

In this paper it is shown that any 4-connected graph that does not contain a minor isomorphic to the cube is a minor of the line graph of V_n for some n6 or a minor of one of five graphs. Moreover, there exists a unique 5-connected graph on at least 8 vertices with no cube minor and a unique 4-connected graph with a vertex of degree at least 8 with no cube minor. Further, it is shown that any graph with no cube minor is obtained from 4-connected such graphs by 0-, 1-, and 2-summing, and 3-summing over a specified triangles.     

Longest cycles in 3-connected graphs contain three contractible edges

We show that if G is a 3-connected graph of order at least seven, then every longest path between distinct vertices in G contains at least two contractible edges. An immediate corollary is that longest cycles in such graphs contain at least three contractible edges.     

2-connected coverings of bounded degree in 3-connected graphs

In a recent paper, Barnette showed that every 3-connected planar graph has a 2-connected spanning subgraph of maximum degree at most fifteen, he also constructed a planar triangulation that does not have 2-connected spanning subgraphs of maximum degree five. In this paper, we show that every 3-connected graph which is embeddable in the sphere, the projective plane, the torus or the Klein bottle has a 2-connected spanning subgraph of maximum degree at most six. © 1995 John Wiley & Sons, Inc.     

A new lower bound on the number of trivially noncontractible edges in contraction critical 5-connected graphs

An edge of a k-connected graph is said to be k-contractible if its contraction results in a k-connected graph. A k-connected non-complete graph with no k-contractible edge, is called contraction critical k-connected. An edge of a k-connected graph is called trivially noncontractible if its two end vertices have a common neighbor of degree k. Ando [K. Ando, Trivially noncontractible edges in a contraction critically 5-connected graph, Discrete Math. 293 (2005) 61-72] proved that a contraction critical 5-connected graph on n vertices has at least n/2 trivially noncontractible edges. Li [Xiangjun Li, Some results about the contractible edge and the domination number of graphs, Guilin, Guangxi Normal University, 2006 (in Chinese)] improved the lower bound to n+1. In this paper, the bound is improved to the statement that any contraction critical 5-connected graph on n vertices has at least trivially noncontractible edges.     

Convex Drawings of Planar Graphs and the Order Dimension of 3-Polytopes

We define an analogue of Schnyder's tree decompositions for 3-connected planar graphs. Based on this structure we obtain: Let G be a 3-connected planar graph with f faces, then G has a convex drawing with its vertices embedded on the (f–1)×(f–1) grid. Let G be a 3-connected planar graph. The dimension of the incidence order of vertices, edges and bounded faces of G is at most 3.The second result is originally due to Brightwell and Trotter. Here we give a substantially simpler proof.     

Improvements on the density of maximal 1‐planar graphs

A graph is 1‐planar if it can be drawn in the plane such that each edge is crossed at most once. A graph, together with a 1‐planar drawing is called 1‐plane. A graph is maximal 1‐planar (1‐plane), if we cannot add any missing edge so that the resulting graph is still 1‐planar (1‐plane). Brandenburg et al. showed that there are maximal 1‐planar graphs with only edges and maximal 1‐plane graphs with only edges. On the other hand, they showed that a maximal 1‐planar graph has at least edges, and a maximal 1‐plane graph has at least edges. We improve both lower bounds to .     

On Hamilton cycles in certain planar graphs

Let G be a 2-connected plane graph with outer cycle X_G such that for every minimal vertex cut S of G with |S| ≤ 3, every component of G\S contains a vertex of X_G. A sufficient condition for G to be Hamiltonian is presented. This theorem generalizes both Tutte's theorem that every 4-connected planar graph is Hamiltonian, as well as a recent theorem of Dillencourt about NST-triangulations. A linear algorithm to find a Hamilton cycle can be extracted from the proof. One corollary is that a 4-connected planar graph with the vertices of a triangle deleted is Hamiltonian. © 1996 John Wiley & Sons, Inc.     

On triconnected and cubic plane graphs on given point sets

Let S be a set of n4 points in general position in the plane, and let h<n be the number of extreme points of S. We show how to construct a 3-connected plane graph with vertex set S, having max{3n/2,n+h−1} edges, and we prove that there is no 3-connected plane graph on top of S with a smaller number of edges. In particular, this implies that S admits a 3-connected cubic plane graph if and only if n4 is even and hn/2+1. The same bounds also hold when 3-edge-connectivity is considered. We also give a partial characterization of the point sets in the plane that can be the vertex set of a cubic plane graph.     

Proper 1-immersions of graphs triangulating the plane

In this paper we study what planar graphs are “rigid” enough such that they can not be drawn on the plane with few (1, 2, or 3) crossings per edge. A graph drawn on the plane is k$k$-immersed in the plane if each edge is crossed by at most k$k$ other edges. By a proper  k$k$-immersion of a graph we mean a k$k$-immersion of the graph in the plane such that there is at least one crossing point. We give a characterization (in terms of forbidden subgraphs) of 4-connected graphs which triangulate the plane and have a proper 1-immersion. We show that every planar graph has a proper 3-immersion.     

Paths with restricted degrees of their vertices in planar graphs

In this paper it is proved that every 3-connected planar graph contains a path on 3 vertices each of which is of degree at most 15 and a path on 4 vertices each of which has degree at most 23. Analogous results are stated for 3-connected planar graphs of minimum degree 4 and 5. Moreover, for every pair of integers n 3, k 4 there is a 2-connected planar graph such that every path on n vertices in it has a vertex of degree k.     

The 2-Extendability of Graphs on the Projective Plane, the Torus and the Klein Bottle

A graph is said to be k-extendable if any independent set of k edges extends to a perfect matching. We shall show that every 5-connected graph of even order embedded on the projective plane and every 6-connected one embedded on the torus and the Klein bottle is 2-extendable and characterize the forbidden structures for 5-connected toroidal graphs to be 2-extendable.     

SEFE without Mapping via Large Induced Outerplane Graphs in Plane Graphs

We show that every n‐vertex planar graph admits a simultaneous embedding without mapping and with fixed edges with any ‐vertex planar graph. In order to achieve this result, we prove that every n‐vertex plane graph has an induced outerplane subgraph containing at least vertices. Also, we show that every n‐vertex planar graph and every n‐vertex planar partial 3‐tree admit a simultaneous embedding without mapping and with fixed edges.