AN ELEMENTARY METHOD FOR FINDING SELFCOMPLEMENTARY GRAPHS
IP.com Disclosure Number: IPCOM000151530D

Electronic Publication Date: 23Apr2007 
Publishing Venues
The IP.com Prior Art Database (backfile addition)
Software Patent Institute
Related People
Alter, Ronald  Author
[+1]
University of Kentucky  Owner
Abstract
Copyright
Database entry Copyright (c) Software Patent Institute
Language
English (United States)
Country
United States
Document File
7 pages / 270.3 KB
AN ELEMENTARY METHOD FOR FINDING
SELFCOMPLEMENTARY GRAPHS
BY
RONALD ALTER
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 selfcomplementary 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 selfcomplementary is that be even. Thus, every selfcomplementary
(3
graph has 4n or 4n+l points. Figure 1 consists of the smallest non trivial se1.fcomplementary graphs, nzme3y the one selfcomplementary graph of order 4 and the two selfcomplementary graphs of order 5 . b
FIGURE
For a proof of chis remark and more information about selfcomplementary graphs the reader is referred to Xarary [3].
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 selfcomplementary graphs on n vertices. In particular, the nurrber of selfcorn2lementary graphs on 8 vertices is 10.
Although Ringel [6] . gave a procedure for coastructing selfcomplementary grsphs, the ten saifcomplementary grr?hs of order eight have never appeared i n the literature. In an unpublished manuscript Morris [4]
GRDHS
u.5.1 i. :i;c::'s 71c;hod to construct the selfcomplementary graphs on 8 and
TIiEOZX. Let G be an selfcomplementary graph w i t h p > I. points, then:
(a) 2 2nd i? arc both connected.
There is :lo point iil G of order (pI).  
(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 (pa1)
. If an even (odd) number of points or order a are adjacent

t o points of order (paI) in G rnen an odd (even) number of points of order a are adjacent to points of order (pa1) in G. Hence G is noc
isqmorphic to contradicting that G is selfcomplemertary. 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...