• 検索結果がありません。

On the number of non-isomorphic simple connected planar graphs of order 7 and 8

N/A
N/A
Protected

Academic year: 2021

シェア "On the number of non-isomorphic simple connected planar graphs of order 7 and 8"

Copied!
2
0
0

読み込み中.... (全文を見る)

全文

(1)

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.

(2)

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

参照

関連したドキュメント

In our paper we tried to characterize the automorphism group of all integral circulant graphs based on the idea that for some divisors d | n the classes modulo d permute under

The torsion free generalized connection is determined and its coefficients are obtained under condition that the metric structure is parallel or recurrent.. The Einstein-Yang

The basic bound on the chromatic number of a graph of maximum degree ∆ is ∆ + 1 obtained by coloring the vertices greedily; Brooks theorem states that equality holds only for

Abstract The representation theory (idempotents, quivers, Cartan invariants, and Loewy series) of the higher-order unital peak algebras is investigated.. On the way, we obtain

In Section 13, we discuss flagged Schur polynomials, vexillary and dominant permutations, and give a simple formula for the polynomials D w , for 312-avoiding permutations.. In

Debreu’s Theorem ([1]) says that every n-component additive conjoint structure can be embedded into (( R ) n i=1 ,. In the introdution, the differences between the analytical and

Then it follows immediately from a suitable version of “Hensel’s Lemma” [cf., e.g., the argument of [4], Lemma 2.1] that S may be obtained, as the notation suggests, as the m A

Abstract The classical abelian invariants of a knot are the Alexander module, which is the first homology group of the the unique infinite cyclic covering space of S 3 − K ,