General Editor Peter L. HAMMER, University of Waterloo, Ont., Canada Advisory Editors C. BERGE, Universite de Paris, France M.A. HARRISON, University of California, Berkeley, CA, U.S.A. V. KLEE, Universityof Washington, Seattle, WA, U S A . J.H. VAN LINT, California Institute of Technology, Pasadena, CA, U.S.A. G.-C. ROTA, Massachusetts Institute of Technology, Cambridge, MA, U.S.A. NORTH-HOLLAND PUBLISHING COMPANY -AMSTERDAM NEW YORK OXFORD
NORTH-HOLLAND MATHEMATICS STUDIES 62 Annals of Discrete Mathematics(13) General Editor: Peter L. Hammer University of Waterloo, Ont., Canada Graph Theory Proceedingsof the Conference on Graph Theory, Cambridge Editor: BelaBOLLOBAS Department of Pure Mathematics and Mathematical Statistics University of Cambridge Cambridge CB2 lSB, England 1982 NORTH-HOLLAND PUBLISHING COMPANY -AMSTERDAM NEW YORK OXFORD
North-Holland Publishing Company, 1982 AII rights reserved. N opart of thispublication may be reproduced, stored inaretrievalsystem ortransmitted,in any otherformorby any means, electronic, mechanical,photocopying, recording orotherwise, without thepriorpermissionof the copyright owner. ISBN: 0 444 86449 0 Publishers: NORTH-HOLLAND PUBLISHING COMPANY AMSTERDAM NEW YORK OXFORD Sole distributorsforthe U.S.A.and Canada: ELSEVIER SCIENCE PUBLISHING COMPANY, INC. 52 VANDERBILT AVENUE, NEW YORK, NY 10017 Library of Congress Calaloging in Publication Data Main entry under title: Graph theory. (Annals of discrete mathematics ; U) (North- Holland mathematics studies ; 62) Papers presented a t the Cambridge Graph Theory Conference, held a t Trinity College 11-l.3 Mar. p81. 1. Graph theory--Congresses. I. Bollob&, Bela. 11. Cambrid e Gra h Theory Conference (181 : Trinity Colfege, eniversity of Cambridge? 111. Se- r i e s . I V . Series: North-Holland mathematics studies ; 62. QA166.G718 1982 5ll'.5 82-8098 ISBN 0-444-86449-0 AACF2 - PRINTED IN THE NETHERLANDS
FOREWORD The Cambridge Graph Theory Conference,held at Trinity College from 11to 13 March 1981, brought together top ranking workers from diverse areas of the subject. The papers presented were by invitationonly. Thisvolume containsmost of the contniutions, suitably refereed and revised. For many years now, graph theory has been developing at a great pace and in many directions. In order to emphasize the variety of questionsand topreserve the freshnessof research, the theme of the meetingwas not restricted. Consequent- ly, the papers in this volume deal with many aspects of graph theory, including colouring, connectivity, cycles, Ramsey theory, random graphs, flows, simplicial decompositions and directed graphs. A number of other papers are concernedwith related areas,including hypergraphs, designs, algorithms, games and social models. Thiswealth of topics should enhance the attractivenessof the volume. It is a pleasure to thank Mrs. J.E.Scutt and Mrs. B. Sharples for retyping most of the papers so quickly and carefully, and to acknowledge the financial assistance of the Department of Pure Mathematics and Mathematical Statistics of the University of Cambridge. Above all, warm thanks are due to the particip- ants for the exciting lectures and lively discussions at the meeting and for the many excellent papers in thisvolume. €#la Bollobis 25th February 1982 Baton Rouge
TABLEOF CONTENTS Foreword V J.AKIYAMA,K.AND0 and H. MXZUNO,Characterizationsand classificationsof bioonnectedgraphs 1 R.A. BAN, Line graphs and their chromatic polynomials 15 J.C. BERMOND, C. DELORME and G. FARHI, Large graphs with given degree and diameter 111 23 B. BOLLOBh, Distinguishingvertices of random graphs 33 B. BOLLOBh and F. HARARY, Thetrail numberof a graph 51 J.H. CONWAY and M.J.T. GUY, Message graphs 61 D.E. DAYKIN and P.FRANKL, Sets of graph colourings 65 P.DUCHET and H. MEYNIEL, On Hadwiger’s number and the stability number 71 H.DE FRAYSSEIXand P.ROSENSTIEHL,A depth-first-search characterizationof planarity 75 J.L. GROSS, Graph-theoreticalmodelof social organization 81 R. I-I&XKVIST, Odd cyclesof specifiedlengthin non-bipartite graphs 89 R. HALIN, Simplicialdecompositions: Some new aspects and applications 101 F. HARARY, Achievement and avoidance games for graphs 111
viii Cbnrenrs AJ.W.HILTON, Embedding incomplete latm rectangles 121 AJ.W.HILTONand C.A. RODGER, Edgecolouringregular bipartite graphs 139 AJ. W S F I E U ) and DJ.A. WELSH, Some colouring problems andtheir complexity 159 A. PAPAIOANNOU,A Hamilbniangame 171 J. SHEEHAN,Finite Ramsey theory and stronglyregular graphs 179 R. TINDELL,The connectivitiesof agraph anditscomplement 191
Annalsof Discrete Mathematics 13 (1982) 1-14 0North-Holland Publishing Company CHARACTERIZATIONSAND CLASSIFICATIONS OF BICONNECTED GRAPHS J. AKIYAMA, K. AND0 and H. MIZUNO Nippon Ika University, Kawasaki, Japan and University of Electrocommunications, Tokyo, Japan Dedicated t o Frank Harary f o r h i s 60th b i r t h d a y A graph G is s a i d t o be b i c o n n e c t e d i f both G and i t s complement 5 a r e connected. I n t h i s paper w e mainly d e a l w i t h biconnected g r a p h s and c l a s s i f y a set G o f biconnected graphs i n t o s e v e r a l c l a s s e s i n terms of t h e number of c u t v e r t i c e s ( o r e n d v e r t i c e s ) of G and E. Furthermore w e g i v e s t r u c t u r a l charac- t e r i z a t i o n s of t h e s e classes, t h a t is, c h a r a c t e r i - z a t i o n s of graphs G such t h a t G has m c u t - v e r t i c e s ( e n d v e r t i c e s ) and E h a s n c u t v e r t i c e s ( e n d v e r t i c e s ) r e s p e c t i v e l y , where m and n a r e given, 1 5 m 2 2 and 1 6 n 5 2 . 51. INTRODUCTION A graph G is b i c o n n e c t e d i f both G and i t s complement a r e connected. I n t h i s paper w e a r e mainly concerned w i t h biconnected graphs. W e denote by G t h e set of a l l biconnected g r a p h s and by G p t h e set of a l l biconnected graphs of o r d e r p. W e u s e t h e nota- t i o n s and terminology of C11 o r C21. The c h a r a c t e r i z a t i o n of b i - connected graphs is w e l l known, which i s s t a t e d a s follows: Theorem A. C 1 , p. 261 A graph G of o r d e r p ( p 2 2 ) i s biconnected i f and o n l y i f n e i t h e r G nor E c o n t a i n s a complete bigraph K(m,n) a s a spanning subgraph f o r some m and n w i t h m + n = p. We denote by c ( G ) , e ( G ) t h e number of c u t v e r t i c e s and e n d v e r t i c e s of a connected graph G , r e s p e c t i v e l y . W e say t h e c u t v e h t e x - t y p e of G G i s (m,n) i f { c ( G ) , c ( c ) }= cm,n). S i m i l a r l y t h e E c n d v e k t e x - t y p e of G E G is (m,n) i f { e ( G ) , e ( E ) j = {m,n). Note t h a t t h e c u t v e r t e x - t y p e ( t h e endvertex-type) of a graph G E i s t h e same a s one of its complement E from t h e d e f i n i t i o n . The 1
2 J. Akiyama, K.Ando and H.Mizuno c u t v e r t e x - t y p e and t h e endvertex-type f o r a l l graphs o f o r d e r p 2 5, a s p r e s e n t e d i n Table 1. Table 1. The cutvertex-type and t h e endvertex-type f o r graphs ( E G ) of o r d e r p ( 5 5 ) . W e now p r e s e n t a l i s t of symbols which w e u s e i n t h i s paper: C(m,n) = { G E G I G i s a graph with c u t v e r t e x - t y p e (m,n)1, E(m,n) = ( G E G I G i s a graph w i t h endvertex-type ( m , n ) l , Cp(m,n) = C(m,n) n G GP' Ep(m,n) = E(m,n) n P' C ( G ) = { v E V ( G ) J v is a c u t v e r t e x of G I , End(G) = (v E V ( G ) Iv i s an endvertex of G I , E = U E(m,n), t h a t is E is a set of a l l biconnected graphs G m,n?J z such t h a t both G and have a t l e a s t one endvertex. The following two w e l l known r e s u l t s a r e r e q u i r e d t o prove t h e lemmas w e w i l l mention l a t e r . P r o p o s i t i o n 1. Every n o n t r i v i a l graph G of o r d e r p c o n t a i n s a t l e a s t two v e r t i c e s t h a t a r e n o t c u t v e r t i c e s ; c 6 G ) 2 p - 2 f o r every n o n t r i v i a l graph G. 0 P r o p o s i t i o n 2 . (Harary C31) I f v is a c u t v e r t e x of a biconnected graph G , t h e n v is n o t a c u t v e r t e x of E ; C ( G ) n C ( c ) = Ip f o r every graph G E 6 . 0
Characterizationsand classifications ofbiconnected graphs 3 W e now p r e s e n t two fundamental lemmas. Lemma 1. L e t G be a connected graph and v be any v e r t e x n o t i n C ( G ) . Then (i) c ( G - v ) 2- c ( G ) - 1, (ii) and if t h e e q u a l i t y h o l d s , then v i s an endvertex of G . Proof. L e t C ( G ) = {u,, u2, ..., unl be t h e c o l l e c t i o n of c u t v e r t i c e s of G , where n = c ( G ) . A s s u m e t h a t G - ui = k;lmi (i)Gk r where Gk(i) (i5 k 5 m,) a r e components of G - ui. Without loss of g e n e r a l i t y w e may assume t h a t G i i ) c o n t a i n s v. W e d i v i d e o u r proof i n t o two c a s e s depending on t h e degree of v. Case 1. degG v 2 2. I n t h i s c a s e , t h e d e g r e e of v i n G1(i) i s a t l e a s t 1, and, -so G j i )- - v -i s n o t a n u l l- graph.- Thus,.ai)f o r every... i(l... 5 i 5 n) G ui v = (G v ) ui = ( G : ~ ) v ) u u u Gm( i ) holds. This f a c t i m p l i e s t h a t ui i s a l s o a c u t v e r t e x - i of G v. Therefore w e o b t a i n t h e i n e q u a l i t y Case 2 . degG v = 1. I n t h i s c a s e t h e r e a r e two p o s s i b i l i t i e s de- pending on whether v is a d j a c e n t t o a c u t v e r t e x of G - v o r n o t . o r By (l), (2) and ( 3 ) w e complete t h e proof. 0 Remark: Lemma 1 g i v e s t h e lower bound of c ( G - v) i n t e r m s of c ( G ) f o r a connected graph G and a non-cutvertex v of G , how- ever-it is impossible t o e s t i m a t e t h e n o n t r i v i a l upper bound of c ( G v ) i n terms of c ( G ) a s seen i n t h e example G = Pn + K1. Furthermore, n o t e t h a t t h e converse of s t a t e m e n t (ii)of Lemma 1 d o e s n o t hold when t h e endvertex v of G i s a d j a c e n t t o a c u t v e r t e x of G - v, a s shown by t h e graph i n Figure 1. F i g u r e 1
4 J. Akiyama, K.Ando and H. Mizuno It is easy t o prove t h e following r e s u l t s corresponding the previous two p r o p o s i t i o n s . P r o p o s i t i o n 3 . For any biconnected graph G , Proof. For any connected graph H of o r d e r p , t h e i n e q u a l i t y e ( H ) 2 p ( H ) - 1 holds, and i f t h e e q u a l i t y h o l d s , namely e ( H ) = p(H) - 1, t h e n H must be a s t a r . However every s t a r i s n o t biconnected, t h u s w e o b t a i n P r o p o s i t i o n 4 . I f v is an endvertex of a biconnected graph G I then v is n o t an endvertex o f E ; End(G) n End(E) = 4 f o r e v e r y graph G E 6 . 0 Lemma 2 . L e t G E G and u , v be any v e r t i c e s w i t h degG u = 1, degG v = p - 2 , t h a tP' is, u End(G) and v E n d ( c ) . Then, G E E c o n t a i n s a p a t h P4 a s an induced subgraph, which c o n t a i n s both u and v . Proof. W e may assume t h a t uv E E ( G ) , o t h e r w i s e w e may c o n s i d e r uv i n E i n s t e a d of G. S i n c e degG v = p - 2 , t h e r e i s e x a c t l y one v e r t e x w which i s n o t a d j a c e n t t o v i n G . Since degG u = 1 and uv E E ( G ) by t h e assumption, u is n o t a d j a c e n t w I n . G . S i n c e G is connected, w i s a d j a c e n t to some v e r t e x x o t h e r than u o r v . Since degG v = p - 2 and degG u = 1, w e see t h a t v is a d j a c e n t t o x, and u is not a d j a c e n t t o x. (See Figure 2 . ) F i g u r e 2 . Therefore t h e subgraph induced by {u, v , w, x ) i n G (and a l s o i n E ) is P4 c o n t a i n i n g b o t h u and v as r e q u i r e d . 0
Characterizationsand classificationsof biconnected graphs 5 I f G and Pn a r e graphs w i t h t h e p r o p e r t y t h a t t h e i d e n t i f i c a t i o n of any v e r t e x of G w i t h an a r b i t r a r y endvertex of H- r e s u l t s i n a unique graph (up t o isomorphism), t h e n we w r i t e G Pn fox t h i s graph. W e s h a l l show t h e e x i s t e n c e theorem f o r g r a p h s w i t h c e r t a i n c u t - vertex-types o r endvertex-types. Theorem 1. For a l l p o s i t i v e i n t e g e r s p 2 6 and m ( 0 2 m 5 p - 2 ) , ( i 1 C p ( m , O ) # Izl, (ii) E p ( m , O ) # PI and (iii) E p ( m , l ) # 8 . Proof. To prove t h i s , it i s s u f f i c i e n t t o e x h i b i t graphs G E G 5__ belonging t o t h e v a r i o u s sets (see Figure 3 ) : (i) C (m = 01, P 'p-m 'm+l (15 m 2 P - 11, PP ( m = p - 2 ) . m = O m = l m = 2 m = 3 m - 4 Figure 3 . p = 6 . (ii) L e t Tm = T(m/2 , m / 2 ) be a double s t a r and d e f i n e a graph T; as t h e graph o b t a i n e d from Tm by i n s e r t i n g p - m - 2 new vertices of degree 2 i n t o t h e edge j o i n i n g two nonendvertices of T~ (see Figure 4 ) . Then t h e graph Tk is i n E ( m , o ) f o r m ( 0 5 m 2 p - 2 ) .
6 J. Akiyama, K. Ando and H. Mizuno Figure 4 . p = 8, m = 5 , when m = 0, it c o i n c i d e s w i t h t h e c a s e (ii). (iii) Define a graph GA of o r d e r p ( 2 6 ) a s follows: f o r p , m (1 5 m 5 p - 2 1 , set GA = K1 + (Pp-m-l u - where KO s t a n d s f o r a n u l l graph. Then w e o b t a i n Gm from G; by adding a new v e r t e x x and j o i n i n g x t o one of t h e e n d v e r t i c e s Pp-m-1 (see Figure 5). Then t h e graph Gm belongs t o E p ( m , l ) . Of 0 m = 4 m = 3 m = 2 m = l Figure 5 . p = 6 . Before p r e s e n t i n g Theorem 2 , w e i n t r o d u c e a d e f i n i t i o n and a lemma which a r e r e q u i r e d i n t h e p r o o f s l a t e r . L e t G be a connected graph. An edge uv of G i s s a i d t o b e a d o m i n a t i n g e d g e of G i f any v e r t e x w o t h e r than u o r v i n G is a d j a c e n t t o e i t h e r u o r v . Lemma 3 . L e t G be a connected graph w i t h dominating edge uv E E(G) and w i t h c u t v e r t e x x , t h e n x i s e i t h e r u o r v . Proof. F i r s t w e observe t h a t f o r any w V(G) - {u, v ) , uv i s E a l s o a dominating edge of G - w. Then it follows immediately from t h e f a c t t h a t a graph with a dominating edge is connected t h a t every c u t v e r t e x of G is e i t h e r u o r v . 0
Characterizationsand classificationsofbiconnected graphs 7 Theorem 2 . For mn 2 1, m 2 2 , C ( m , n ) c E m proof. L e t G E C ( m , n) , m n 2 1, m 2 2 . Assume t h a t c ( G ) 2 2 , c(E) 2 1 and t h a t v E C ( G ) , t h e n G - v = G1 u G2 U...U G n' where k is t h e number of components of G - v. Case 1. k 2 3 f o r some v E C ( G )- o r k = 2 and l G l l , IG21 2 2 f o r some v E C ( G ) . I f k 2 3 , G - v c o n t a i n s a spanning complete k - p a r t i t e graph K I G l I , . .., l G k l 1, and t h u s E - v i s a block. I f k = 2 and I G 1 l , l G 2 1 2 2 , E- - v c o n t a i n s a spanning complete bigraph K ( I G 1 l , I G 2 1 ) , and so G - v is a l s o a block. That i s , c(E - v ) = 0. It f o l l o w s from Lemma 1 (ii)t h a t v E End(E) s i n c e c(E) = 1 by t h e hypothesis. Therefore v is a d j a c e n t t o e x a c t l y one v e r t e x , say u , i n E , t h a t i s uv E E ( C ) . However i n t h i s c a s e , G - u c o n t a i n s a spanning s t a r with c e n t e r v . Thus c ( G - u ) 2 1. Since c ( G ) 2- 2 by t h e h y p o t h e s i s , it f o l l o w s from L e m a 1 (ii) t h a t u E End(G). Thus, G E E. Case 2 . G - v = 11-11 u G 2 f o r any v C ( G ) . L e t v , v ' be c u t - E v e r t i c e s of G and u, u ' be e n d v e r t i c e s of G a d j a c e n t t o v , v ' , r e s p e c t i v e l y . Denote by H t h e graph o b t a i n e d from G be removing f o u r v e r t i c e s u, u ' , v and v ' (see Figure 6). Then d G ( u , u ' ) 2 3 . F i g u r e 6 . This i m p l i e s t h a t t h e edge uu' i s a dominating edge of E. By t h e hypothesis, 5 has a t l e a s t one c u t v e r t e x . Applying Lemma 3 , w e may assume t h a t u is a c u t v e r t e x of E . Since t h e c l o s e d neighbourhood NCu'l i n E c o n t a i n s v and a l l t h e v e r t i c e s of V ( H ) i n E , v ' must be an endvertex of E. 0
8 J. Akiyama, K.Ando and H.Mizur;o I2. A CLASSIFICATION OF BICONNECTED GRAPHS W e c l a s s i f y t h e set of a l l biconnected graphs i n t o 5 p o s s i b l e classes depending on t h e cutvertex-type C(m,n), and a l s o t h e endvertex-type E(m,n) r e s p e c t i v e l y , w e g i v e t h e s t r u c t u r a l charac- t e r i z a t i o n s f o r t h e following 6 c l a s s e s of graphs: C ( 2 , 2 ) , C ( 2 , 1 ) , C ( 1 , l ) and E , E ( 2 , 2 ) , E ( m , l ) (m 2 1). Before p r e s e n t i n g o u r r e s u l t s , w e i n t r o d u c e a convenient n o t a t i o n i n o r d e r t o d e s c r i b e v a r i o u s k i n d s of f a m i l i e s of graphs. L e t G, H be p o i n t - d i s j o i n t subgraphs of a graph F. G - H : The induced subgraph of < V ( G ) u V ( H ) > i n F has a complete b i p a r t i t e subgraph w i t h p a r t i t e sets V ( G ) and V ( H ) . G - H : There i s a p a i r of a d j a c e n t v e r t i c e s u , v w i t h u E V ( G ) , v E V ( H ) and a t t h e same t i m e t h e r e i s a p a i r o f nonadjacent v e r t i c e s u, v w i t h u E V ( G ) , v E V ( H ) i n F. G H : N o edge j o i n s a v e r t e x of G t o a v e r t e x o f H . G ---- This n o t a t i o n s t a n d s f o r every p o s s i b l e adjacency H : r e l a t i o n between V ( G ) and V ( H ) . "L: G Figure 7 . W e e x p l a i n t h e s e n o t a t i o n s by t a k i n g graphs i l l u s t r a t e d i n F i g u r e 7 a s an example. The family of g r a p h s r e p r e s e n t e d i n F i g u r e 7 a r e t h e 4 graphs i n Figure 8 i f G = K3, H = K1. F i g u r e 8.
Characterizations and clussifications of biconnected graphs 9 Note t h a t i f G is t h e graph i n Figure 9 ( a ) , t h e n its complement E is one of t h e form i n Figure 9 ( b ) , where F is an a r b i t r a r y graph and F' is its complement. 1 ( a ) Figure 9 . W e a r e now ready t o c h a r a c t e r i z e graphs i n E. Theorem 3. Both G and have a t l e a s t one endvertex, i.e. G E E i f and o n l y i f G is one of t h e following graphs G1 o r G2 i n Figure 10, where F i s an a r b i t r a r y graph ( p o s s i b l y a n u l l g r a p h ) . Figure 10. Proof. F i r s t n o t e t h a t i f G is one of t h e graphs of t h e form G1 o r G2 i n Figure 10, then E i s t h e o t h e r . And so i f G is re- presented i n t h e form G1 o r G 2 t h e n G E E. It t h u s s u f f i c e s t o show t h a t i f G E E t h e n G o r E is r e p r e s e n t e d a s one of t h e graphs G1 o r G 2 . For any G E E, n e i t h e r End(G) nor End(e) is empty. It follows from Lemma 2 t h a t G c o n t a i n s an induced subgraph P4 c o n t a i n i n g both u and v f o r any u E End(G) and any v E End(G). (we may assume without loss of g e n e r a l i t y t h a t uv E ( G ) . ) L e t F be t h e graph obtained from G by removing V ( P 4 ) . Then
10 J. Akiyama, K. Ando and H.Mizuno (1) u E End(G) i f and o n l y i f every v e r t e x o f F i s n o t a d j a c e n t t o u i n G . ( 2 ) v E End(e) i f and o n l y i f every v e r t e x of F i s a d j a c e n t t o v i n G . Thus, G i s a graph of t h e form G1 o r G 2 depending on uv i E ( G ) o r uv E ( E ) r e s p e c t i v e l y . 0 We now p r e s e n t two c h a r a c t e r i z a t i o n theorems, t h e f i r s t one f o l l o w s immediately from Theorems 2 and 3, t h e second from Theorem 3. C o r o l l a r y 3.1. A biconnected graph G i s i n C ( 2 , l ) i f and o n l y i f G o r E is one of t h e graphs of t h e form G1 o r G 2 i n Figure 11, where F is any graph. F F F i g u r e 11. Corollary 3.2. For any given i n t e g e r m 2 1, a biconnected graph G is i n E ( m , l ) i f and o n l y i f G o r E is one of t h e following graphs G1, G2 o r G3 i n F i g u r e 1 2 , where F i s i n G I , G2 and G3 i s any graph, and t h e induced subgraph <NCFI> i n G3 has no endvertex. Figure 1 2 .
Characterizations and classificationsof biconnected graphs 1 1 Theorem 4 . I f G has a t l e a s t 3 e n d v e r t i c e s , t h e n E has a t m o s t one endvertex, i.e. Proof. Let G E E be a graph w i t h e ( G ) 2 3. By Theorem 3 , G i s one of t h e graphs of t h e form G1 o r G 2 i n Figure 10. -Case 1. G is a graph o f t h e form G1 i n Figure 10. S i n c e e ( G ) 2 3 , t h e r e e x i s t s a v e r t e x u E V(F) such t h a t u E End(G). This implies t h a t uvl, uv3 L E ( G ) , i.e., uvlI uv3 E E ( C ) , and so vl, v3 u End(E). Furthermore, s i n c e UW, v4w E E ( E ) f o r any w V(F) - {u}, w e see t h a t w L End(E) f o r any w V(F) - { u ) . E E Thus w e o b t a i n End(E) = {v2}, i . e . e ( E ) = 1. Case 2 . G i s a graph of t h e form G2 i n Figure 10. S i n c e e ( G ) 2 3, t h e r e e x i s t s a v e r t e x u E V(F) such t h a t u E End(G). S i m i l a r t o Case 1, w e o b t a i n t h a t End(E) = {v3}, and t h u s e ( G ) = 1. By Case 1 and 2 , w e see t h a t e(E) = 1 i f e ( G ) 2 3. 0 The following r e s u l t s a r e immediately from Theorems 2 and 4 . C o r o l l a r y 4 . 1 . For any i n t e g e r m , n (mn 2 31, C(m,n) = 0. 0 C o r o l l a r y 4 . 2 . The set c ( 2 , 2 ) c o i n c i d e s w i t h t h e set E ( 2 , 2 ) , furthermore any graph G i n c ( 2 , 2 ) i s one of t h e graphs i n Figure 13, where F i s an a r b i t r a r y graph ( p o s s i b l y a n u l l g r a p h ) . F i g u r e 13. Theorem 5. C ( l , l ) = E u E ( 1 , O ) . Proof. W e sliow t h a t G E ( l,O) provided t h a t G c(1,l) and E E G L E . Assume t h a t e ( G ) = 0 and C ( G ) = { v } , t h e n
显示前 20 页。下载资料查看完整内容。
暂无评论。快来抢沙发吧！
评论 (0)
暂无评论。快来抢沙发吧！