Large deviation on a covering graph with group of polynomial growth

We discuss a large deviation principle of a periodic random walk on a covering graph with its transformation group of polynomial volume growth in view of geometry. As we shall observe, the behavior of a random walk at infinity is closely related to the Gromov?CHausdorff limit of an infinite graph and in the case where the graph admits an action of a group of polynomial volume growth, the Carnot-Carathéodory metric shows up in its limit space.     

Feasible Graphs and Colorings

The problem of when a recursive graph has a recursive k-coloring has been extensively studied by Bean, Schmerl, Kierstead, Remmel, and others. In this paper, we study the polynomial time analogue of that problem. We develop a number of negative and positive results about colorings of polynomial time graphs. For example, we show that for any recursive graph G and for any k, there is a polynomial time graph G′ whose vertex set is {0,1}* such that there is an effective degree preserving correspondence between the set of k-colorings of G and the set of k-colorings of G′ and hence there are many examples of k-colorable polynomial time graphs with no recursive k-colorings. Moreover, even though every connected 2-colorable recursive graph is recursively 2-colorable, there are connected 2-colorable polynomial time graphs which have no primitive recursive 2-coloring. We also give some sufficient conditions which will guarantee that a polynomial time graph has a polynomial time or exponential time coloring.     

On Graphs Determined by Their Tutte Polynomials

We say that a graph G is T-unique if any other graph having the same Tutte polynomial as G is necessarily isomorphic to G. In this paper we show that several well-known families of graphs are T-unique: wheels, squares of cycles, complete multipartite graphs, ladders, Möbius ladders, and hypercubes. In order to prove these results, we show that several parameters of a graph, like the number of cycles of length 3, 4 and 5, and the edge-connectivity are determined by its Tutte polynomial.Research partially supported by projects BFM2001-2340 and by CUR Gen. Cat. 1999SGR00356Final version received: January 10, 2003     

Application of computer algebra to Jones polynomials

In this paper we apply computer algebra (Maple) techniques to calculate Jones polynomial of graphs of K(2,q)-Torus knots. For this purpose, a computer program was developed. When a positive integer q is given, the program calculate Jones polynomial of graph of K(2,q)-Torus knots.     

On the complexity of deciding whether the distinguishing chromatic number of a graph is at most two

In an article Cheng (2009) [3] published recently in this journal, it was shown that when k≥3, the problem of deciding whether the distinguishing chromatic number of a graph is at most k is NP-hard. We consider the problem when k=2. In regards to the issue of solvability in polynomial time, we show that the problem is at least as hard as graph automorphism, but no harder than graph isomorphism.     

Some results on the signless Laplacians of graphs

In this paper we give two results concerning the signless Laplacian spectra of simple graphs. Firstly, we give a combinatorial expression for the fourth coefficient of the (signless Laplacian) characteristic polynomial of a graph. Secondly, we consider limit points for the (signless Laplacian) eigenvalues and we prove that each non-negative real number is a limit point for (signless Laplacian) eigenvalue of graphs.     

Density of the circular chromatic numbers of series‐parallel graphs

In this paper we show that every simple cubic graph on n vertices has a set of at least ? n/4 ? disjoint 2‐edge paths and that this bound is sharp. Our proof provides a polynomial time algorithm for finding such a set in a simple cubic graph. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 57–79, 2003     

On the theory of the matching polynomial

In this paper we report on the properties of the matching polynomial α(G) of a graph G. We present a number of recursion formulas for α(G), from which it follows that many families of orthogonal polynomials arise as matching polynomials of suitable families of graphs. We consider the relation between the matching and characteristic polynomials of a graph. Finally, we consider results which provide information on the zeros of α(G).     

Unsigned State Models for the Jones Polynomial

It is a well-known and fundamental result that the Jones polynomial can be expressed as Potts and vertex partition functions of signed plane graphs. Here we consider constructions of the Jones polynomial as state models of unsigned graphs and show that the Jones polynomial of any link can be expressed as a vertex model of an unsigned embedded graph. In the process of deriving this result, we show that for every diagram of a link in S ³ there exists a diagram of an alternating link in a thickened surface (and an alternating virtual link) with the same Kauffman bracket. We also recover two recent results in the literature relating to the Jones and Bollobás-Riordan polynomials and show they arise from two different interpretations of the same embedded graph.     

Characteristic polynomials of complement of graph bundles and their applications

We study the structure of the complement of an F-bundle over a graph G when it can be expressed as an F-bundle over another graph G. In particular, we compute the characteristie polynomial of the complement of an F-bundle when its voltages lie in and abelian subgroup Г of Aut(F) which acts freely and transitively on the vertices of the fiber F Some applications to regular embeddings of graph bundles into Euclidean spaces are also discussed     

Integer Roots Chromatic Polynomials of Non-Chordal Graphs and the Prouhet-Tarry-Escott Problem

In this paper, we give an affirmative answer to a question of Dmitriev concerning the existence of a non-chordal graph with a chordless cycle of order n whose chromatic polynomial has integer roots for a few values of n, extending prior work of Dong et al. Received: April, 2003     

An introduction to the k-defect polynomials

The 0-defect polynomial of a graph is just the chromatic polynomial. This polynomial has been widely studied in the literature. Yet little is known about the properties of k-defect polynomials of graphs in general, when 0 < k ≤ |E(G)|. In this survey we give some properties of k-defect polynomials, in particular we highlight the properties of chromatic polynomials which also apply to k-defect polynomials. We discuss further research which can be done on the k-defect polynomials.     

Relaxations of vertex packing

A polynomially computable upper bound for the weighted independence number of a graph is studied. This gives rise to a convex body containing the vertex packing polytope of the graph. This body is a polytope if and only if the graph is perfect. As an application of these notions, we show that the maximum weight independent set of an h-perfect graph can be found in polynomial time.     

The Hilbert Series of the Clique Complex

For a graph G, we show a theorem that establishes a correspondence between the fine Hilbert series of the Stanley-Reisner ring of the clique complex for the complementary graph of G and the fine subgraph polynomial of G. We obtain from this theorem some corollaries regarding the independent set complex and the matching complex.     

Algorithms for coloring semi-random graphs

The graph coloring problem is to color a given graph with the minimum number of colors. This problem is known to be NP-hard even if we are only aiming at approximate solutions. On the other hand, the best known approximation algorithms require n^δ (δ>0) colors even for bounded chromatic (k-colorable for fixed k) n-vertex graphs. The situation changes dramatically if we look at the average performance of an algorithm rather than its worst case performance. A k-colorable graph drawn from certain classes of distributions can be k-colored almost surely in polynomial time. It is also possible to k-color such random graphs in polynomial average time. In this paper, we present polynomial time algorithms for k-coloring graphs drawn from the semirandom model. In this model, the graph is supplied by an adversary each of whose decisions regarding inclusion of edges is reversed with some probability p. In terms of randomness, this model lies between the worst case model and the usual random model where each edge is chosen with equal probability. We present polynomial time algorithms of two different types. The first type of algorithms always run in polynomial time and succeed almost surely. Blum and Spencer [J. Algorithms, 19 , 204–234 (1995)] have also obtained independently such algorithms, but our results are based on different proof techniques which are interesting in their own right. The second type of algorithms always succeed and have polynomial running time on the average. Such algorithms are more useful and more difficult to obtain than the first type of algorithms. Our algorithms work for semirandom graphs drawn from a wide range of distributions and work as long as p≥n^−α(k)+ϵ where α(k)=(2k)/((k−1)(k+2)) and ϵ is a positive constant. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13, 125–158 (1998)     

Robust Algorithms for the Stable Set Problem

The stable set problem is to find in a simple graph a maximum subset of pairwise non-adjacent vertices. The problem is known to be NP-hard in general and can be solved in polynomial time on some special classes, like cographs or claw-free graphs. Usually, efficient algorithms assume membership of a given graph in a special class. Robust algorithms apply to any graph G and either solve the problem for G or find in it special forbidden configurations. In the present paper we describe several efficient robust algorithms, extending some known results.     

Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms

A minimal blocker in a bipartite graph G is a minimal set of edges the removal of which leaves no perfect matching in G. We give an explicit characterization of the minimal blockers of a bipartite graph G. This result allows us to obtain a polynomial delay algorithm for finding all minimal blockers of a given bipartite graph. Equivalently, we obtain a polynomial delay algorithm for listing the anti‐vertices of the perfect matching polytope of G. We also provide generation algorithms for other related problems, including d‐factors in bipartite graphs, and perfect 2‐matchings in general graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 209–232, 2006     

Cutpoints and the chromatic polynomial

We prove that the multiplicity of the root 1 in the chromatic polynomial of a simple graph G is equal to the number of nontrivial blocks in G. In particular, a connected simple graph G has a cutpoint if and only if its chromatic polynomial is divisible by (λ – 1)². We apply this theorem to obtain some chromatic equivalence and uniqueness results.     

Vertex fusion under distance constraints

In this paper, we analyze parameter improvement under vertex fusion in a graph G. This is a setting in which a new graph G^′ is obtained after identifying a subset of vertices of G in a single vertex. We are interested in distance parameters, in particular diameter, radius and eccentricity of a vertex v. We show that the corresponding problem is NP-Complete for the three parameters. We also find graph classes in which the problem can be solved in polynomial time.     

On the Commuting Graph of Dihedral Group

Let Γ be a non-abelian group and Ω ? Γ. We define the commuting graph G = 𝒞(Γ, Ω) with vertex set Ω and two distinct elements of Ω are joined by an edge when they commute in Γ. In this article, among some properties of commuting graphs, we investigate distant properties as well as detour distant properties of commuting graph on D_2n. We also study the metric dimension of commuting graph on D_2n and compute its resolving polynomial.