 Забыли?

?

149

код для вставкиСкачать
```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 .
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).
 F. Lazebnik, New upper bounds for the greatest number of proper colorings of a
(v,e)-graph, J. Graph Theory 14 (1990), 25-29.
 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.
 W. T. Tutte, A ring in graph theory, Proc. Cambridge Phil. Soc. 43 (1947), 26-40.