AN ELEMENTARY METHOD FOR FINDING SELF-COMPLEMENTARY GRAPHS

IP.com Prior Art Database Disclosure
IP.com Disclosure Number: IPCOM000151530D
Electronic Publication Date: 23-Apr-2007
Find Similar Download

Publishing Venues

The IP.com Prior Art Database (backfile addition)
Software Patent Institute

Related People

Alter, Ronald - Author [+1] [-1]
University of Kentucky - Owner

Abstract

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 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 FIGURE For a proof of chis remark and more information about self-complementary 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 self-complementary graphs on n vertices. In particular, the nurrber of self-corn2lementary graphs on 8 vertices is 10. Although Ringel [6] . 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 [4]

Copyright

Database entry Copyright (c) Software Patent Institute

Language

English (United States)

Country

United States

Document File

7 pages / 270.3 KB

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 49% of the total text.

Page 1 of 7

AN ELEMENTARY METHOD FOR FINDING
SELF-COMPLEMENTARY GRAPHS

BY

RONALD ALTER

MA1 LING ADDRESS :

DEPARTMENT OF COMPUTER SCIENCE

915 PATTERSON OFFICE TOWER

UN IVERS ITY OF KENTUCKY LEXINGTON., KENTUCKY 40506

[This page contains 1 picture or other non-text object]

Page 2 of 7

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

(3

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

FIGURE

For a proof of chis remark and more information about self-complementary 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 self-complementary graphs on n vertices. In particular, the nurrber of self-corn2lementary graphs on 8 vertices is 10.
Although Ringel [6] . 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 [4]

GRDHS

[This page contains 1 picture or other non-text object]

Page 3 of 7

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~~.

[This page contains 1 picture or other non-text object]

Page 4 of 7

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

First page image
You are not signed in. If you have an IP.com account, your download price may be lower or waived. Click here if you want to sign-in now.
Loading PayPal...
The full document comprises 7 pages and is available as a PDF document as well as a ZIP archive. The cost is $40.00 USD (depending on your billing address, sales tax may apply); payment may be made directly using your credit card or your PayPal account.

If you've already purchased this document, and wish to download it now you may enter the download access code you received in your original email receipt.