This site is supported by donations to The OEIS Foundation.

# Sequences from Harary and Palmer's Graphical Enumeration

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

- For a long time I (njas) 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 [[<dont>|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.

## Contents

- 1 Harary and Palmer's Graphical Enumeration
- 1.1 Chapter 1: Labeled Enumeration
- 1.2 Chapter 2: Polya's Theorem
- 1.3 Chapter 3: Trees
- 1.4 Chapter 4: Graphs
- 1.5 Chapter 5: Digraphs
- 1.6 Chapter 6: Power Group Enumeration
- 1.7 Chapter 7: Superposition
- 1.8 Chapter 8: Blocks
- 1.9 Chapter 9: Asymptotics
- 1.10 Chapter 10: Unsolved Problems
- 1.11 Appendix I
- 1.12 Appendix II
- 1.13 Appendix III

### 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

#### Appendix III