On Graph Invariants Satisfying the Deletion-Contraction Formula* Klaus Dohmen HUMBOLDT-UNIVERSITAT ZU BERLIN INSTITUT FUR INFORMATIK UNTER DEN LINDEN 6 10099 BERLIN, GERMANY ABSTRACT As a generalization of chromatic polynomials, this paper deals with real-valued map- + on the class of graphs satisfying +(GI) = +(Gz) for all pairs GI, GZ of pings isomorphic graphs and +(G) = +(G - e) - rC/(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. 0 1996 John Wiley & Sons, Inc. 1. INTRODUCTION In this paper we consider finite undirected graphs without loops or multiple edges. For such a graph G, n(G) resp. m(G) denotes the number of vertices resp. edges of G. If e = uw is an edge of G, then G - e resp. G / e denotes the graph obtained from G by deleting e resp. contracting e and then, in the resulting multigraph, replacing each class of parallel edges by a single edge. Thereby, the vertices of G - e are precisely the vertices of G, while the edges of G - e are those of G except e . The vertex-set of G / e consists of the vertices of G other than u or w and one new vertex 2. If x and y are two vertices of G / e neither of which is the new vertex 2, then x and y are joined by an edge of G / e if and only if they are joined by an edge of G. In addition, x and are joined by an edge of G / e if and only if x and u or x and w are joined by an edge of G. Note that the definition of G / e is non standard. e *This paper is part of the author’s doctoral dissertation written at the University of Dusseldorf under the supervision of Professor Dr. Egbert Harzheim. Journal of Graph Theory, Vol. 21. No. 3, 311-316 (1996) 0 1996 John Wiley & Sons, Inc. CCC 0364-9024/96/030311-06 312 JOURNAL OF GRAPH THEORY In this context, a graph invariant is a real-valued mapping $ on the class of graphs such that $(GI) = $(G2) holds for all pairs G I , G2 of isomorphic graphs. $ will be said to satisfy the deletion-contractionfonnufa,if +(G) = $(G - e ) - + ( G / e ) is valid for all graphs G and all edges e of G. Our purpose is to investigate the set W of graph invariants satisfying the deletion-contraction formula. Several authors (e.g., Tutte [ 5 ] ) considered similar concepts in graph theory (and also in matroid theory). The main distinction to the present concept arises from different meanings being attached to G / e . u~(G)A”(~ denote ) - ~ the chromatic polynomial of G. By the deletionLet PG(A) = contraction formula for chromatic polynomials (see e.g., [4, Thm. 2.6]),PG(A) = Pc-,(A) Pc/,(A) for all graphs G and all edges e of G. Hence all functions G P c ( A ) (A E N) belong to T.More generally each derivative G H Pg)(() ( k E NO,6 E R) is in W.The same holds for G I-+ Zc(A, C ) (A E N,C C (1,. .. ,A}), where Zc(h,C) denotes the number of proper A-colorings f of G satisfying f-’(C> # 0. Obviously, Zc(A,C) = PG(A) - P G ( A - ICl), where ICl stands for the cardinality of C. 2. BASIC PROPERTIES Here and subsequently, Ln denotes the edgeless graph on n vertices. Proposition 1. For all graphs G and all $ E the following identity holds: Proof. We prove the proposition by induction on the number of edges. If G has no edges, then PG(A) = An@), which entails ao(G) = 1 and ak(G) = 0 for k = 1, . .., n(G). Since G is isomorphic to Ln(c),we have $(G) = $(Ln(c)). Hence the theorem holds for graphs without edges. Now let e be an edge of G . By the induction hypothesis, Since $ satisfies the deletion-contraction formula we conclude that By PG(A) = Pc-,(A) - Pcle(A) and a comparison of the coefficients, we obtain Now the proposition immediately follows from (l), (2), and ao(G) = ao(G - e ) = 1. I GRAPH INVARIANTS AND DELETION-CONTRACTION 31 3 Corollary 1. Let G be a graph having at least one vertex, and let $ E W be multiplicative, that is I)(Ln+,J = $(Ln)$(L,) for all n, m E N. Then I)(G) = P G ( $ ( L ~ ) ) . Proof. Since G has at least one vertex, an(c)(G)= 0. From the condition on 1+4 we deduce I)(Ln)= $(Ll)' for all n E N. Hence the corollary is implied by Proposition 1. I In some sense the following proposition is the counterpart of the preceding one: Proposition 2. Let 3 be any real-valued mapping on L := {LO,L1,. . .}, and define $ ( G ) := ak(G)@(L,(G)-k)for all graphs G . Then E and $ 1 ~= ~~f~ +. w Proof. Obviously $JL: = I). Since any two isomorphic graphs G I , G2 have the same chromatic polynomial, we find $(GI) = $(Gz) by the definition of $. Now let G be a graph and e an edge of G. Again by the definition of we have the equations 4 x x n(G-e) $(G - e ) = n(G) ak(G - e)I)(Ln(G-e)-k) = k=O n(G/e) & ( G / e )= 1ak(G - e ) $ ( L n ( G ) - k ) , k=O k=O x n(G) ak(G/e)@(Ln(G/e)-k)= ak-1 ( G / e ) I ) ( L n ( G ) - k ) . k= 1 Combining these with (2) we obtain &(G) = $(G - e> - $ ( G / e ) . Hence $ E T. 1 Theorem 1. With the natural definition of addition and scalar multiplication, forms a real vector space, which is isomorphic to R" = { ( X I , x 2 , . . .)lxn E R, n E N}. Moreover, the set {G * P G ( ( ) ~ (E R} is a linearly independent subset of W. Proof. The first statement is obvious. For the second, it is easy to verify that f : W - R", f($) := ($(Lo),$(Ll),...) is a homomorphism. Proposition 1 states that f is one-to-one while Proposition 2 implies that f is surjective. Hence T and R" are isomorphic. For the (', t 2 ,. ..)I( E R} is a linearly independent last statement it suffices to prove that E := {(to, subset of R". By Vandermonde's well-known formula, det((~);,j=o,...,= flosisjsn((, - 5;) for all n E N and all (0, . . . , (,, E R.Therefore, E is linearly independent. I Note that {C * P G ( ( ) ~ (E R} does not span T.Otherwise E would span R", and a;(! for all k E N. Hence there would exist ( Y I , . .. , as,51, . .. , tssuch that exp(k2) = exp(k2) = 0 ( x k )( k a),where x := max{l(l I,. .. ,l(sl}. But this is false. - Proposition 3. Let rC, E W be such that {$(Ln)ln E NO}is a linearly independent subset of R, where R is considered as a rational vector space. Then two graphs GI, Gz have the same chromatic polynomial if and only if $(GI) = $(G*). Proof. By proposition 1, $(GI) = $(G2) holds for all graphs GI, G2 having the same chromatic polynomial. On the contrary, assume $(GI) = I)(G2) where GI resp. G2 has nl resp. n2 vertices, n1 5 n2. Application of Proposition 1 gives Since {$(LO),. . . ,$(LnZ)}is linearly independent (over the rationals), we obtain ak(G1) = a k f n z - n l ( G 2 ) ak(G2) = 0 (k = o,...,nl) ( k = 0, ...,n2 - n1 - 1) (3) (4) 314 JOURNAL OF GRAPH THEORY From ao(G2) = 1, nl 5 n2 and (4)we deduce n l = n2. Now by (3), P G , ( A ) = PG,(A). I 3. LOWER BOUNDS AND UPPER BOUNDS Obviously, P c ( A ) and Z G ( A , C ) are non-negative for all graphs G, all A E N and all C C { 1,. . . ,A}. This leads to the following definition: A mapping Cc/ on the class of graphs is called nowhere negative ($ 2 0 for short), if there is no graph G satisfying $(G) < 0. Proposition 4. Let 9 E and $(G) 2 0 for all complete graphs G. Then 9 2 0. Proof. Assume $ 2 0 while $(G) 2 0 for all complete graphs G. Under this assumption, the set N consisting of all graphs G satisfying $ ( G ) < 0 is non-empty. Define N ‘ := {C E M J n ( G )5 n ( H ) for all H E M } , 32”:= {G E N ’ l m ( G ) 2 m ( H ) for all H E M’}. Clearly, N ” # 0. Choose G E N ” . Since G E N , G is not complete. Let G + e be obtained from G by adjoining a new edge e . It follows that G + e @ 3 f and (G + e ) / e @ 32,that is $(G + e ) 2 0 and $((G + e ) / e ) I0. Hence $(G) = $(G + e ) + $(G e ) / e ) 2 0, being in contradiction with G E ?d. I For any graph G, let g(G) denote the girth of G, where g ( G ) = + w if G is cycle-free. + Theorem 2. Let G be a graph having at least one edge, and let IC, E and satisfy $(LO) 5 $(L1). Then we have the following estimates: be nowhere negative Proof. If G has only one edge, say e , then G - e resp. G / e is isomorphic to L,(G) resp. Hence $(GI = $(G - e ) - @ ( G / e )= $ ( L n ( G ) ) - $(L,,(G)-I),and the theorem holds for graphs with one edge. Now we consider four cases: q = 0, q = 1, q = 2, q 1 3. In the first three cases we proceed by induction on the number of edges. Case q = 0. By the preceding remark we may assume that G is a graph with at least two edges and the induction hypothesis is true. Let e be an edge of G. Since $ is nowhere negative, we find $(G) = $(G - e ) - $ ( G / e ) 5 $(G - e ) . Applying the induction hypothesis to G - e we obtain $(G - e ) 5 $ ( L n ( G ) ) - $(Ln(c)-l).Hence the estimate holds when q = 0. Case q = 1. Again, let G be a graph having more than one edge and assume the estimate holds for graphs having less edges when q = 1. Applying the induction hypothesis to G - e and the estimate of the preceding case to G / e we obtain $(G - e ) 2 $(L,,(,)) ( m ( G ) - ~ ) $ & I ( G ) - I ) + ( m ( G )- 2)$(Ln(c)-2)resp. $ ( G / e ) 5 $(Ln(c)-i) - $ ( L n ( G ) - 2 ) . Subtraction of the second inequality from the first one leads to the desired result. Case q = 2. Let G have at least two edges and the statement be true for smaller graphs. Application of the induction hypothesis and the preceding inequality yields Ln(G)-I. GRAPH INVARIANTS AND DELETION-CONTRACTION 315 where S denotes the number of triangles of G in which e occurs. Obviously, m(G) 1 2 entails n(G) 2 3. When n(G) = 3, we deduce $ ( L , ( G ) - ~2) +(Ln(,3-3)from the assumption $ ( L l ) 1 $(LO).Otherwise we adjoin a new edge f to L"(G)-z and conclude # ( L , ( G ) - ~1 ) +((L,(c)-z + f)/f) = +(L"(G)-~). Together with (6) we obtain $ ( G / e ) 2 #L(G)-I) ( m ( G) - 1)$(Ln(~)-2)+ (m(G)- 2)1)(L,,(~)-3).Combining this with ( 5 ) gives the estimate in question. Case q 2 3. This case is proved by induction on q + m(G). By the remark at the beginning of the proof we may assume m(G) -1 2. Since q 1 3, G has no triangles. Hence m ( G / e ) = m(G) - 1 for each edge e of G. For even q, the induction hypothesis gives Likewise for odd q. Combining the last two inequalities we finally finish the proof. I The condition $(LO)5 $ ( L I ) cannot be omitted: Set #(G) := PG(O) for all graphs G. Then $(LO) > $&), and $ is nowhere negative. For G = K3 and q = 2 Theorem 2 yields +(K3) 5 $(L3) - 3+(&) + ~ + ( L I-) $(LO),that is 0 5 -1. Corollary 2. Let G be a graph with at least one edge and A E N. Then Proof. Let #(G) := PG(/\).Thus the corollary follows from Theorem 2. 8 Dropping T( m ( ~ ) - l ) A " ( c ) - q -we ' , obtain a weaker result of the present author [l]. Corollary 3. Suppose that G has at least one edge and A E N. Then we have Proof. The corollary follows from the preceding one by q = 1 resp. q = 2. I The second inequality of the preceding corollary improves a result of Lazebnik [3]. Lazebnik's original estimate can easily be obtained by dropping -( m(5))-1 ACKNOWLEDGMENT The author gratefully acknowledges the many stimulating conversations and helpful suggestions of Professor Dr. Egbert Harzheim during the preparation of the paper. 316 JOURNAL OF GRAPH THEORY References [ 11 K. Dohmen, Lower bounds and upper bounds for chromatic polynomials, J. Graph Theory 17 (1993), 75-80. [21 K. Dohmen, Chromatische Polynome von Graphen und Hypergraphen. Dissertation. Heinrich-Heine-Universitat Dusseldorf ( 1993). [3] F. Lazebnik, New upper bounds for the greatest number of proper colorings of a (v,e)-graph, J. Graph Theory 14 (1990), 25-29. [4] R. C. Read and W. T. Tutte, Chromatic polynomials in: Selected Topics in Graph Theory I11 (eds. L. W. Beineke & R. J. Wilson), Academic Press, New York (1988), 15-42. [5] W. T. Tutte, A ring in graph theory, Proc. Cambridge Phil. Soc. 43 (1947), 26-40. Received March 7, 1994

1/--страниц