Sequences from Harary and Palmer's Graphical Enumeration

Keywords: Harary, Palmer, graphs, counting, enumeration, integer sequences, concordance

For a long time I have had the idea of making a series of concordances which would list the integer sequences to be found in certain classical books (Riordan, Comtet, Stanley, Knuth, Graham-Knuth-Patashnik, etc.). Here is the third of these, a concordance to:

Frank Harary and Edgar M. Palmer's Graphical Enumeration, Academic Press, 1973

The idea is that when you are reading one of these books, these files will give pointers to the On-Line Encyclopedia of Integer Sequences whenever an interesting sequence is mentioned. This will enable you to see the terms of the sequence, recurrences, formulae, other references, links, most recent progress, etc.

Furthermore, the preparation of these concordances will supply additional sequences for the database, and additional references for existing sequences.

In case I have missed any sequences from this book, please send them to me at this address: njas@research.att.com.

There are several sequences in this book (marked below by ****) where not enough terms are given to make it possible to enter them into the database. It would be nice if someone would work these out and send them in to the database (unless of course they are there already, in which let me know and I will add links in both directions). Whenever possible, please use the convenient web page for Contributing a New Sequence or Comment.

Thanks to Christian G. Bower (bowerc@usa.net), Wolfdieter Lang (wolfdieter.lang@physik.uni-karlsruhe.de), and especially Vladeta Jovovic (vladeta@EUnet.yu), for updates and corrections to this file.

Harary and Palmer's Graphical Enumeration

Chapter 1: Labeled Enumeration

Page 3, G_p, (1.1.2): A006125
Page 5, D_p(1), (1.1.5): A053763
Page 7, C_p, Table 1.2.1: A001187
Page 9, B_p, (1.3.2): A013922
Page 10, R_p, (1.3.4): A053549
Page 11, W_p, (1.4.1): A006125
Page 12, U_p, (1.4.6): A033678
Page 13, triangle of coefficients of w_p(x), (1.4.7): A058878
Page 18, Table 1.5.1: This shows values of C_p(k). Triangle formed by these numbers gives A058843.
Triangle of values of C_p(k)/2^(k*(k-1)/2) gives A058875.
Columns give A058872 and A000683, A058873 and A006201, A058874 and A006202
Page 18, acyclic digraphs (or DAGs): A003024 (labeled), A003087 (unlabeled)
Page 19, labeled acyclic digraphs (or DAGs), (1.6.10: A003024
Page 19, (1.6.4), triangle of values of a_{p,k} gives A058876.
a_{p,p-1} gives A058877.
Page 20, t_p, (1.7.2): A000272
Pages 29-31: probably many of these exercises would provide new sequences. (****)
Page 30, Problem 1.13(a): A036361
Page 30, Problem 1.13(b): presumably the exponent should be p-k-2. For k=3 we get A036362
Page 30, Problem 1.13(c): A036363
Page 30, Problem 1.14: A003092
Page 30, Problem 1.15(a): A036360
Page 30, Problem 1.15(b): A057500 (Thanks to Keith M. Briggs for pointing this out)
Page 31, Problem 1.16(a): A059167
Page 31, Problem 1.19: A016031

Chapter 2: Polya's Theorem

Page 48, connected graphs, c(x), (2.6.2): A001349
Page 48, connected graphs with three components, C(x), (2.6.3): A058915

Chapter 3: Trees

Page 51, p^(p-2): A000272
Page 52, T_p, (3.1.3): A000081
Page 54, T_p, (3.1.13): A000081
Page 58, t_p, (3.2.8): A000055
Page 60, R(x), (3.3.1): A000151
Page 60, r(x), (3.3.3): A000238
Page 61, L(x): A063881
Page 62, homeomorphically irreducible planted trees by nodes, H bar(x), (3.3.8): A001678
Page 62, homeomorphically irreducible rooted trees by nodes, H(x), (3.3.9): A059123. See also A007827.
Page 62, homeomorphically irreducible trees by nodes, h(x), (3.3.10): A000014
Page 62. Corrections from Wolfdieter Lang (wolfdieter.lang@physik.uni-karlsruhe.de): eq. (3.3.10) should have an additional term -(Hbar^2(x))/x^2. There is also a misprint in the proof p. 63, line 4: it should be Z(S_{2},Hbar(x)) not H(x).
Page 64, U(x), (3.3.15): A004111
Page 64, u(x), (3.3.16): A000220
Page 66, u(x), (3.3.22): A000220
Page 66, need to track down the sequences mentioned from [HP14]
Page 67, P bar(x), (3.3.23): A000108 (Catalan numbers)
Page 67, P(x), (3.3.24): A003239
Page 67, p(x), (3.3.26): A002995
Page 69, triangle of values of coefficients of U_n(x), (3.4.1): A058879
Page 70, v(x), (3.4.4) and Table 3.4.1: A001373
Page 70, functions, (3.4.6) and Table 3.4.1: A001372
Page 71, the two-dimensional arrays enumerated by T_C(x,y), T_B(x,y), T(x,y), t(x,y) - are they in the database? (****)
Page 71, B bar(x), (3.4.13): A007563
Page 71, B(x), (3.4.14): A035053
Page 73, D(x), (3.4.20): A003080
Page 73, d(x), (3.4.21): A003081
Page 75, M_1(x), (3.5.3), number of 2-trees rooted at a symmetric end-edge: A005750
Page 75, N_1(x), (3.5.4), number of 2-trees rooted at an asymmetric end-edge: A063682
Page 75, M(x), (3.5.9), number of 2-trees rooted at any symmetric edge: A063687
Page 75, N(x), (3.5.10), number of 2-trees rooted at any asymmetric edge: A058870
Page 75, L(x), (3.5.11), number of 2-trees rooted at any edge: A058866
Page 76, DELTA(x), (3.5.13), number of 2-trees rooted at a triangle: A063688
Page 76, s_1(x), (3.5.16), number of 2-trees rooted at a triangle with two similar edges: A063692
Page 76, s_2(x), (3.5.17), number of 2-trees rooted at a triangle with 3 similar edges: A063689
Page 76, t(x), (3.5.19), 2-trees: A054581
Page 78, f_n, (3.5.22): A000108 (Catalan numbers)
Page 78, M_1 bar (x), (3.5.25): A000108
Page 78, N_1 bar (x), (3.5.26): A000150, A050180
Page 78, L bar (x), (3.5.28): A001895
Page 78, DELTA bar (x), (3.5.29): A003446
Page 78, s_1 bar (x), (3.5.30): A063786
Page 78, s_2 bar (x), (3.5.31): A007595
Page 78, t bar (x), (3.5.32): A000207
Page 79, t_n bar, Table 3.5.1: A000207 (note that two of the entries in this table are wrong)
Pages 79-80: probably many of these exercises would provide new sequences. (****)
Page 80, Problem 3.9: A055290
Page 80, Problem 3.10, U(x): A004111
Page 80, Problem 3.13: A003239

Chapter 4: Graphs

Page 83, Triangle of values of g_{p,q}: A008406
Page 88, m_p(x), (4.1.18): A001399 (p = 3), A003082 (p = 4), A014395 (p = 5), A014396 (p = 6), A014397 (p = 7), A014398 (p = 8), A050535 (p = infinity)
Page 90, g_p, (4.2.1): A000088
Page 90, c_p, (4.2.2): A001349
Page 91, Table 4.2.1: A000088, A003083 and A001349
Page 93, triangle in Table 4.2.2 gives A054923
Page 112, triangle in Table 4.6.1 gives A039754; totals give A000616
Page 114, w_p, (4.7.1): A002854
Page 117, w(x), (4.7.4): A002854
Page 117, u(x), (4.7.5): A003049
Pages 117-118: probably many of these exercises would provide new sequences. (****)

Chapter 5: Digraphs

Page 124, Table 5.1.2: A000273 (d_p), A003084 (p a_p), A003085 (c_p)
Page 124, T(p), (5.2.1): A000568
Page 126, T(p), Table 5.2.1: A000568
Page 127, S(x), (5.2.4): A051337
Page 129, o(C_p): (5.3.3): A058880
Page 133, c_p, (5.4.14): A001174
Pages 133-134: probably many of these exercises would provide new sequences. (****)

Chapter 6: Power Group Enumeration

Page 139, g_p bar, (6.2.3) and Table 6.1.1 (note that zero entries have been omitted from the table): A000171
Page 140, d_p bar, (6.2.7) and Table 6.1.2: A003086
Page 149, Table 6.5.1: A000591 (t=1)
Page 155, Table 6.6.1, d'_p (note last entry is wrong): A002499
Page 155, Table 6.6.1, r'_p: A002450
Pages 155-157: probably many of these exercises would provide new sequences. (****)

Chapter 7: Superposition

Page 171, Table 7.4.1: column 1: a new sequence?; columns 2, 3 and 4: A003223, A003224, A003225 (****)
Page 175, (7.5.12): A005814
Page 176: probably many of these exercises would provide new sequences. (****)

Chapter 8: Blocks

Page 188, Table 8.6.1, b_p: A002218
Page 191, connected graphs without endpoints, (8.7.11): A004108 (see also A004110)
Page 191, acyclic digraphs (or DAGs): A003024 (labeled), A003087 (unlabeled)
Page 194, Table 8.8.1, a_p: A003087
Page 194: probably many of these exercises would provide new sequences. (****)

Chapter 9: Asymptotics

Page 196, g_p: A000088
Page 198, d_p: A000273
Page 205, G_p: A006125
Page 205, C_p: A001187
Page 207, B_p: A013922
Page 208, g_p bar: A000171
Page 208, d_p bar: A003086
Page 209, T_p: A000081
Page 210, B_p, (9.5.03): A000108 (Catalan numbers)
Page 213, T_p: A000081
Page 213, t_p: A000272

Chapter 10: Unsolved Problems

Page 218, Section P2.1. Strong digraphs of order 4: A035512 (more is now known)
Page 218, Section P2.2. Unilateral digraphs (the sequence is wrong): A003088 (more is now known)
Page 218, Section P2.3. Digraphs with a source (the sequence is wrong): A051421
Page 218, Section P2.4. Transitive digraphs: or topologies: A001930 (unlabeled - the last term is wrong); A000798 (labeled)
Page 219, Section P2.5. Digraphs both self-complementary and self-converse: would give new sequence? (****)
Page 219, Section P2.6. Eulerian digraphs (the sequence is wrong): A058337)
Page 219, Eulerian tournaments: would give new sequence? (****)
Page 219, Section P3.1. Hamiltonian graphs: A003216 (more is now known)
Page 220, Hamiltonian digraphs: would give new sequence? (****)
Page 220, Section P3.2. would give new sequences? (****)
Page 220, Section P3.3. Graphs such that each node belongs to a triangle: would give new sequence? (****)
Page 220, Section P3.4. Identity (or asymmetric) graphs: A003400; identity (or asymmemetric) digraphs (the last term is wrong): A051504; identity (or asymmemetric) trees: A000220.
Page 221, Section P3.5 ?
Page 221, Section P3.6 ?
Page 221, Section P3.7: A003089
Page 222, Section P3.8: interval graphs have been extensively studied - see the index to the database
Pages 222-230 ?
Page 228, Section P6.1: A039751
Page 231, Section P8.1: s(y) (sequence contains errors): A000665 (more is now known)
Page 231, Section P8.1: Latin squares have been extensively studied - see the index to the database
Page 231, L_n: A000315
Page 231, species of Latin squares: A003090
Page 232, Section P8.3: knots have been extensively studied - see the index to the database
Page 234, Section P8.4: rooks problem: A000903 (more is now known)
Page 234, queens problem: A000170 (more is now known)
Page 234, Section P8.5: polyominoes have been extensively studied - see the index to the database
Page 235, Table 10.8.1 (both rows contain errors): A000104 and A001419 (more is now known)
Page 235, triangular polyominoes: A000577 (more is now known)
Page 236, hexagonal polyominoes: A038147 (see also A000228)

Appendix I

Page 240, triangle gives A008404
Page 240, g_p gives A000088
Page 241, triangle gives A054923
Page 241, d_p, Table A4: A000273
Page 241, connected digraphs, Table A4: A003085
Page 241, symmetric relations, Table A4: A000666
Page 242, g_p: A000088
Page 242, c_p: A001349
Page 242, b_p: A002218
Page 243, Table A5 (second column contains errors): A003086, A002499, A002500
Page 243, Table A6: A000798
Page 244, Table A7: A000055, A000081, A000220, A000014
Page 245, Table A8: A000568
Page 246, Table A9: A003091

Appendix II

Page 247, Table A10: last row is part of A052283
Page 248, Table A11: last row is part of A052283