Harmonic analysis on the Pascal graph

In this paper, we completely determine the spectral invariants of an auto-similar planar 3-regular graph. Using the same methods, we study the spectral invariants of a natural compactification of this graph.     

On the power of combinatorial and spectral invariants

We extend the traditional spectral invariants (spectrum and angles) by a stronger polynomial time computable graph invariant based on the angles between projections of standard basis vectors into the eigenspaces (in addition to the usual angles between standard basis vectors and eigenspaces). The exact power of the new invariant is still an open problem. We also define combinatorial invariants based on standard graph isomorphism heuristics and compare their strengths with the spectral invariants. In particular, we show that a simple edge coloring invariant is at least as powerful as all these spectral invariants.     

Approximation of 3-Edge-Coloring of Cubic Graphs

The problem to find a 4-edge-coloring of a 3-regular graph is solvable in polynomial time but an analogous problem for 3-edge-coloring is NP-hard. We study complexity of approximation algorithms for invariants measuring how far is a 3-regular graph from having a 3-edge-coloring. We prove that it is an NP-hard problem to approximate such invariants by a power function with exponent smaller than 1.     

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.     

The normal curvatures of a graph

A set of arithmetical invariants for each vertex of a graph was defined in [1]. In this paper these invariants are expressed by the eigenvalues and eigenvectors of the graph.     

On the reconstruction of graph invariants

The reconstruction conjecture has remained open for simple undirected graphs since it was suggested in 1941 by Kelly and Ulam. In an attempt to prove the conjecture, many graph invariants have been shown to be reconstructible from the vertex-deleted deck, and in particular, some prominent graph polynomials. Among these are the Tutte polynomial, the chromatic polynomial and the characteristic polynomial. We show that the interlace polynomial, the U-polynomial, the universal edge elimination polynomial ξ and the colored versions of the latter two are reconstructible.We also present a method of reconstructing boolean graph invariants, or in other words, proving recognizability of graph properties (of colored or uncolored graphs), using first order logic.     

Milnor invariants for spatial graphs

Link-homotopy has been an active area of research for knot theorists since its introduction by Milnor in the 1950s. We introduce a new equivalence relation on spatial graphs called component-homotopy, which reduces to link-homotopy in the classical case. Unlike previous attempts at generalizing link-homotopy to spatial graphs, our new relation allows analogues of some standard link-homotopy results and invariants.In particular we can define a type of Milnor group for a spatial graph under component-homotopy, and this group determines whether or not the spatial graph is splittable. More surprisingly, we will also show that whether the spatial graph is splittable up to component-homotopy depends only on the link-homotopy class of the links contained within it. Numerical invariants of the relation will also be produced.     

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 multiplicity of abelian covers of splice quotient singularities

From a resolution graph with certain conditions, Neumann and Wahl constructed an equisingular family of surface singularities called splice quotients. For this class some fundamental analytic invariants have been computed from their resolution graph. In this paper we give a method to compute the multiplicity of an abelian covering of a splice quotient from its resolution graph and the Galois group.     

On Kauffman invariants for 6-valent graphs

An explicit way for producing invariants for 6-valent graphs with rigid vertices within the framework of Kauffman's approach to graph invariants is presented. These invariants can be used to detect the chirality of a 6-valent graph with rigid vertices. A relevant example is considered. Bibliography: 19 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 223, 1995, pp. 251–262. Translated by A. M. Nikitin     

Graph isomorphism and equality of simplices

We show that the graph isomorphism problem is equivalent to the problem of recognizing equal simplices in ? ⁿ . This result can lead to new methods in the graph isomorphism problem based on geometrical properties of simplices. In particular, relations between several well-known classes of invariants of graphs and geometrical invariants of simplices are established.     

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.     

Diffusions on graphs, Poisson problems and spectral geometry

We study diffusions, variational principles and associated boundary value problems on directed graphs with natural weightings. We associate to certain subgraphs (domains) a pair of sequences, each of which is invariant under the action of the automorphism group of the underlying graph. We prove that these invariants differ by an explicit combinatorial factor given by Stirling numbers of the first and second kind. We prove that for any domain with a natural weighting, these invariants determine the eigenvalues of the Laplace operator corresponding to eigenvectors with nonzero mean. As a specific example, we investigate the relationship between our invariants and heat content asymptotics, expressing both as special values of an analog of a spectral zeta function.

     

Zero-divisor graphs of nilpotent-free semigroups

We find strong relationships between the zero-divisor graphs of apparently disparate kinds of nilpotent-free semigroups by introducing the notion of an Armendariz map between such semigroups, which preserves many graph-theoretic invariants. We use it to give relationships between the zero-divisor graph of a ring, a polynomial ring, and the annihilating-ideal graph. Then we give relationships between the zero-divisor graphs of certain topological spaces (so-called pearled spaces), prime spectra, maximal spectra, tensor-product semigroups, and the semigroup of ideals under addition, obtaining surprisingly strong structure theorems relating ring-theoretic and topological properties to graph-theoretic invariants of the corresponding graphs.     

The Zagreb coindices of graph operations

Recently introduced Zagreb coindices are a generalization of classical Zagreb indices of chemical graph theory. We explore here their basic mathematical properties and present explicit formulae for these new graph invariants under several graph operations.     

Flag algebras and the stable coefficients of the Jones polynomial

We study the structure of the stable coefficients of the Jones polynomial of an alternating link. We start by identifying the first four stable coefficients with polynomial invariants of a (reduced) Tait graph of the link projection. This leads us to introduce a free polynomial algebra of invariants of graphs whose elements give invariants of alternating links which strictly refine the first four stable coefficients. We conjecture that all stable coefficients are elements of this algebra, and give experimental evidence for the fifth and the sixth stable coefficient. We illustrate our results in tables of all alternating links with at most 10 crossings and all irreducible planar graphs with at most 6 vertices.     

Convexities related to path properties on graphs

A feasible family of paths in a connected graph G is a family that contains at least one path between any pair of vertices in G. Any feasible path family defines a convexity on G. Well-known instances are: the geodesics, the induced paths, and all paths. We propose a more general approach for such ‘path properties’. We survey a number of results from this perspective, and present a number of new results. We focus on the behaviour of such convexities on the Cartesian product of graphs and on the classical convexity invariants, such as the Carathéodory, Helly and Radon numbers in relation with graph invariants, such as the clique number and other graph properties.     

Hypertree width and related hypergraph invariants

We study the notion of hypertree width of hypergraphs. We prove that, up to a constant factor, hypertree width is the same as a number of other hypergraph invariants that resemble graph invariants such as bramble number, branch width, linkedness, and the minimum number of cops required to win Seymour and Thomas’s robber and cops game.     

A hierarchy of submodels of differential equations

We consider a system of differential equations admitting a group of transformations. The Lie algebra of the group generates a hierarchy of submodels. This hierarchy can be chosen so that the solutions to each of submodels are solutions to some other submodel in the same hierarchy. For this we must calculate an optimal system of subalgebras and construct a graph of embedded subalgebras and then calculate the differential invariants and invariant differentiation operators for each subalgebra. The invariants of a superalgebra are functions of the invariants of the algebra. The invariant differentiation operators of a superalgebra are linear combinations of invariant differentiation operators of a subalgebra over the field of invariants of the subalgebra. The comparison of the representations of group solutions gives a relation between the solutions to the models of the superalgebra and the subalgebra. Some examples are given of embedded submodels for the equations of gas dynamics.     

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.