The Peterson recurrence formula for the chromatic discriminant of a graph

The absolute value of the coefficient of q in the chromatic polynomial of a graph G is known as the chromatic discriminant of G and is denoted α(G). There is a well known recurrence formula for α(G) that comes from the deletion-contraction rule for the chromatic polynomial. In this paper we prove another recurrence formula for α(G) that comes from the theory of Kac- Moody Lie algebras. We start with a brief survey on many interesting algebraic and combinatorial interpretations of α(G). We use two of these interpretations (in terms of acyclic orientations and spanning trees) to give two bijective proofs for our recurrence formula of α(G).     

On the reduced signless Laplacian spectrum of a degree maximal graph

For a (simple) graph G, the signless Laplacian of G is the matrix A(G)+D(G), where A(G) is the adjacency matrix and D(G) is the diagonal matrix of vertex degrees of G; the reduced signless Laplacian of G is the matrix Δ(G)+B(G), where B(G) is the reduced adjacency matrix of G and Δ(G) is the diagonal matrix whose diagonal entries are the common degrees for vertices belonging to the same neighborhood equivalence class of G. A graph is said to be (degree) maximal if it is connected and its degree sequence is not majorized by the degree sequence of any other connected graph. For a maximal graph, we obtain a formula for the characteristic polynomial of its reduced signless Laplacian and use the formula to derive a localization result for its reduced signless Laplacian eigenvalues, and to compare the signless Laplacian spectral radii of two well-known maximal graphs. We also obtain a necessary condition for a maximal graph to have maximal signless Laplacian spectral radius among all connected graphs with given numbers of vertices and edges.     

Clique-inserted-graphs and spectral dynamics of clique-inserting

Motivated by studying the spectra of truncated polyhedra, we consider the clique-inserted-graphs. For a regular graph G of degree r>0, the graph obtained by replacing every vertex of G with a complete graph of order r is called the clique-inserted-graph of G, denoted as C(G). We obtain a formula for the characteristic polynomial of C(G) in terms of the characteristic polynomial of G. Furthermore, we analyze the spectral dynamics of iterations of clique-inserting on a regular graph G. For any r-regular graph G with r>2, let S(G) denote the union of the eigenvalue sets of all iterated clique-inserted-graphs of G. We discover that the set of limit points of S(G) is a fractal with the maximum r and the minimum −2, and that the fractal is independent of the structure of the concerned regular graph G as long as the degree r of G is fixed. It follows that for any integer r>2 there exist infinitely many connected r-regular graphs (or, non-regular graphs with r as the maximum degree) with arbitrarily many distinct eigenvalues in an arbitrarily small interval around any given point in the fractal. We also present a formula on the number of spanning trees of any kth iterated clique-inserted-graph and other related results.     

Polynomial addition sets and polynomial digraphs

Let G be a group of order v, and f(x) be a nonzero integral polynomial. A (v, k, f(x))-polynomial addition set in G is a subset D of G with k distinct elements such that f(Σ_d∈Dd) = λΣ_g∈Gg for some integer λ. We discuss some general properties of polynomial addition sets. The relation between polynomial addition sets and polynomial Cayley digraphs is studied and, in particular, some new results on Cayley xⁿ-digraphs and strongly regular Cayley graphs are obtained. Finally, a complete list of polynomial addition sets with certain restrictions on parameters is given.     

The binding number of a graph and its Anderson number

The binding number of a graph G, bind(G), is defined; some examples of its calculation are given, and some upper bounds for it are proved. It is then proved that, if bind(G) ≥ c, then G contains at least $\text{|G|}\text{c}\text{(c + 1)}$ disjoint edges if $\text{0 ≤ c ≤}\text{1}\text{2}$, at least $\text{| G |}\text{(3c ? 2)}\text{3c}\text{?}\text{2(c ? 1)}\text{c}$ disjoint edges if $\text{1 ≤ c ≤}\text{4}\text{3}$, a Hamiltonian circuit if $\text{c ≥}\text{3}\text{2}$, and a circuit of length at least $\text{3(| G | ?1)(c ? 1)}\text{c}$ if $\text{1 < c ≤}\text{3}\text{2}$ and G is not one of two specified exceptional graphs. Each of these results is best possible.The Anderson number of a graph is defined. The Anderson numbers of a few very simple graphs are determined; and some rather weak bounds are obtained, and some conjectures made, on the Anderson numbers of graphs in general.     

Optimal clustering of multipartite graphs

Given a graph G=(X,U), the problem dealt within this paper consists in partitioning X into a disjoint union of cliques by adding or removing a minimum number z(G) of edges (Zahn's problem). While the computation of z(G) is NP-hard in general, we show that its computation can be done in polynomial time when G is bipartite, by relating it to a maximum matching problem. When G is a complete multipartite graph, we give an explicit formula specifying z(G) with respect to some structural features of G. In both cases, we give also the structure of all the optimal clusterings of G.     

A polynomial dual of partitions

Let P(x) = Σ_i=0ⁿa_ixⁱ be a nonnegative integral polynomial. The polynomial P(x) is m-graphical, and a multi-graph G a realization of P(x), provided there exists a multi-graph G containing exactly P(1) points where a_i of these points have degree i for 0≤i≤n. For multigraphs G, H having polynomials P(x), Q(x) and number-theoretic partitions (degree sequences) π, ?, the usual product P(x)Q(x) is shown to be the polynomial of the Cartesian product G × H, thus inducing a natural product π? which extends that of juxtaposing integral multiple copies of ?. Skeletal results are given on synthesizing a multi-graph G via a natural Cartesian product G₁ × … × G_k having the same polynomial (partition) as G. Other results include an elementary sufficient condition for arbitrary nonnegative integral polynomials to be graphical.     

Tutte sets in graphs II: The complexity of finding maximum Tutte sets

A well-known formula of Tutte and Berge expresses the size of a maximum matching in a graph G in terms of what is usually called the deficiency. A subset X of V(G) for which this deficiency is attained is called a Tutte set of G. While much is known about maximum matchings, less is known about the structure of Tutte sets. We explored the structural aspects of Tutte sets in another paper. Here, we consider the algorithmic complexity of finding Tutte sets in a graph. We first give two polynomial algorithms for finding a maximal Tutte set. We then consider the complexity of finding a maximum Tutte set, and show it is NP-hard for general graphs, as well as for several interesting restricted classes such as planar graphs. By contrast, we show we can find maximum Tutte sets in polynomial time for graphs of level 0 or 1, elementary graphs, and 1-tough graphs.     

Distorsion des distances dans les groupes de Lie nilpotents

Let G be a connected nilpotent Lie group and H a connected subgroup of G. We give an explicit formula for the distance to the origin with the exponential coordinates of the second kind of g∈G. Using this fact, we prove that the distance to the origin of any element in H is bounded by a polynomial function of the distance to the origin in the group G. The degree of the polynomial is the nilpotency rank of the group G.     

Groupoids and Faà di Bruno formulae for Green functions in bialgebras of trees

We prove a Faà di Bruno formula for the Green function in the bialgebra of P-trees, for any polynomial endofunctor P. The formula appears as relative homotopy cardinality of an equivalence of groupoids.     

On the structure of finite coverings of compact connected groups

Finite-sheeted covering mappings onto compact connected groups are studied. We show that for a covering mapping from a connected Hausdorff topological space onto a compact (in general, non-abelian) group there exists a topological group structure on the covering space such that the mapping becomes a homomorphism of groups. To prove this fact we construct an inverse system of covering mappings onto Lie groups which approximates the given covering mapping. As an application, it is shown that a covering mapping onto a compact connected abelian group G must be a homeomorphism provided that the character group of G admits division by degree of the mapping. We also get a criterion for triviality of coverings in terms of means and prove that each finite covering of G is equivalent to a polynomial covering.     

Finite 2-groups with exactly one nonmetacyclic maximal subgroup

We determine here the structure of the title groups. All such groups G will be given in terms of generators and relations, and many important subgroups of these groups will be described. Let d(G) be the minimal number of generators of G. We have here d(G) ≤ 3 and if d(G) = 3, then G′ is elementary abelian of order at most 4. Suppose d(G) = 2. Then G′ is abelian of rank ≤ 2 and G/G′ is abelian of type (2, 2^m), m ≥ 2. If G′ has no cyclic subgroup of index 2, then m = 2. If G′ is noncyclic and G/Φ(G ₀) has no normal elementary abelian subgroup of order 8, then G′ has a cyclic subgroup of index 2 and m = 2. But the most important result is that for all such groups (with d(G) = 2) we have G = AB, for suitable cyclic subgroups A and B. Conversely, if G = AB is a finite nonmetacyclic 2-group, where A and B are cyclic, then G has exactly one nonmetacyclic maximal subgroup. Hence, in this paper the nonmetacyclic 2-groups which are products of two cyclic subgroups are completely determined. This solves a long-standing problem studied from 1953 to 1956 by B. Huppert, N. Itô and A. Ohara. Note that if G = AB is a finite p-group, p > 2, where A and B are cyclic, then G is necessarily metacyclic (Huppert [4]). Hence, we have solved here problem Nr. 776 from Berkovich [1].     

On the 2-factor index of a graph

The 2-factor index of a graph G, denoted by f(G), is the smallest integer m such that the m-iterated line graph L^m(G) of G contains a 2-factor. In this paper, we provide a formula for f(G), and point out that there is a polynomial time algorithm to determine f(G).     

Metric properties on Lie groups of polynomial volume growth

It is well known that we have an algebraic characterization of connected Lie groups of polynomial volume growth: a Lie group G has polynomial volume growth if and only if it is of type R. In this paper, we shall give a geometric characterization of connected Lie groups of polynomial volume growth in terms of the distance distortion of the subgroups. More precisely, we prove that a connected Lie group G has polynomial volume growth if and only if every closed subgroup has a polynomial distortion in G.     

Relative colorings of graphs

In this paper, the notion of relative chromatic number χ(G, H) for a pair of graphs G, H, with H a full subgraph of G, is formulated; namely, χ(G, H) is the minimum number of new colors needed to extend any coloring of H to a coloring of G. It is shown that the four color conjecture (4CC) is equivalent to the conjecture (R4CC) that χ(G, H) ≤ 4 for any (possibly empty) full subgraph H of a planar graph G and also to the conjecture (CR3CC) that χ(G, H) ≤ 3 if H is a connected and nonempty full subgraph of planar G. Finally, relative coloring theorems on surfaces other than the plane or sphere are proved.     

Polynomial diffeomorphisms of C2: V. critical points and Lyapunov exponents

There is an invariant measure μ, which is the pluri-complex version of the harmonic measure of the Julia set for polynomial maps of C.In this paper we give an integral formula for the Lyapunov exponents of a polynomial automorphism with respect to μ, analogous to the Brolin-Manning formula polynomial maps of C.Our formula relates the Lyapunov exponents to the value of a Green function at a type of critical point which we define in this paper. We show that these the critical points have a natural dynamical interpretation.     

The Hilbert Series of the Face Ring of a Flag Complex

 It is shown that the Hilbert series of the face ring of a clique complex (equivalently, flag complex) of a graph G is, up to a factor, just a specialization of , the subgraph polynomial of the complement of G. We also find a simple relationship between the size of a minimum vertex cover of a graph G and its subgraph polynomial. This yields a formula for the h-vector of the flag complex in terms of those two invariants of . Some computational issues are addressed and a recursive formula for the Hilbert series is given based on an algorithm of Bayer and Stillman. Received: December 10, 1999 Acknowledgments. I would like to thank Rick Wilson and the mathematics department of the California Institute of Technology for their kind hospitality, and Richard Stanley for pointing out an error in an earlier draft.     

Some panconnected and pancyclic properties of graphs with a local ore-type condition

Asratian and Khachatrian proved that a connected graphG of order at least 3 is hamiltonian ifd(u) + d(v) ≥ |N(u) ∪ N(v) ∪ N(w)| for any pathuwv withuv ? E(G), whereN(x) is the neighborhood of a vertexx. We prove that a graphG with this condition, which is not complete bipartite, has the following properties:

1. For each pair of verticesx, y with distanced(x, y) ≥ 3 and for each integern, d(x, y) ≤ n ≤ |V(G)| ? 1, there is anx ? y path of lengthn.
2. For each edgee which does not lie on a triangle and for eachn, 4 ≤ n ≤ |V(G)|, there is a cycle of lengthn containinge.
3. Each vertex ofG lies on a cycle of every length from 4 to |V(G)|.

This implies thatG is vertex pancyclic if and only if each vertex ofG lies on a triangle.     

Edge covering coloring of nearly bipartite graphs

LetG be a simple graph with vertex setV(G) and edge setE(G). A subsetS ofE(G) is called an edge cover ofG if the subgraph induced byS is a spanning subgraph ofG. The maximum number of edge covers which form a partition ofE(G) is called edge covering chromatic number ofG, denoted by χ′_c(G). It known that for any graphG with minimum degreeδ,δ -1 ≤χ′_c(G) ≤δ. If χ′_c(G) =δ, thenG is called a graph of CI class, otherwiseG is called a graph of CII class. It is easy to prove that the problem of deciding whether a given graph is of CI class or CII class is NP-complete. In this paper, we consider the classification of nearly bipartite graph and give some sufficient conditions for a nearly bipartite graph to be of CI class.     

On n-Hamiltonian line graphs

With each nonempty graph G one can associate a graph L(G), called the line graph of G, with the property that there exists a one-to-one correspondence between E(G) and V(L(G)) such that two vertices of L(G) are adjacent if and only if the corresponding edges of G are adjacent. For integers m ≥ 2, the mth iterated line graph L^m(G) of G is defined to be L(L^m-1(G)). A graph G of order p ≥ 3 is n-Hamiltonian, 0 ≤ n ≤ p ? 3, if the removal of any k vertices, 0 ≤ k ≤ n, results in a Hamiltonian graph. It is shown that if G is a connected graph with δ(G) ≥ 3, where δ(G) denotes the minimum degree of G, then L²(G) is (δ(G) ? 3)-Hamiltonian. Furthermore, if G is 2-connected and δ(G) ≥ 4, then L²(G) is (2δ(G) ? 4)-Hamiltonian. For a connected graph G which is neither a path, a cycle, nor the graph K(1, 3) and for any positive integer n, the existence of an integer k such that L^m(G) is n-Hamiltonian for every m ≥ k is exhibited. Then, for the special case n = 1, bounds on (and, in some cases, the exact value of) the smallest such integer k are determined for various classes of graphs.