On
the number
of non-isomorphic
simple
connected planar graphs of order 7 and 8
Osamu Nakamura Faculty of Education
The numbers of non-isomorphic simple connected planar graphs of order n (1≦7z≦6) are listed in [6]. The correct number for order 6 is 99. In this paper we shall compute the number of non-isomorphic simple connected planar graphs of order 7 and 8. We have the following theorem.
Theorem、There are 647 non-isomorpfiicsimpleconnectedplanargraphs of order 7 am
These results are obtained by a personal computer PC9821Ne. Our C十十program has 1094 lines. So we give only algorithm.
Algorithm. Finding non-isomorphic simple connected planar graphs of order n input: order n
1. Set R←all edges of Kn − 2. Set G ←皿11 graph j弘
3. Do the following: graphCR.G)
Procedure graphiR.G)
1. If R is empty, then return 2. For alleE瓦dothe following: 3 4 5 6 7 8 9 0 1 Set G’←GU硝
If G’is not isomorphic to stored graphs, then If G’is planar, then
Store G’
If G’is connected, then し Displayび
Set R’←召一図
graph(R≒G’) ,- A few planarity algorithms are given in[1]and a mathema七ica program of checking planarity of graph is given in[41. But this program has some bugs. We debug this program and translate it from mathematica into C十 十.A mathematica program of checking whether two graphs are isomorphic or not is given 込[41. We translate it from mathematica into C十十. The connectedness algorithm is well-known.
156 高知大学学術研究報告 第44巻(1995年)自然科学
References ・● ………: ……… 1. Ronald Gould. Graph.tfieor-y・Benjamin Cummings, Menlo Park, Calif.,1988 2. Brain W. Kernighan and Dennis M. Ritchie.プログラム言語C第2版 共立出版1989 3. R. Sedgewick.アルゴリズムC十十 近代科学社∧1994つ.・・. .・> ‥‥‥‥‥‥‥ 4. Steven S. SχIEχA.Mathematica組み合せ論とグラフ理論 トッパン1992 犬
5. Bjarne Stroustrupプログラミング言語C十十第2版 トッパン1993
6. R. J. Wilson.グラフ理論入門 近代科学社 < ニ
Manuscript received: September 22,1995 \ :Published: December 25,1995