The Las Vergnas polynomial for embedded graphs

The Las Vergnas polynomial is an extension of the Tutte polynomial to cellularly embedded graphs. It was introduced by Michel Las Vergnas in 1978 as special case of his Tutte polynomial of a morphism of matroids. While the general Tutte polynomial of a morphism of matroids has a complete set of deletion–contraction relations, its specialisation to cellularly embedded graphs does not. Here we extend the Las Vergnas polynomial to graphs in pseudo-surfaces. We show that in this setting we can define deletion and contraction for embedded graphs consistently with the deletion and contraction of the underlying matroid perspective, thus yielding a version of the Las Vergnas polynomial with complete recursive definition. This also enables us to obtain a deeper understanding of the relationships among the Las Vergnas polynomial, the Bollobás–Riordan polynomial, and the Krushkal polynomial. We also take this opportunity to extend some of Las Vergnas’ results on Eulerian circuits from graphs in surfaces of low genus to graphs in surfaces of arbitrary genus.     

A polynomial of graphs on surfaces

ribbon graphs , i.e., graphs realized as disks (vertices) joined together by strips (edges) glued to their boundaries, corresponding to neighbourhoods of graphs embedded into surfaces. We construct a four-variable polynomial invariant of these objects, the ribbon graph polynomial, which has all the main properties of the Tutte polynomial. Although the ribbon graph polynomial extends the Tutte polynomial, its definition is very different, and it depends on the topological structure in an essential way. Received: 14 September 2000 / Published online: 18 January 2002     

A remark on embedded bipartite graphs

A use of Euler's formula in Zaks (J. Combin. Theory Ser. B 32 (1982), 95–98) is replaced by an elementary argument on permutations.     

Trivalent orbit polynomial graphs

We introduce orbit polynomial graphs, and discuss their connections with distance- transitive, distance-regular, and distance polynomial graphs. After some general results, we classify all of the nonsymmetric trivalent orbit polynomial graphs.     

Thickness and outerthickness for embedded graphs

We prove new upper bounds for the thickness and outerthickness of a graph in terms of its orientable and nonorientable genus by applying the method of deleting spanning disks of embeddings to approximate the thickness and outerthickness. We also show that every non-planar toroidal graph can be edge partitioned into a planar graph and an outerplanar graph. This implies that the outerthickness of the torus (the maximum outerthickness of all toroidal graphs) is 3. Finally, we show that all graphs embeddable in the double torus have thickness at most 3 and outerthickness at most 5.     

Transnormal graphs of polynomial curves

We take up the study of transnormal graphs again. We recall that some results on this topic appeared in [2], [3], [4] and [8]. The purpose of this paper is two-fold. We start by considering curves in Euclidean n-space and extend the results in [3]. The main result shows that no polynomial curve of positive even degree (see below for the definitions) has transnormal graph. In section 3 we deal with polynomial functions f: of odd degree. Some conditions are proved to be necessary and sufficient for the transnormality of the graph. The results obtained enable us to characterize the polynomial functions of degree less than or equal to 5 which have transnormal graph.To Professor N. K. Stephanidis on his 65^th birthday     

The Hosoya polynomial decomposition for catacondensed benzenoid graphs

For a graph G with the vertex set V(G), we denote by d(u,v) the distance between vertices u and v in G, by d(u) the degree of vertex u. The Hosoya polynomial of G is H(G)=∑_{u,v}⊆V(G)x^d(u,v). The partial Hosoya polynomials of G are for positive integer numbers m and n. It is shown that H(G₁)−H(G₂)=x²(x+1)²(H₃₃(G₁)−H₃₃(G₂)),H₂₂(G₁)−H₂₂(G₂)=(x²+x−1)²(H₃₃(G₁)−H₃₃(G₂)) and H₂₃(G₁)−H₂₃(G₂)=2(x²+x−1)(H₃₃(G₁)−H₃₃(G₂)) for arbitrary catacondensed benzenoid graphs G₁ and G₂ with equal number of hexagons. As an application, we give an affine relationship between H(G) with two other distance-based polynomials constructed by Gutman [I. Gutman, Some relations between distance-based polynomials of trees, Bulletin de l’Académie Serbe des Sciences et des Arts (Cl. Math. Natur.) 131 (2005) 1-7].     

A polynomial time algorithm for finding the prime factors of cartesian-product graphs

We consider the computational complexity of recognizinf concerned cartesian product graphs. Sabidussi gives a non-algorithmic proof that the cartesian factorization is unique. He uses a tower of successively coarser equivalence relations on the edge set in which each prime factor of the graph is identified with an equivalence class in the coarsest of the relations. We first explore the structure and size of the relation at the base of the tower. Then we give a polynomial-time algorithm to compute the relations and to construct the prime factors of any connected graph. The bounds on the size of the relations are crucial to the runtime analysis of our algorithm.     

A result on combinatorial curvature for embedded graphs on a surface

Let G be an infinite graph embedded in a surface such that each open face of the embedding is homeomorphic to an open disk and is bounded by finite number of edges. For each vertex x of G, we define the combinatorial curvature

     

Homomorphisms and polynomial invariants of graphs

This paper initiates a general study of the connection between graph homomorphisms and the Tutte polynomial. This connection can be extended to other polynomial invariants of graphs related to the Tutte polynomial such as the transition, the circuit partition, the boundary, and the coboundary polynomials. As an application, we describe in terms of homomorphism counting some fundamental evaluations of the Tutte polynomial in abelian groups and statistical physics. We conclude the paper by providing a homomorphism view of the uniqueness conjectures formulated by Bollobás, Pebody and Riordan.     

Coloring edges of embedded graphs

In this paper, we prove that any graph G with maximum degree , which is embeddable in a surface Σ of characteristic χ(Σ) ≤ 1 and satisfies , is class one. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 197–205, 2000     

Automorphism properties of embedded graphs

This paper presents some conditions under which every automorphism of a graph, embedded on a surface of positive genus, maps face boundaries of the embedding to face boundaries. These results extend a result of Whitney which provides an analogous, but simpler, condition for planar graphs. The new result is applied to graphs on the torus to obtain a classification of many toroidal vertex-, edge-, and face-transitive graphs.     

Face colorings of embedded graphs

We characterize those graphs which have at least one embedding into some surface such that the faces can be properly colored in four or fewer colors. Embeddings into both orientable and nonorientable surfaces are considered.     

Coloring-flow duality of embedded graphs

Let be a directed graph embedded in a surface. A map is a tension if for every circuit , the sum of on the forward edges of is equal to the sum of on the backward edges of . If this condition is satisfied for every circuit of which is a contractible curve in the surface, then is a local tension. If holds for every , we say that is a (local) -tension. We define the circular chromatic number and the local circular chromatic number of by and , respectively. The invariant is a refinement of the usual chromatic number, whereas is closely related to Tutte's flow index and Bouchet's biflow index of the surface dual .

From the definitions we have . The main result of this paper is a far-reaching generalization of Tutte's coloring-flow duality in planar graphs. It is proved that for every surface and every 0$">, there exists an integer so that holds for every graph embedded in with edge-width at least , where the edge-width is the length of a shortest noncontractible circuit in .

In 1996, Youngs discovered that every quadrangulation of the projective plane has chromatic number 2 or 4, but never 3. As an application of the main result we show that such `bimodal' behavior can be observed in , and thus in for two generic classes of embedded graphs: those that are triangulations and those whose face boundaries all have even length. In particular, if is embedded in some surface with large edge-width and all its faces have even length , then . Similarly, if is a triangulation with large edge-width, then . It is also shown that there exist Eulerian triangulations of arbitrarily large edge-width on nonorientable surfaces whose circular chromatic number is equal to 5.

     

A polynomial algorithm for the max-cut problem on graphs without long odd cycles

Given a graphG=[V, E] with positive edge weights, the max-cut problem is to find a cut inG such that the sum of the weights of the edges of this cut is as large as possible. Letg(K) be the class of graphs whose longest odd cycle is not longer than2K+1, whereK is a nonnegative integer independent of the numbern of nodes ofG. We present an O(n ^4K) algorithm for the max-cut problem for graphs ing(K). The algorithm is recursive and is based on some properties of longest and longest odd cycles of graphs. This research was supported by National Science Foundation Grant ECS-8005350 to Cornell University.     

Strongly regular graphs and spin models for the Kauffman polynomial

We study spin models for invariants of links as defined by Jones [22]. We consider the two algebras generated by the weight matrices of such models under ordinary or Hadamard product and establish an isomorphism between them. When these algebras coincide they form the Bose-Mesner algebra of a formally self-dual association scheme. We study the special case of strongly regular graphs, which is associated to a particularly interesting link invariant, the Kauffman polynomial [27]. This leads to a classification of spin models for the Kauffman polynomial in terms of formally self-dual strongly regular graphs with strongly regular subconstituents [7]. In particular we obtain a new model based on the Higman-Sims graph [17].     

A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles

The vertex packing problem for a given graph is to find a maximum number of vertices no two of which are joined by an edge. The weighted version of this problem is to find a vertex packingP such that the sum of the individual vertex weights is maximum. LetG be the family of graphs whose longest odd cycle is of length not greater than 2K + 1, whereK is any non-negative integer independent of the number (denoted byn) of vertices in the graph. We present an O(n ^2K+1) algorithm for the maximum weighted vertex packing problem for graphs inG 1. A by-product of this algorithm is an algorithm for piecing together maximum weighted packings on blocks to find maximum weighted packings on graphs that contain more than one block. We also give an O(n ^2K+3) algorithm for testing membership inG This work was supported by NSF grant ENG75-00568 to Cornell University. Some of the results of this paper have appeared in Hsu's unpublished Ph.D. dissertation [9].