On graph invariants satisfying the deletion-contraction formula

As a generalization of chromatic polynomials, this paper deals with real-valued mappings ψ on the class of graphs satisfying ψ(G₁) = ψ(G₂) for all pairs G₁, G₂ of isomorphic graphs and ψ(G) = ψ(G − e) − ψ(G/e) for all graphs G and all edges e of G, where the definition of G/e is nonstandard. In particular, new inequalities for chromatic polynomials are presented. © 1996 John Wiley & Sons, Inc.     

Duality of graph invariants

We study a new set of duality relations between weighted,combinatoric invariants of a graph G.The dualities arise from a non-linear transform B,acting on the weight function p.We define B on a space of real-valued functions O and investigate its properties.We show that three invariants(the weighted independence number,the weighted Lovasz number,and the weighted fractional packing number) are fixed points of B~2,but the weighted Shannon capacity is not.We interpret these invariants in the study of quantum non-locality.     

A Ramsey property for graph invariants

We consider the problem of which graph invariants have a certain property relating to Ramsey's theorem. Invariants which have this property are called Ramsey functions. We examine properties of chains of graphs associated with Ramsey functions. Methods are developed which enable one to prove that a given invariant is not a Ramsey function. Results for several familiar invariants are presented.     

A unified construction of semiring-homomorphic graph invariants

Journal of Algebraic Combinatorics - It has recently been observed by Zuiddam that finite graphs form a preordered commutative semiring under the graph homomorphism preorder together with join and...     

Hierarchy for imbedding-distribution invariants of a graph

Most existing papers about graph imbeddings are concerned with the determination of minimum genus, and various others have been devoted to maximum genus or to highly symmetric imbeddings of special graphs. An entirely different viewpoint is now presented in which one seeks distributional information about the huge family of all cellular imbeddings of a graph into all closed surfaces, instead of focusing on just one imbedding or on the existence of imbeddings into just one surface. The distribution of imbeddings admits a hierarchically ordered class of computable invariants, each of which partitions the set of all graphs into much finer subcategories than the subcategories corresponding to minimum genus or to any other single imbedding surface. Quite low in this hierarchy are invariants such as the average genus, taken over all cellular imbeddings, and the average region size, where “region size” means the number of edge traversals required to complete a tour of a region boundary. Further up in the hierarchy is the multiset of duals of a graph. At an intermediate level are the “imbedding polynomials.” The hierarchy is explored, and several specific calculations of the values of some of the invariants are provided. The main results are concerned with the amount of work needed to derive one invariant from another, when possible, and with principles for computing the algebraic effect of adding an edge or of otherwise combining two graphs.     

Finite-type invariants for graphs and graph reconstructions

Many of the fundamental open problems in graph theory have the following general form: How much information does one need to know about a graph G in order to determine G uniquely. In this article we investigate a new approach to this sort of problem motivated by the notion of a finite-type invariant, recently introduced in the study of knots. We introduce the concepts of vertex-finite-type invariants of graphs, and edge-finite-type invariants of graphs, and show that these sets of functions have surprising algebraic properties. The study of these invariants is intimately related with the classical vertex- and edge-reconstruction conjectures, and we demonstrate that the algebraic properties of the finite-type invariants lead immediately to some of the fundamental results in graph reconstruction theory.     

Integration of singular braid invariants and graph cohomology

We prove necessary and sufficient conditions for an arbitrary invariant of braids with double points to be the `` derivative' of a braid invariant. We show that the ``primary obstruction to integration' is the only obstruction. This gives a slight generalization of the existence theorem for Vassiliev invariants of braids. We give a direct proof by induction on which works for invariants with values in any abelian group.

We find that to prove our theorem, we must show that every relation among four-term relations satisfies a certain geometric condition. To find the relations among relations we show that of a variant of Kontsevich's graph complex vanishes. We discuss related open questions for invariants of links and other things.

     

Reductions of the graph reconstruction conjecture

In this note we shall show that the Graph Reconstruction Conjecture (also called the Kelly-Ulam conjecture [1, p. 11]) is equivalent to a conjecture about the algebraic properties of certain directed trees and their homomorphic images. We shall show the the Greph Reconstruction Conjecture is equivalent to recognizing the (abstract) group of a graph from the tree (generalized “deck”) of the graph.     

Certain graph invariants do not distinguish all graphs

This paper considers a certain fairly large class of graph invariants and shows that for any invariant in this class, there is a pair of nonisomorphic graphs that have the same invariant. Some explicit examples of such invariants are discussed.     

The graph reconstruction number

The reconstruction number of graph G is the minimum number of point-deleted subgraphs required in order to uniquely identify the original graph G. We list, based on computer calculations, the reconstruction number for all graphs with at most seven points. Some constructions and conjectures for graphs of higher order are given. the most striking statement is our concluding conjeture that almost all graphs have have reconstruction number three.     

Further results on monotonic graph invariants and bipartiteness number

Abstract

The bipartiteness of a graph is the minimum number of vertices whose deletion from G results in a bipartite graph. If a graph invariant decreases or increases with addition of edges of its complement, then it is called a monotonic graph invariant. In this article, we determine the extremal values of some famous monotonic graph invariants, and characterize the corresponding extremal graphs in the class of all connected graphs with a given vertex bipartiteness.     

Complexity results in graph reconstruction

We investigate the relative complexity of the graph isomorphism problem (GI) and problems related to the reconstruction of a graph from its vertex-deleted or edge-deleted subgraphs (in particular, deck checking (DC) and legitimate deck (LD) problems). We show that these problems are closely related for all amounts c?1 of deletion:

(1)

, , , and .

(2)

For all k?2, and .

(3)

For all k?2, .

(4)

.

(5)

For all k?2, .

For many of these results, even the c=1 case was not previously known.Similar to the definition of reconstruction numbers vrn_∃(G) [F. Harary, M. Plantholt, The graph reconstruction number, J. Graph Theory 9 (1985) 451-454] and ern_∃(G) (see [J. Lauri, R. Scapellato Topics in Graph Automorphism and Reconstruction, London Mathematical Society, Cambridge University Press, Cambridge, 2003, p. 120]), we introduce two new graph parameters, vrn_∀(G) and ern_∀(G), and give an example of a family {G_n}_n?4 of graphs on n vertices for which vrn_∃(G_n)<vrn_∀(G_n). For every k?2 and n?1, we show that there exists a collection of k graphs on (2^k-1+1)n+k vertices with 2ⁿ 1-vertex-preimages, i.e., one has families of graph collections whose number of 1-vertex-preimages is huge relative to the size of the graphs involved.     

On the finiteness of differential invariants

In this paper we show how Weil's theory of near points yields a new light on the classical approaches to the study of the differential invariants of a sheaf of tangent vector fields. We give conditions for the existence of invariant derivations for a sheaf of tangent vector fields, which allows to apply Lie's algorithm to obtain new differential invariants as quotients of Jacobian determinants of known ones. We give sufficient conditions for the asymptotic stability of the symbol of a sheaf of tangent vector fields and prove our main result, a finiteness theorem for the differential invariants of a sheaf of Lie algebras which simplifies and improves on the treatment given in J. Differential Geom. 10 (1975) 249-416.     

Facet defining inequalities among graph invariants: The system GraPHedron

We present a new computer system, called GraPHedron, which uses a polyhedral approach to help the user to discover optimal conjectures in graph theory. We define what should be optimal conjectures and propose a formal framework allowing to identify them. Here, graphs with n nodes are viewed as points in the Euclidian space, whose coordinates are the values of a set of graph invariants. To the convex hull of these points corresponds a finite set of linear inequalities. These inequalities computed for a few values of n can be possibly generalized automatically or interactively. They serve as conjectures which can be considered as optimal by geometrical arguments.We describe how the system works, and all optimal relations between the diameter and the number of edges of connected graphs are given, as an illustration. Other applications and results are mentioned, and the forms of the conjectures that can be currently obtained with GraPHedron are characterized.     

Finite type invariants of order 3 for a spatial handcuff graph

We express a basis for the vector space of finite type invariants of order less than or equal to three for an embedded handcuff graph in a 3-sphere in terms of the linking number, the Conway polynomial, and the Jones polynomial of the sublinks of the handcuff graph.     

On the hamiltonian path graph of a graph

The hamiltonian path graph H(F) of a graph F is that graph having the same vertex set as F and in which two vertices u and v are adjacent if and only if F contains a hamiltonian u ? v path. First, in response to a conjecture of Chartrand, Kapoor and Nordhaus, a characterization of nonhamiltonian graphs isomorphic to their hamiltonian path graphs is presented. Next, the maximum size of a hamiltonian graph F of given order such that K?_d ? H(F) is determined. Finally, it is shown that if the degree sum of the endvertices of a hamiltonian path in a graph F with at least five vertices is at least |V(F)| + t(t ? 0), then H(F) contains a complete subgraph of order t + 4.