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.     

On Light Graphs in 3-Connected Plane Graphs Without Triangular or Quadrangular Faces

 We prove that each 3-connected plane graph G without triangular or quadrangular faces either contains a k-path P _k , a path on k vertices, such that each of its k vertices has degree ≤5/3k in G or does not contain any k-path. We also prove that each 3-connected pentagonal plane graph G which has a k-cycle, a cycle on k vertices, k∈ {5,8,11,14}, contains a k-cycle such that all its vertices have, in G, bounded degrees. Moreover, for all integers k and m, k≥ 3, k∉ {5,8,11,14} and m≥ 3, we present a graph in which every k-cycle contains a vertex of degree at least m. Received: June 29, 1998 Final version received: April 11, 2000     

Four gravity results

The gravity of a graph H in a given family of graphs H is the greatest integer n with the property that for every integer m, there exists a supergraph G∈H of H such that each subgraph of G, which is isomorphic to H, contains at least n vertices of degree ?m in G. Madaras and Škrekovski introduced this concept and showed that the gravity of the path P_k on k?2 vertices in the family of planar graphs of minimum degree 2 is k-2 for each k≠5,7,8,9. They conjectured that for each of the four excluded cases the gravity is k-3. In this paper we show that this holds.     

On well-covered triangulations: Part III

A graph G is said to be well-covered if every maximal independent set of vertices has the same cardinality. A planar (simple) graph in which each face is a triangle is called a triangulation. It was proved in an earlier paper Finbow et al. (2004) [3] that there are no 5-connected planar well-covered triangulations, and in Finbow et al. (submitted for publication) [4] that there are exactly four 4-connected well-covered triangulations containing two adjacent vertices of degree 4. It is the aim of the present paper to complete the characterization of 4-connected well-covered triangulations by showing that each such graph contains two adjacent vertices of degree 4.     

On well-covered triangulations: Part II

A graph G is said to be well-covered if every maximal independent set of vertices has the same cardinality. A planar (simple) graph in which each face is a triangle is called a triangulation. It was proved in an earlier paper [A. Finbow, B. Hartnell, R. Nowakowski, M. Plummer, On well-covered triangulations: Part I, Discrete Appl. Math., 132, 2004, 97-108] that there are no 5-connected planar well-covered triangulations. It is the aim of the present paper to completely determine the 4-connected well-covered triangulations containing two adjacent vertices of degree 4. In a subsequent paper [A. Finbow, B. Hartnell, R. Nowakowski, M. Plummer, On well-covered triangulations: Part III (submitted for publication)], we show that every 4-connected well-covered triangulation contains two adjacent vertices of degree 4 and hence complete the task of characterizing all 4-connected well-covered planar triangulations. There turn out to be only four such graphs. This stands in stark contrast to the fact that there are infinitely many 3-connected well-covered planar triangulations.     

Heavy cycles in k-connected weighted graphs with large weighted degree sums

A weighted graph is one in which every edge e is assigned a nonnegative number w(e), called the weight of e. The weight of a cycle is defined as the sum of the weights of its edges. The weighted degree of a vertex is the sum of the weights of the edges incident with it. In this paper, we prove that: Let G be a k-connected weighted graph with k?2. Then G contains either a Hamilton cycle or a cycle of weight at least 2m/(k+1), if G satisfies the following conditions: (1) The weighted degree sum of any k+1 pairwise nonadjacent vertices is at least m; (2) In each induced claw and each induced modified claw of G, all edges have the same weight. This generalizes an early result of Enomoto et al. on the existence of heavy cycles in k-connected weighted graphs.     

An extension of Sallee’s theorem to infinite locally finite vap-free plane graphs

A graph isk-cyclable if givenk vertices there is a cycle that contains thek vertices. Sallee showed that every finite 3-connected planar graph is 5-cyclable. In this paper, by characterizing the circuit graphs and investigating the structure of LV-graphs, we extend his result to 3-connected infinite locally finite VAP-free plane graphs.     

Large non-planar graphs and an application to crossing-critical graphs

We prove that, for every positive integer k, there is an integer N such that every 4-connected non-planar graph with at least N vertices has a minor isomorphic to K4,k, the graph obtained from a cycle of length 2k+1 by adding an edge joining every pair of vertices at distance exactly k, or the graph obtained from a cycle of length k by adding two vertices adjacent to each other and to every vertex on the cycle. We also prove a version of this for subdivisions rather than minors, and relax the connectivity to allow 3-cuts with one side planar and of bounded size. We deduce that for every integer k there are only finitely many 3-connected 2-crossing-critical graphs with no subdivision isomorphic to the graph obtained from a cycle of length 2k by joining all pairs of diagonally opposite vertices.     

Some properties of contraction-critical 5-connected graphs

Let k be a positive integer and let G be a k-connected graph. An edge of G is called k-contractible if its contraction still results in a k-connected graph. A non-complete k-connected graph G is called contraction-critical if G has no k-contractible edge. Let G be a contraction-critical 5-connected graph, Su proved in [J. Su, Vertices of degree 5 in contraction-critical 5-connected graphs, J. Guangxi Normal Univ. 17 (3) (1997) 12-16 (in Chinese)] that each vertex of G is adjacent to at least two vertices of degree 5, and thus G has at least vertices of degree 5. In this paper, we further study the properties of contraction-critical 5-connected graph. In the process, we investigate the structure of the subgraph induced by the vertices of degree 5 of G. As a result, we prove that a contraction-critical 5-connected graph G has at least vertices of degree 5.     

The Erdős–Pósa Property for Odd Cycles in Graphs of Large Connectivity

Dedicated to the memory of Paul Erdős A graph G is k-linked if G has at least 2k vertices, and, for any vertices , , ..., , , , ..., , G contains k pairwise disjoint paths such that joins for i = 1, 2, ..., k. We say that G is k-parity-linked if G is k-linked and, in addition, the paths can be chosen such that the parities of their lengths are prescribed. We prove the existence of a function g(k) such that every g(k)-connected graph is k-parity-linked if the deletion of any set of less than 4k-3 vertices leaves a nonbipartite graph. As a consequence, we obtain a result of Erdős–Pósa type for odd cycles in graphs of large connectivity. Also, every -connected graph contains a totally odd -subdivision, that is, a subdivision of in which each edge of corresponds to an odd path, if and only if the deletion of any vertex leaves a nonbipartite graph. Received May 13, 1999/Revised June 19, 2000     

A degree sum condition for long cycles passing through a linear forest

Let G be a (k+m)-connected graph and F be a linear forest in G such that |E(F)|=m and F has at most k-2 components of order 1, where k?2 and m?0. In this paper, we prove that if every independent set S of G with |S|=k+1 contains two vertices whose degree sum is at least d, then G has a cycle C of length at least min{d-m,|V(G)|} which contains all the vertices and edges of F.     

The contractible subgraph of 5-connected graphs

An edge e of a k-connected graph G is said to be k-removable if G — e is still k-connected. A subgraph H of a k-connected graph is said to be k-contractible if its contraction results still in a k-connected graph. A k-connected graph with neither removable edge nor contractible subgraph is said to be minor minimally k-connected. In this paper, we show that there is a contractible subgraph in a 5-connected graph which contains a vertex who is not contained in any triangles. Hence, every vertex of minor minimally 5-connected graph is contained in some triangle.     

Circumferences of regular claw-free graphs

A known result obtained independently by Fan and Jung is that every 3-connected k-regular graph on n vertices contains a cycle of length at least min{3k,n}. This raises the question of how much can be said about the circumferences of 3-connected k-regular claw-free graphs. In this paper, we show that every 3-connected k-regular claw-free graph on n vertices contains a cycle of length at least min{6k-17,n}.     

Spanning Trees with Few Leaves

In this paper, we prove that an m-connected graph G on n vertices has a spanning tree with at most k leaves (for k ≥ 2 and m ≥ 1) if every independent set of G with cardinality m + k contains at least one pair of vertices with degree sum at least n − k + 1. This is a common generalization of results due to Broersma and Tuinstra and to Win.     

The New Lower Bound of the Number of Vertices of Degree 5 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. Let G be a contraction critical 5-connected graph, in this paper we show that G has at least ${\frac{1}{2}|G|}$ vertices of degree 5.     

Oriented coloring of triangle-free planar graphs and 2-outerplanar graphs

A graph is 2-outerplanar if it has a planar embedding such that the subgraph obtained by removing the vertices of the external face is outerplanar (i.e. with all its vertices on the external face). An oriented k-coloring of an oriented graph G is a homomorphism from G to an oriented graph H of order k. We prove that (1) every oriented triangle-free planar graph has an oriented chromatic number at most 40, and (2) every oriented 2-outerplanar graph has an oriented chromatic number at most 40, that improves the previous known bounds of 47 and 67, respectively.     

Vertices of Degree 5 in a Contraction Critically 5-connected Graph

An edge of a k-connected graph is said to be k-contractible if the contraction of the edge results in a k-connected graph. A k-connected graph with no k-contractible edge is said to be contraction critically k-connected. We prove that a contraction critically 5-connected graph on n vertices has at least n/5 vertices of degree 5. We also show that, for a graph G and an integer k greater than 4, there exists a contraction critically k-connected graph which has G as its induced subgraph.     

Long cycles in 4-connected planar graphs

Let G be a 4-connected planar graph on n vertices. Malkevitch conjectured that if G contains a cycle of length 4, then G contains a cycle of length k for every k∈{n,n−1,…,3}. This conjecture is true for every k∈{n,n−1,…,n−6} with k≥3. In this paper, we prove that G also has a cycle of length n−7 provided n≥10.     

Removable edges in a 5-connected graph and a construction method of 5-connected graphs

An edge e of a k-connected graph G is said to be a removable edge if G?e is still k-connected. A k-connected graph G is said to be a quasi (k+1)-connected if G has no nontrivial k-separator. The existence of removable edges of 3-connected and 4-connected graphs and some properties of quasi k-connected graphs have been investigated [D.A. Holton, B. Jackson, A. Saito, N.C. Wormale, Removable edges in 3-connected graphs, J. Graph Theory 14(4) (1990) 465-473; H. Jiang, J. Su, Minimum degree of minimally quasi (k+1)-connected graphs, J. Math. Study 35 (2002) 187-193; T. Politof, A. Satyanarayana, Minors of quasi 4-connected graphs, Discrete Math. 126 (1994) 245-256; T. Politof, A. Satyanarayana, The structure of quasi 4-connected graphs, Discrete Math. 161 (1996) 217-228; J. Su, The number of removable edges in 3-connected graphs, J. Combin. Theory Ser. B 75(1) (1999) 74-87; J. Yin, Removable edges and constructions of 4-connected graphs, J. Systems Sci. Math. Sci. 19(4) (1999) 434-438]. In this paper, we first investigate the relation between quasi connectivity and removable edges. Based on the relation, the existence of removable edges in k-connected graphs (k?5) is investigated. It is proved that a 5-connected graph has no removable edge if and only if it is isomorphic to K₆. For a k-connected graph G such that end vertices of any edge of G have at most k-3 common adjacent vertices, it is also proved that G has a removable edge. Consequently, a recursive construction method of 5-connected graphs is established, that is, any 5-connected graph can be obtained from K₆ by a number of θ⁺-operations. We conjecture that, if k is even, a k-connected graph G without removable edge is isomorphic to either K_k+1 or the graph H_k/2+1 obtained from K_k+2 by removing k/2+1 disjoint edges, and, if k is odd, G is isomorphic to K_k+1.     

2‐connected 7‐coverings of 3‐connected graphs on surfaces

An m‐covering of a graph G is a spanning subgraph of G with maximum degree at most m. In this paper, we shall show that every 3‐connected graph on a surface with Euler genus k ≥ 2 with sufficiently large representativity has a 2‐connected 7‐covering with at most 6k ? 12 vertices of degree 7. We also construct, for every surface F² with Euler genus k ≥ 2, a 3‐connected graph G on F² with arbitrarily large representativity each of whose 2‐connected 7‐coverings contains at least 6k ? 12 vertices of degree 7. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 26–36, 2003