Projective‐Planar Graphs with no K3, 4‐Minor. II

The authors previously published an iterative process to generate a class of projective‐planar K_{3, 4}‐free graphs called “patch graphs.” They also showed that any simple, almost 4‐connected, nonplanar, and projective‐planar graph that is K_{3, 4}‐free is a subgraph of a patch graph. In this article, we describe a simpler and more natural class of cubic K_{3, 4}‐free projective‐planar graphs that we call Möbius hyperladders. Furthermore, every simple, almost 4‐connected, nonplanar, and projective‐planar graph that is K_{3, 4}‐free is a minor of a Möbius hyperladder. As applications of these structures we determine the page number of patch graphs and of Möbius hyperladders.     

Regular factors in K1,3-free graphs

We show that every connected K_1,3-free graph with minimum degree at least 2k contains a k-factor and construct connected K_1,3-free graphs with minimum degree k + 0(√k) that have no k-factor.     

A pair of forbidden subgraphs and perfect matchings in graphs of high connectivity

Sumner [7] proved that every connected K _1,3-free graph of even order has a perfect matching. He also considered graphs of higher connectivity and proved that if m ≥ 2, every m-connected K _1,m+1-free graph of even order has a perfect matching. In [6], two of the present authors obtained a converse of sorts to Sumner’s result by asking what single graph one can forbid to force the existence of a perfect matching in an m-connected graph of even order and proved that a star is the only possibility. In [2], Fujita et al. extended this work by considering pairs of forbidden subgraphs which force the existence of a perfect matching in a connected graph of even order. But they did not settle the same problem for graphs of higher connectivity. In this paper, we give an answer to this problem. Together with the result in [2], a complete characterization of the pairs is given.     

Hamiltonian results in K1,3-free graphs

There have been a number of results dealing with Hamiltonian properties in powers of graphs. In this paper we show that the square and the total graph of a K_1,3-free graph are vertex pancyclic. We then discuss some of the relationships between connectivity and Hamiltonian properties in K_1,3-free graphs.     

Hamiltonian connectedness in 3-connected line graphs

We investigate graphs G such that the line graph L(G) is hamiltonian connected if and only if L(G) is 3-connected, and prove that if each 3-edge-cut contains an edge lying in a short cycle of G, then L(G) has the above mentioned property. Our result extends Kriesell’s recent result in [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected line graph of a claw free graph is hamiltonian connected. Another application of our main result shows that if L(G) does not have an hourglass (a graph isomorphic to K₅−E(C₄), where C₄ is an cycle of length 4 in K₅) as an induced subgraph, and if every 3-cut of L(G) is not independent, then L(G) is hamiltonian connected if and only if κ(L(G))≥3, which extends a recent result by Kriesell [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected hourglass free line graph is hamiltonian connected.     

On connected factors inK 1,3-free graphs

A graph is said to beK _1,3-free if it contains noK _1,3 as an induced subgraph. It is shown in this paper that every 2-connectedK _1,3-free graph contains a connected [2,3]-factor. We also obtain that every connectedK _1,3-free graph has a spanning tree with maximum degree at most 3. This research is partially supported by the National Natural Sciences Foundation of China and by the Natural Sciences Foundation of Shandong Province of China.     

On Cubic Graphs Admitting an Edge-Transitive Solvable Group

Using covering graph techniques, a structural result about connected cubic simple graphs admitting an edge-transitive solvable group of automorphisms is proved. This implies, among other, that every such graph can be obtained from either the 3-dipole Dip₃ or the complete graph K ₄, by a sequence of elementary-abelian covers. Another consequence of the main structural result is that the action of an arc-transitive solvable group on a connected cubic simple graph is at most 3-arc-transitive. As an application, a new infinite family of semisymmetric cubic graphs, arising as regular elementary abelian covering projections of K _3,3, is constructed.     

Subdivisions of K5 in Graphs Embedded on Surfaces With Face‐Width at Least 5

We prove that if G is a 5‐connected graph embedded on a surface Σ (other than the sphere) with face‐width at least 5, then G contains a subdivision of K₅. This is a special case of a conjecture of P. Seymour, that every 5‐connected nonplanar graph contains a subdivision of K₅. Moreover, we prove that if G is 6‐connected and embedded with face‐width at least 5, then for every v ∈ V(G), G contains a subdivision of K₅ whose branch vertices are v and four neighbors of v.     

Characterizing planarity using theta graphs

A theta graph is a homeomorph of K_2,3. In an embedded planar graph the local rotation at one degree-three vertex of a theta graph determines the local rotation at the other degree-three vertex. Using this observation, we give a characterization of planar graphs in terms of balance in an associated signed graph whose vertices are K_1,3 subgraphs and whose edges correspond to theta graphs. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 17–20, 1998     

On triangles in ‐minor free graphs

We study graphs where each edge that is incident to a vertex of small degree (of degree at most 7 and 9, respectively) belongs to many triangles (at least 4 and 5, respectively) and show that these graphs contain a complete graph (K₆ and K₇, respectively) as a minor. The second case settles a problem of Nevo. Moreover, if each edge of a graph belongs to six triangles, then the graph contains a K₈‐minor or contains K_{2, 2, 2, 2, 2} as an induced subgraph. We then show applications of these structural properties to stress freeness and coloring of graphs. In particular, motivated by Hadwiger's conjecture, we prove that every K₇‐minor free graph is 8‐colorable and every K₈‐minor free graph is 10‐colorable.     

On the conjecture of hajós

Hajós conjectured that everys-chromatic graph contains a subdivision ofK _s, the complete graph ons vertices. Catlin disproved this conjecture. We prove that almost all graphs are counter-examles in a very strong sense.     

Hamiltonian circuits in N2-locally connected K1,3-free graphs

There are many results concerned with the hamiltonicity of K_1,3-free graphs. In the paper we show that one of the sufficient conditions for the K_1,3-free graph to be Hamiltonian can be improved using the concept of second-type vertex neighborhood. The paper is concluded with a conjecture.     

Some probabilistic and extremal results on subdivisions and odd subdivisions of graphs

A probabilistic result of Bollobás and Catlin concerning the largest integer p so that a subdivision of K_p is contained in a random graph is generalized to a result concerning the largest integer p so that a subdivision of A_p is contained in a random graph for some sequence A₁, A₂,… of graphs such that A_i+1 contains a subdivision of A_i. A similar result is proved for subdivisions with odd paths or cycles. The result is applied to disprove a conjecture of Chartrand, Geller, and Hedetniemi. The maximum number of edges in a graph without a subdivision of K_p, p = 4, 5, with odd paths or cycles is determined.     

The spanning subgraphs of eulerian graphs

It is shown that a connected graph G spans an eulerian graph if and only if G is not spanned by an odd complete bigraph K(2_m + 1, 2n + 1). A disconnected graph spans an eulerian graph if and only if it is not the union of the trivial graph with a complete graph of odd order. Exact formulas are obtained for the number of lines which must be added to such graphs in order to get eulerian graphs.     

Every connected,locally connected nontrivial graph with no induced claw is hamiltonian

A graph is locally connected if every neighborthood induces a connected subgraph. We show here that every connected, locally connected graph on p ≥ 3 vertices and having no induced K_1,3 is Hamiltonian. Several sufficient conditions for a line graph to be Hamiltonian are obtained as corollaries.     

Clique‐inverse graphs of K3‐free and K4‐free graphs

The clique graph K(G) of a given graph G is the intersection graph of the collection of maximal cliques of G. Given a family ℱ of graphs, the clique‐inverse graphs of ℱ are the graphs whose clique graphs belong to ℱ. In this work, we describe characterizations for clique‐inverse graphs of K₃‐free and K₄‐free graphs. The characterizations are formulated in terms of forbidden induced subgraphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 257–272, 2000     

On the join of graphs and chromatic uniqueness

A graph is chromatically unique if it is uniquely determined by its chromatic polynomial. Let G be a chromatically unique graph and let K_m denote the complete graph on m vertices. This paper is mainly concerned with the chromaticity of K_m + G where + denotes the join of graphs. Also, it is shown that a large family of connected vertextransitive graphs that are not chromatically unique can be obtained by taking the join of some vertex-transitive graphs. © 1995 John Wiley & Sons, Inc.     

Minimal claw-free graphs

A graph G is a minimal claw-free graph (m.c.f. graph) if it contains no K _1,3 (claw) as an induced subgraph and if, for each edge e of G, G ™ e contains an induced claw. We investigate properties of m.c.f. graphs, establish sharp bounds on their orders and the degrees of their vertices, and characterize graphs which have m.c.f. line graphs. Support by the South African National Research Foundation is gratefully acknowledged.     

Equimatchable Regular Graphs

A graph is called equimatchable if all of its maximal matchings have the same size. Kawarabayashi, Plummer, and Saito showed that the only connected equimatchable 3‐regular graphs are K₄ and K_{3, 3}. We extend this result by showing that for an odd positive integer r, if G is a connected equimatchable r‐regular graph, then . Also it is proved that for an even r, a connected triangle‐free equimatchable r‐regular graph is isomorphic to one of the graphs C₅, C₇, and .     

Maximal non- hamilton-laceable graphs

For bipartite graphs the property of being Hamilton laceable is analogous to the property of being Hamilton connected for simple graphs. in this paper it is proven that all of the graphs obtained by deleting fewer than m ? 1 edges from either of the complete bipartite graphs K_{m, m} or K_{m, m+1} are Hamilton laceable. It is also proven that the deletion of m ? 1 edges results in a non-Hamiltonlaceable graph if and only if the graph is either the complement of the star K_1,m?1 in K_{m, m} or K_{m, m+1} or else the complement in K_3,3 of a pair of nonadjacent edges.