Planar embeddings with infinite faces

We investigate vertex‐transitive graphs that admit planar embeddings having infinite faces, i.e., faces whose boundary is a double ray. In the case of graphs with connectivity exactly 2, we present examples wherein no face is finite. In particular, the planar embeddings of the Cartesian product of the r‐valent tree with K₂ are comprehensively studied and enumerated, as are the automorphisms of the resulting maps, and it is shown for r = 3 that no vertex‐transitive group of graph automorphisms is extendable to a group of homeomorphisms of the plane. We present all known families of infinite, locally finite, vertex‐transitive graphs of connectivity 3 and an infinite family of 4‐connected graphs that admit planar embeddings wherein each vertex is incident with an infinite face. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 257–275, 2003     

On Toughness and Hamiltonicity of 2K2‐Free Graphs

The toughness of a (noncomplete) graph G is the minimum value of t for which there is a vertex cut A whose removal yields components. Determining toughness is an NP‐hard problem for general input graphs. The toughness conjecture of Chvátal, which states that there exists a constant t such that every graph on at least three vertices with toughness at least t is hamiltonian, is still open for general graphs. We extend some known toughness results for split graphs to the more general class of 2K₂‐free graphs, that is, graphs that do not contain two vertex‐disjoint edges as an induced subgraph. We prove that the problem of determining toughness is polynomially solvable and that Chvátal's toughness conjecture is true for 2K₂‐free graphs.     

K4,4 − e has no finite planar cover

A graph G has a planar cover if there exists a planar graph H , and a homomorphism φ : H → G that maps the neighbors of each vertex bijectively. Each graph that has an embedding in the projective plane also has a finite planar cover. Negami conjectured the converse in 1988. This conjecture holds as long as no minor-minimal nonprojective graph has a finite planar cover. From the list there remain only two cases not solved yet—the graphs K _4,4 − e and K _1,2,2,2. We prove the nonexistence of a finite planar cover of K _4,4 − e. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 51–60, 1998     

On second order degree of graphs

Given a vertex v of a graph G the second order degree of v denoted as d 2(v) is defined as the number of vertices at distance 2 from v.In this paper we address the following question:What are the sufficient conditions for a graph to have a vertex v such that d2(v) ≥ d(v),where d(v) denotes the degree of v? Among other results,every graph of minimum degree exactly 2,except four graphs,is shown to have a vertex of second order degree as large as its own degree.Moreover,every K-4-free graph or every maximal planar graph is shown to have a vertex v such that d2(v) ≥ d(v).Other sufficient conditions on graphs for guaranteeing this property are also proved.     

不含有5-圈和k4平面图的森林分解

本文研究了不含有5-圈和K₄的平面图的森林分解问题.利用权转移法,证明了任意不含有5-圈和K₄的平面图能分解成三个森林,且其中有一个森林的最大度不超过2,这一结果推广了文献[2,3]中的结论.     

Maximum Zagreb index, minimum hyper-Wiener index and graph connectivity

In this work we show that among all n-vertex graphs with edge or vertex connectivity k, the graph G=K_k(K₁+K_n−k−1), the join of K_k, the complete graph on k vertices, with the disjoint union of K₁ and K_n−k−1, is the unique graph with maximum sum of squares of vertex degrees. This graph is also the unique n-vertex graph with edge or vertex connectivity k whose hyper-Wiener index is minimum.     

Clique-critical graphs: Maximum size and recognition

The clique graph of G, K(G), is the intersection graph of the family of cliques (maximal complete sets) of G. Clique-critical graphs were defined as those whose clique graph changes whenever a vertex is removed. We prove that if G has m edges then any clique-critical graph in K^-1(G) has at most 2m vertices, which solves a question posed by Escalante and Toft [On clique-critical graphs, J. Combin. Theory B 17 (1974) 170-182]. The proof is based on a restatement of their characterization of clique-critical graphs. Moreover, the bound is sharp. We also show that the problem of recognizing clique-critical graphs is NP-complete.     

Matching graphs

The matching graph M(G) of a graph G is that graph whose vertices are the maximum matchings in G and where two vertices M₁ and M₂ of M(G) are adjacent if and only if |M₁ − M₂| = 1. When M(G) is connected, this graph models a metric space whose metric is defined on the set of maximum matchings in G. Which graphs are matching graphs of some graph is not known in general. We determine several forbidden induced subgraphs of matching graphs and add even cycles to the list of known matching graphs. In another direction, we study the behavior of sequences of iterated matching graphs. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 73–86, 1998     

Zero-Divisor Semigroups and Some Simple Graphs

In this article, we study commutative zero-divisor semigroups determined by graphs. We prove that for all n ≥ 4, the complete graph K _n together with two end vertices has a unique corresponding zero-divisor semigroup, while the complete graph K _n together with three end vertices has no corresponding semigroups. We determine all the twenty zero-divisor semigroups whose zero-divisor graphs are the complete graph K ₃ together with an end vertex.     

Forbidding Kuratowski Graphs as Immersions

Immersion is a containment relation on graphs that is weaker than topological minor. (Every topological minor of a graph is also its immersion.) The graphs that do not contain any of the Kuratowski graphs (K₅ and K_{3, 3}) as topological minors are exactly planar graphs. We give a structural characterization of graphs that exclude the Kuratowski graphs as immersions. We prove that they can be constructed from planar graphs that are subcubic or of branch‐width at most 10 by repetitively applying i‐edge‐sums, for . We also use this result to give a structural characterization of graphs that exclude K_{3, 3} as an immersion.     

On graphs without crowns with regularμ-subgraphs

Anm-crown is the complete tripartite graphK _{1, 1,m} with parts of order 1, 1,m, and anm-claw is the complete bipartite graphK _1,m with parts of order 1,m, wherem ≥ 3. A vertexa of a graph Γ is calledweakly reduced iff the subgraph {x є Γ ‖a ^⊥ =x ^⊥} consists of one vertex. A graph Γ is calledweakly reduced iff all its vertices are weakly reduced. In the present paper we classify all connected weakly reduced graphs without 3-crowns, all of whose μ-subgraphs are regular graphs of constant nonzero valency. In particular, we generalize the characterization of Grassman and Johnson graphs due to Numata, and the characterization of connected reduced graphs without 3-claws due to Makhnev. Translated fromMatematicheskie Zametki, Vol. 67, No. 6, pp. 874–881, June, 2000. This research was supported by the Russian Foundation for Basic Research under grant No. 99-01-00462.     

On Switching to H‐Free Graphs

In this article, we study the problem of deciding if, for a fixed graph H, a given graph is switching equivalent to an H‐free graph. Polynomial‐time algorithms are known for H having at most three vertices or isomorphic to P₄. We show that for H isomorphic to a claw, the problem is polynomial, too. On the other hand, we give infinitely many graphs H such that the problem is NP‐complete, thus solving an open problem [Kratochvíl, Ne?et?il and Zýka, Ann Discrete Math 51 (1992)]. Further, we give a characterization of graphs switching equivalent to a K_{1, 2}‐free graph by ten forbidden‐induced subgraphs, each having five vertices. We also give the forbidden‐induced subgraphs for graphs switching equivalent to a forest of bounded vertex degrees.     

Planar graphs and poset dimension

We view the incidence relation of a graph G=(V. E) as an order relation on its vertices and edges, i.e. a<_G b if and only of a is a vertex and b is an edge incident on a. This leads to the definition of the order-dimension of G as the minimum number of total orders on V E whose intersection is <_G. Our main result is the characterization of planar graphs as the graphs whose order-dimension does not exceed three. Strong versions of several known properties of planar graphs are implied by this characterization. These properties include: each planar graph has arboricity at most three and each planar graph has a plane embedding whose edges are straight line segments. A nice feature of this embedding is that the coordinates of the vertices have a purely combinatorial meaning.     

Recognizing Planar Strict Quasi-Parity Graphs

 A graph is a strict-quasi parity (SQP) graph if every induced subgraph that is not a clique contains a pair of vertices with no odd chordless path between them (an “even pair”). We present an O(n ³) algorithm for recognizing planar strict quasi-parity graphs, based on Wen-Lian Hsu's decomposition of planar (perfect) graphs and on the (non-algorithmic) characterization of planar minimal non-SQP graphs given in [9]. Received: September 21, 1998 Final version received: May 9, 2000     

Another two graphs with no planar covers

A graph H is a cover of a graph G if there exists a mapping φ from V( H ) onto V( G ) such that φ maps the neighbors of every vertex υ in H bijectively to the neighbors of φ(υ) in G . Negami conjectured in 1986 that a connected graph has a finite planar cover if and only if it embeds in the projective plane. It follows from the results of Archdeacon, Fellows, Negami, and the author that the conjecture holds as long as K _1,2,2,2 has no finite planar cover. However, this is still an open question, and K _1,2,2,2 is not the only minor‐minimal graph in doubt. Let ??₄ (?₂) denote the graph obtained from K _1,2,2,2 by replacing two vertex‐disjoint triangles (four edge‐disjoint triangles) not incident with the vertex of degree 6 with cubic vertices. We prove that the graphs ??₄ and ?₂ have no planar covers. This fact is used in [P. Hlin?ný, R. Thomas, On possible counterexamples to Negami's planar cover conjecture, 1999 (submitted)] to show that there are, up to obvious constructions, at most 16 possible counterexamples to Negami's conjecture. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 227–242, 2001     

From regular boundary graphs to antipodal distance-regular graphs

Let Γ be a regular graph with n vertices, diameter D, and d + 1 different eigenvalues λ > λ₁ > ··· > λ_d. In a previous paper, the authors showed that if P(λ) > n − 1, then D ≤ d − 1, where P is the polynomial of degree d − 1 which takes alternating values ± 1 at λ₁, …, λ_d. The graphs satisfying P(λ) = n − 1, called boundary graphs, have shown to deserve some attention because of their rich structure. This paper is devoted to the study of this case and, as a main result, it is shown that those extremal (D = d) boundary graphs where each vertex have maximum eccentricity are, in fact, 2-antipodal distance-regular graphs. The study is carried out by using a new sequence of orthogonal polynomials, whose special properties are shown to be induced by their intrinsic symmetry. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 123–140, 1998     

On conservative and supermagic graphs

A graph is called supermagic if it admits a labelling of the edges by pairwise different consecutive positive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. A graph G is called conservative if it admits an orientation and a labelling of the edges by integers {1,…,|E(G)|} such that at each vertex the sum of the labels on the incoming edges is equal to the sum of the labels on the outgoing edges. In this paper we deal with conservative graphs and their connection with the supermagic graphs. We introduce a new method to construct supermagic graphs using conservative graphs. Inter alia we show that the union of some circulant graphs and regular complete multipartite graphs are supermagic.     

The symmetric (2k,k)‐graphs

A noncomplete graph G is called an (n, k)‐graph if it is n‐connected and G − X is not (n − |X| + 1)‐connected for any X ⊆ V(G) with |X| ≤ k. Mader conjectured that for k ≥ 3 the graph K_{2k + 2} − (1‐factor) is the unique (2k, k)‐graph. We settle this conjecture for strongly regular graphs, for edge transitive graphs, and for vertex transitive graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 35–51, 2001     

Hadwiger's conjecture for quasi‐line graphs

A graph G is a quasi‐line graph if for every vertex v ∈ V(G), the set of neighbors of v in G can be expressed as the union of two cliques. The class of quasi‐line graphs is a proper superset of the class of line graphs. Hadwiger's conjecture states that if a graph G is not t‐colorable then it contains K_{t + 1} as a minor. This conjecture has been proved for line graphs by Reed and Seymour. We extend their result to all quasi‐line graphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 17–33, 2008     

Forbidden subgraphs and hamiitonian properties in the square of a connected graph

Various Harniltonian-like properties are investigated in the squares of connected graphs free of some set of forbidden subgraphs. The star K_1,4 the subdivision graph of K_1,3, and the subdivision graph of K_1,3 minus an endvertex play central roles. In particular, we show that connected graphs free of the subdivision graph of K_1,3 minus an endvertex have vertex pancyclic squares.