Hamilton cycles in plane triangulations

We extend Whitney's Theorem that every plane triangulation without separating triangles is hamiltonian by allowing some separating triangles. More precisely, we define a decomposition of a plane triangulation G into 4‐connected ‘pieces,’ and show that if each piece shares a triangle with at most three other pieces then G is hamiltonian. We provide an example to show that our hypothesis that each piece shares a triangle with at most three other pieces' cannot be weakened to ‘four other pieces.’ As part of our proof, we also obtain new results on Tutte cycles through specified vertices in planar graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 138–150, 2002     

Approximation algorithms via contraction decomposition

We prove that the edges of every graph of bounded (Euler) genus can be partitioned into any prescribed number k of pieces such that contracting any piece results in a graph of bounded treewidth (where the bound depends on k). This decomposition result parallels an analogous, simpler result for edge deletions instead of contractions, obtained in [4,20, 10, 17], and it generalizes a similar result for “compression” (a variant of contraction) in planar graphs [29]. Our decomposition result is a powerful tool for obtaining PTASs for contraction-closed problems (whose optimal solution only improves under contraction), a much more general class than minor-closed problems. We prove that any contraction-closed problem satisfying just a few simple conditions has a PTAS in bounded-genus graphs. In particular, our framework yields PTASs for the weighted Traveling Salesman Problem and for minimum-weight c-edge-connected submultigraph on bounded-genus graphs, improving and generalizing previous algorithms of [24, 1, 29, 25, 8, 5]. We also highlight the only main difficulty in extending our results to general H-minor-free graphs.     

On the linear extension complexity of stable set polytopes for perfect graphs

We study the linear extension complexity of stable set polytopes of perfect graphs. We make use of known structural results permitting to decompose perfect graphs into basic perfect graphs by means of two graph operations: 2-joins and skew partitions. Exploiting the link between extension complexity and the nonnegative rank of an associated slack matrix, we investigate the behavior of the extension complexity under these graph operations. We show bounds for the extension complexity of the stable set polytope of a perfect graph $G$ depending linearly on the size of $G$ and involving the depth of a decomposition tree of $G$ in terms of basic perfect graphs.     

Partially isometric dilations of noncommuting -tuples of operators

Given a row contraction of operators on a Hilbert space and a family of projections on the space that stabilizes the operators, we show there is a unique minimal joint dilation to a row contraction of partial isometries that satisfy natural relations. For a fixed row contraction the set of all dilations forms a partially ordered set with a largest and smallest element. A key technical device in our analysis is a connection with directed graphs. We use a Wold decomposition for partial isometries to describe the models for these dilations, and we discuss how the basic properties of a dilation depend on the row contraction.

     

Triangle‐free graphs that are signable without even holes

We characterize triangle‐free graphs for which there exists a subset of edges that intersects every chordless cycle in an odd number of edges (TF odd‐signable graphs). These graphs arise as building blocks of a decomposition theorem (for cap‐free odd‐signable graphs) obtained by the same authors. We give a polytime algorithm to test membership in this class. This algorithm is itself based on a decomposition theorem. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 204–220, 2000     

Hereditary Efficiently Dominatable Graphs

An efficient dominating set (or perfect code) in a graph is a set of vertices the closed neighborhoods of which partition the graph's vertex set. We introduce graphs that are hereditary efficiently dominatable in that sense that every induced subgraph of the graph contains an efficient dominating set. We prove a decomposition theorem for (bull, fork, C₄)‐free graphs, based on which we characterize, in terms of forbidden induced subgraphs, the class of hereditary efficiently dominatable graphs. We also give a decomposition theorem for hereditary efficiently dominatable graphs and examine some algorithmic aspects of such graphs. In particular, we give a polynomial time algorithm for finding an efficient dominating set (if one exists) in a class of graphs properly containing the class of hereditary efficiently dominatable graphs by reducing the problem to the maximum weight independent set problem in claw‐free graphs.     

Knot theory for self-indexed graphs

We introduce and study so-called self-indexed graphs. These are (oriented) finite graphs endowed with a map from the set of edges to the set of vertices. Such graphs naturally arise from classical knot and link diagrams. In fact, the graphs resulting from link diagrams have an additional structure, an integral flow. We call a self-indexed graph with integral flow a comte. The analogy with links allows us to define transformations of comtes generalizing the Reidemeister moves on link diagrams. We show that many invariants of links can be generalized to comtes, most notably the linking number, the Alexander polynomials, the link group, etc. We also discuss finite type invariants and quandle cocycle invariants of comtes.

     

A Structure Theorem for Strong Immersions

A graph H is strongly immersed in G if H is obtained from G by a sequence of vertex splittings (i.e., lifting some pairs of incident edges and removing the vertex) and edge removals. Equivalently, vertices of H are mapped to distinct vertices of G (branch vertices) and edges of H are mapped to pairwise edge‐disjoint paths in G, each of them joining the branch vertices corresponding to the ends of the edge and not containing any other branch vertices. We describe the structure of graphs avoiding a fixed graph as a strong immersion. The theorem roughly states that a graph which excludes a fixed graph as a strong immersion has a tree‐like decomposition into pieces glued together on small edge cuts such that each piece of the decomposition has a path‐like linear decomposition isolating the high degree vertices.     

Operator Decomposition of Graphs and the Reconstruction Conjecture

We present a new type of decomposition of graphs – the operator decomposition connected with the classical notion of homogeneous set (or module). Using this decomposition we prove that Kelly-Ulam reconstruction conjecture is true for graphs having homogeneous set with prescribed properties, as well as for non-p-connected graphs.     

Uniform 1-cochains and genuine laminations

We construct a pair of transverse genuine laminations on an atoroidal 3-manifold admitting a transversely orientable uniform 1-cochain. The laminations are induced by the uniform 1-cochain and they are the straightening of the coarse laminations defined by Calegari, by using minimal surface techniques. Moreover, when we collapse these laminations, we get a topological pseudo-Anosov flow, as defined by Mosher.     

Unbounded quantum graphs with unbounded boundary conditions

We consider metric graphs with a uniform lower bound on the edge lengths but no further restrictions. We discuss how to describe every local self‐adjoint Laplace operator on such graphs by boundary conditions in the vertices given by projections and self‐adjoint operators. We then characterize the lower bounded self‐adjoint Laplacians and determine their associated quadratic form in terms of the operator families encoding the boundary conditions.     

Characterizations of connected orthogonality graphs of projections of Rickart ∗-rings

In this paper, we study the orthogonality graphs (see Definition 1.2) of ortholattices. We provide a graph theoretic condition for an ortholattice to be orthomodular. We prove that, the orthogonality graphs of two orthomodular lattices are isomorphic if and only if the lattices are isomorphic. As an application, it is proved that the zero-divisor graph of a Rickart ?-ring is obtained by successively duplicating the vertices of the orthogonality graph of the lattice of projections in the ring. We characterize the finite Rickart ?-rings for which the orthogonality graph of projections is connected.     

Distance-Hereditary Comparability Graphs

We study the class of the distance-hereditary comparability graphs, that is, those graphs which admit a transitive orientation and are completely decomposable with respect to the split decomposition. We provide a characterization in terms of forbidden subgraphs. We also provide further characterizations and one of them, based on the split decomposition, is used to devise a recognizing algorithm working in linear time. Finally, we show how to build distance-hereditary comparability graphs.     

Nearly acyclic graphs are reconstructible

We prove that a graph G is reconstructible if G has a node v with G-v acyclic. The proof uses colored graphs and shows how to reconstruct some graphs from pieces which share a common subgraph having few automorphisms.     

Elementary submodels in infinite combinatorics

The use of elementary submodels is a simple but powerful method to prove theorems, or to simplify proofs in infinite combinatorics. First we introduce all the necessary concepts of logic, then we prove classical theorems using elementary submodels. We also present a new proof of Nash-Williams’s theorem on cycle decomposition of graphs, and finally we improve a decomposition theorem of Laviolette concerning bond-faithful decompositions of graphs.     

Coloring planar perfect graphs by decomposition

This paper describes a decomposition scheme for coloring perfect graphs. Based on this scheme, one need only concentrate on coloring highly connected (at least 3-connected) perfect graphs. This idea is illustrated on planar perfect graphs, which yields a straightforward coloring algorithm. We suspect that, under appropriate definition, highly connected perfect graphs might possess certain regular properties that are amenable to coloring algorithms. This research has been supported in part by National Science Foundation under grant ECS—8105989 to Northwestern University.     

Which trees are link graphs?

The link of a vertex v of a graph G is the subgraph induced by all vertices adjacent to v. If all the links of G are isomorphic to L, then G has constant link and L is called a link graph. We investigate the trees of order p≤9 to see which are link graphs. Group theoretic methods are used to obtain constructions of graphs G with constant link L for certain trees L. Necessary conditions are derived for the existence of a graph having a given graph L as its constant link. These conditions show that many trees are not link graphs. An example is given to show that a connected graph with constant link need not be point symmetric.     

Uniquely pairable graphs

The concept of a k-pairable graph was introduced by Z. Chen [On k-pairable graphs, Discrete Mathematics 287 (2004), 11-15] as an extension of hypercubes and graphs with an antipodal isomorphism. In the present paper we generalize further this concept of a k-pairable graph to the concept of a semi-pairable graph. We prove that a graph is semi-pairable if and only if its prime factor decomposition contains a semi-pairable prime factor or some repeated prime factors. We also introduce a special class of k-pairable graphs which are called uniquely k-pairable graphs. We show that a graph is uniquely pairable if and only if its prime factor decomposition has at least one pairable prime factor, each prime factor is either uniquely pairable or not semi-pairable, and all prime factors which are not semi-pairable are pairwise non-isomorphic. As a corollary we give a characterization of uniquely pairable Cartesian product graphs.     

Decomposition of the Flow Polynomial

The flow polynomials denote the number of nowhere-zero flows on graphs, and are related to the well-known Tutte polynomials and chromatic polynomials. We will show the decomposition of the flow polynomials by edge-cuts and vertex-cuts of size 2 or 3. Moreover by using this decomposition, we will consider what kind of graphs have the same flow polynomials. Another application of the decomposition results is that if a bridgeless graph G does not admit a nowhere-zero k-flow and G has a small vertex- or edge-cut, then a proper bridgeless subgraph of G (a graph minor) does not admit a nowhere-zero k-flow either.     

On the knot complement problem for non-hyperbolic knots

This paper explicitly provides two exhaustive and infinite families of pairs (M,k), where M is a lens space and k is a non-hyperbolic knot in M, which produces a manifold homeomorphic to M, by a non-trivial Dehn surgery. Then, we observe the uniqueness of such knot in such lens space, the uniqueness of the slope, and that there is no preserving homeomorphism between the initial and the final M's. We obtain further that Seifert fibered knots, except for the axes, and satellite knots are determined by their complements in lens spaces. An easy application shows that non-hyperbolic knots are determined by their complement in atoroidal and irreducible Seifert fibered 3-manifolds.