The IP.com Prior Art Database (backfile addition)
Software Patent Institute
Database entry Copyright (c) Software Patent Institute
English (United States)
7 pages / 270.3 KB
AN ELEMENTARY METHOD FOR FINDING
MA1 LING ADDRESS :
DEPARTMENT OF COMPUTER SCIENCE
915 PATTERSON OFFICE TOWER
UN IVERS ITY OF KENTUCKY LEXINGTON., KENTUCKY 40506
AN ELEGNTARY YiTHOD FOX FINDING SELF~-C'31f13Td~NTARY
Ronald A l t e r
A graph is self-complementary i f it X s isomor?nic to its complement.
It is easy to show that a necessary condit:ion that G with p points be self-complementary is that be even. Thus, every self-complementary
graph has 4n or 4n+l points. Figure 1 consists of the smallest non- trivial se1.f-complementary graphs, nzme3y the one self-complementary graph of order 4 and the two self-complementary graphs of order 5 . b
For a proof of chis remark and more information about self-complementary graphs the reader is referred to Xarary .
Harary 121 lists as an ynsolved problem ;he enumeration of self- conplementary graphs. Read [S] uses a theorem of de Bruijn to cal- culate the number of self-complementary graphs on n vertices. In particular, the nurrber of self-corn2lementary graphs on 8 vertices is 10.
Although Ringel  . gave a procedure for coastructing self-complementary grsphs, the ten saif-complementary grr?hs of order eight have never appeared i n the literature. In an unpublished manuscript Morris 
u.5.1- i. :i-;c::'s 71c;hod to construct the self-complementary graphs on 8 and
TIiEOZX. Let G be an self-complementary graph w i t h p > I. points, then:
(a) 2 2nd i? arc both connected.
There is :lo point iil G of order (p-I)-. --- -
(c) For everv point in G of or2e.r a # (p-.1)/2 there is a point of order
(d) For every point in G or order a # (p-.1)/2, G has an even number of points of order a.
PROOF: (a) - (c) are immediate. To prove (d), suppose G has an odd amber of points or order a, then by (c) it has an odd number of points 02 srder (p-a-1)
. If an even (odd) number of points or order a are adjacent
t o points of order (p-a-I) in G rnen an odd (even) number of points of order a are adjacent to points of order (p-a-1) in G. Hence G is noc
isqmorphic to contradicting that G is self-complemertary. This conpletes the proof of.the Theorem.
As an application of this Theorem we shall construct a l l self-
compleixentary graphs of order 8. Since G 'has 14 lines it follows that the sum of the orders of the vertices is 28. 'From the Theorem it follows
that there are only six possible distinct ways to partition the orders
of the eighn: vertices. These are given be.10~~.
Clearly, thc first tvo cases, (1,1,1,1,6,6,6,6) and (1,1,2,2,5,5,6,6) are no: possible. Yhis leaves four cases m d it turns out that
CSSC A = (1,1,3,3,4,4,6,6) has...