AN INTRODUCTION TO F-GRAPHS, A GRAPH-THEORETIC REPRESENTATION OF NATURAL NUMBERS

VOL. 15 NO. 2 (1992) 313-318

AN INTRODUCTION TO F-GRAPHS, A GRAPH-THEORETIC REPRESENTATION OF NATURAL NUMBERS

E.J.FARRELL

Department

ofMathematics The University of theWestIndies

St. Augustine,Trinidad

(Received April 4, 1987 and in revised form June 26, 1990)

ABSTRACT.

A

special type of family graphs

(F-graphs,

^for brevity) are introduced. These are cactus-type graphs which form infinite families under an attachment operation. Some of the characterizing properties of F-graphs are discussed. Also, it is shown that, together with the attachment operation, these families form an infinite, commutative semigroup with ^unit element.

’inally,

itisshown thatF-graphs aregraph-theoreticalrepresentations of natural numbers.

KEY

WORDS AND PHRASES. Cactus type graphs, core, pattern recognition, semigroup, semigroup isomorphism, naturalnumbers, ancestor

(graph),

parent

(graph),

descendant

(graph), F-

graph, attachingagraph, basisgraph,root ofanF-graph.

1991AMS SUBJECT CLASSIFICATION CODE. 05C99,20M07.

1. INTRODUCTION.

First of allwe give^some definitions relative to the material which follows. Forthe standard definitions inGraphTheory,^wereferthereadertoHarary

[1].

Let

(G,u)

^and

(H,v)

^{be two}graphs, rooted at u and vrespectively.

By

attaching

H

^to

G,

we mean the identification of the roots^uandv.

H

is thereforeasubgraphof thenewgraphformedby the process.

Suppose

that we attach an isomorph of

(H,u)

^{to every node of}

G,

then the graph formed by doing so, is denoted by

G(H).

^{Notice that if} all the nodes of

H

are equivalent

(for

example if

H

is a

cycle),

thenwe speak about

G(H)

^without specifying a root in H. Also, since every node of

G

isusedinforming

G(H),

it is unnecessarytospeakaboutarootin

G.

Let us beginwith a singlenode G

0,

then attach to it arootedgraph

(H,u),

to form thegraph G

- ^{GO(H)( H). G}

^2isthegraphformed by attachinganisomorph of

H

to everynode ofG i.e., G²

-GI(H). In

general,

G

ⁱ⁺

Gi(H). By

continuing in this manner, ^we obtain a family

F {G 0, G,G2,...}

^ofgraphs. If

H

is anode, then

F {GO};

^{otherwise Fisinfinite. We callGO}

the core of the family. G is the basis of F. G² is the

(direct)

^{descendant of}

G (In

^general, G

+ k(k > 0)

^{is a}descendant ofG

i,

^the

(immediate)

parent ofG²

(In

general, G is an ancestorof G

+ k,

^k

> 0).

Wedefine the elements of

F

tobeF-graphs. G

o

_{andG arecalled,trivialF-graphs.}

Wenotethat F-graphsareaspecialkindof

"cactus-type"

graphsand arealsoHusimitrees

(Harary

[2]).

ForanyF-graph G

k,

^{wecall the}subgraphsisomorphictothebasis G

1,

leaves ofG

k.

314 E.J. FARRELL

In the material which follows,^wederivesome characterizingproperties of F-graphs, and then investigate someof thealgebraicproperties ofthefamilies. Weshowthat operationscanbedefined onF-graphs,so astocreateasystemwhich isisomorphic to the system of natural numbers.

2. SOME

CHARACTERIZING PROPERTIES

OF

F-GRAPHS.

Given an arbitrary graph

G,

it isofinterest todetermine

(i)

^{whetherornot Gis a}non-trivial F-graph and

(ii)

^ifitis, then what is itspositionin the family hierarchy. First ofall,ifGisnota cactus-typegraph,thenitcannotbeanon-trivialF-graph. Also,from the definition ofanF-graph, G must consist of isomorphic leaves. This criteria will eliminate many graphs.

However,

many cactus-typegraphs will qualify, ^so the problemis certainly not a trivialone. For example, is the following graph

T

anon-trivial F-graph?

T:

Figure

Thefollowing^theoremhelps to characterizeF-graphs.

THEOREM 1. Let

F {GO, G1,G2,...}

^{beafamily ofF-graphsin whichG has}

rn( > 1)

^nodes

andnedges. Then

Gr(r > O)

^has

(i)

^mrnodes

(ii) n(nr_-11)

^edges

and

(iii) mr-

_{1 leaves}

rn-1

PROOF.

Theresultcanbe easilyproved.

Theorem 1 provides a

(not

^too

useful)

necessary conditionfor a graphto be a non-trivial

F-

graph. SinceG^Oisalways anode,thenclearly,themembers of the

family’

are totallycharacterized bythe

(rooted)

^leaf

G 1.

Ifoneisgivenanon-trivialF-graph, thenTheorem could be used to find itsposition r, if_aleafcanbe determined. The determinationof the leaf ofan arbitrarynon- trivial F-graph is inpractice,a difficult exercise. Thefirst inclination is to findsymmetries inthe graph; butthis is forbidding,evenin reasonablysmallF-graphs.

Thus,

apractical^{useof Theorem} 1 as anecessary condition, posesgreat problems, sincem and ndependon

one’s

ability to identify the leaf.

We nowrefer the reader to thegraph

T

in Figure 1. Because

T

is constructed from triangles,

one is inclined to look for

T

in the family of triangles.

T

cannot be found in this family; and therefore theconclusioncould be that

T

isnotanon-trivialF-graph.

However,

careful observation will show that

T

consistsof thegraph

G

²from the family oftriangles,withthe leaf

G

²attached to everynode usinga nodeofvalency2asaroot. Therefore,

T

isindeedanon-trivial F-graph.

T

is thesecondmember of thefamilyofF-graphswith basisG²rooted at_an2nodeofvalency 2

(i.e.

^the

family of

G2’s).

It would be useful to develop some analytical meansfor arriving at the correct conclusionaboutanarbitraryT. At present, we areunable to do this.

3. SOME

ALGEBRAIC

PROPERTIES OF

F-GRAPHS.

The practical problem of determining whether or not an arbitrary graph is a non-trivial

F-

graph, seems to beone of pattern recognition.

In

this section, ^wewill show that the family

F

has somebeautifulalgebraic properties which will have usefulimplicationsonthepatterns displayedby thegraphs.

In

thematerialthatfollows,we assumethatzerobelongstothesetofnatural numbers.

LEMMA

1.

In

G

r,

thereexistsanode formedbythe coalescence of the roots ofrleaves.

PROOF.

Thisfollows immediatelyfrom theconstructionofG^rfromG

0.

DEFINITION. Let :rbeanodeof

G

^r definedby

Lemma

1. Thenxis arootof

G r. (Notice

that it is possible for several nodes ofG^rto qualify as aroot eve___anif

G

^r is not regular. Therefore anyof themcanbe usedin the attachment

process).

^{Theideaofaroot and the}existenceofaroot of

G

^r

(by definition)

^arecrucialtothe theoryofF-graphs. Weshow later on, thattheyarevital to theestablishmentof the properties ofF-graphs.

LEMMA

2: G G

- ^{1(G1) GI(G} - ^1),

^{forall k}

^>

^0.

PROOF. We will prove the result by induction on k. For k 1,

G

^k- is

G 0,

which is a rtode. Therefore, G^k-

1(G1) GO(G1)

G

G(GO).

Let us assume that the result holds for k-1. Then

G/r-

_G

2(G1 GI(GIr- 2).

Now

G/r G/r I(G1 (GI(G/- 2))(G1).

Thegraph

(GI(G/- 2))(G1)

is obtainedby attaching G toeverynode of

GI(G

^k-

2). In

particular, G is attachedtoevery node of

G/ -2.

Itcanbeseen that theroots ofeach

G/

^-2nowbecome the rootsof each

G/ 1.

Henceweobtain

G/

attached to

G

i.e.

GI(G

^I

1).

^Therefore,

G/ G/ I(G1 GI(GI 1).

Hence,

theresult holds for k.

By

thePrincipleofInduction,itholds for all k

>

^0.

Lemma 2 suggests that it does not matter whether we attach

G/-

to

G

or

G

to G^k-

1,

whenforming

G/.

Thisideaisgeneralized bythefollowingtheorem.

THEOREM2: G

+

⁸

G.(G ) GS(G).

PROOF. Wewillprove theresult byinductionon k. For k 0,

G/

is a node, and the result follows trivially. For k 1, the resultholds, asshown aboveinLemma2. Let usassume thatthe result holds for k-1. Then

G/r ⁺

^8-1

Gk- 1(G8 GS(GIr- 1).

Clearly

then,

G

+

⁸ _G

+

^8-

I(G1 (G l(GS)) (G1) (G,(G 1)(G1) (1)

The graph

(G/- I(GS))(G1)

^{is the} graph obtained by attaching G to every node of

G

^It-

I(G8).

Now

the attachment of

G

to everynode of thesubgraphs G⁸of

G

^k

-1(G8),

will createsubgraphs, each of which is G^s

+ 1. Therefore,

the resulting graph can be described as

G

^It- with

G

^s

+

attachedi.e.G^k

l(G8 ⁺ 1).

316 E.J. FARRELL

Consider any roof z of

G/- 1.

The graphs with z as a common node can be described as

G

- ^I(GI(Gs))

^{i.e. G}

-

^{with the graph}

^{GI(G s)}

attached to it, at z. But the leaf G can be considered as being ^attached to

G/- 1,

and each node of

G

has

G

^sattached toit

(at

itsroot

z).

Also,everyother nodeofG

: 1(G1)

will haveG^sattached. Therefore, thegraph G

l(GS ⁺ 1)

^is

also

(G

^k-

I(G1))(Gs) Gk(G s)

Similarly, we can show that G^k

+

^s

GS(G k)

by using G^k

+

^s

GI(G

^k

⁺

^s-

1). Hence,

the results holds for k. Theproof^iscompleted bythe Principle ofInduction.

Theorem2 hassomeinteresting implications about the description of^an F-graph ^{as a}pattern.

Thegraph Gⁿcanbe described as G^rwithG attached,^foranypair ofnonnegative integers^r and s, such that r

+

^{s n. Also, weconstruct Gnby} attaching G

r,

to G

s,

for any r,s

>_

O, such that DEFINITION. We define equality in

F,

as a graph isomorphism. Addition

(+)

ⁱⁿ

^F

^is

definedasfollows:

G^r

+

^Gs

^Gr(GS),

^forall

^Gr,

^G

_

^F.

Itcanbe easily shown that

+

^iswell-definedon

F.

COROLLARY2.1

(Closure

^andCommutativity)

For

all nonnegative integers k and s, and for all

G/

andG^sin

F

v ⁺ v(vs) vs(v)

PROOF. The resultisimmediatefrom the theorem.

LEMMA

3 (Associativity)

Gq+

[G

^r

+

^G

s] [G

^q

+

^G

r] +

^G

s,

^forallG

q,

G^randG^sinF.

PROOF: G^q

+ [G

^r

+

^G

s]

G^q

+

^Gr

⁺

^{s Gq}

⁺

^r

⁺

^Gq

⁺ + ^Gs [G

^q

+

^G

^r] +

^G

s,

^forallq,r,s

>

0.

The associative property of

+,

implies that the order in which ancestors are added in the construction of a

descendant,

is unimportant. We can begin with any ancestor and attach the

others,

ⁱⁿanyorder thatwechoose.

Since

G

^Ois a

node,

thefollowing resultisimmediate.

LEMMA

4 (Identity).

Let F

beafamily ofF-graphs. Then G

O+G ^r=G r+G O=G r,

forallGr_F.

Thefollowingtheoremsumsupthe results of Theorem 2 andLemmas3 and4.

THEOREM3.

(F, +

^{is a}commutativesemigroup with identify.

Let us use the symbols

<

^and >, for therelations "is an ancestorof" and "is a descendant of" respectively. Then foreveryfamily

F,

the following result holds.

LEMMA

4 (Trichotomy). For any two elements G^r and G in

F,

one and only one of the following holdseither

G

^r

<

G

s,

G^r

> G

^sor

G

^r

G

PROOF. The result follows immediately from the definitions of ancestor and descendant.

Let us define a mapping from

(F, +

^{to the set N} of natural numbers under addition, ^as follows:

() .

INTRODUCTION OF F-GRAPHS ₃₁₇

Then for allG

r,

G^s

_ ^F,

/(a + a ) /(a ⁺ ) + ^/(a) + /(as).

Therefore

#

^{is a semigroup} homomorphism.

Suppose

that

?(Gr) dl(Gs).

^{Then r s, which}

implies that

G"=

G

s.

^Therefore

_#

isinjective. isclearly surjective. Therefore, is asemigroup isomorphism.

Hence,

wehave thefollowing theorem.

THEOREM4:

(F, +)- (N, +).

Theorem4 isthe crucialresult forcompleting the equivalence between

F

^andN. Nowwecan make parallel definitions in

F

in terms of

+,

by looking at definitions in N. For example, we definemultiplicationin

F

asfollows:

G^r.G G^r

+

^Gr

+

^Gr

+ +

^Gr

(s times)

G

+

^G

+

^G

+ +

^G

^{(r times)}

The roles ofG^OandG asequivalentto 0and 1 remainintact, asshown below.

G

O.G

^r G

O+G O+...+G

^O

(r

times G^O and

G

1.G

^r

G I+G +...+G (r

^times G^r Also,wehave

#(a

^r

a _(G

^r

+ a

^r

+ + a r) ?(ar) + (a r) + + (ar) (s times)

r

+

^r

+

^r...

+

^r

(s

^{times rs}

(Gr),(GS).

The following theorem canbe easily establishedinamannersimilar tothat of Theorem 3.

THEOREM 5.

(F, +

^{is a}commutativesemigroupwithidentity. Fromourobservationson

above,

^wecaneasily establish thefollowingextensionofTheorem4.

THEOREM6:

(F, +,.) (N, +,.).

Theequivalence ofFandNisnowcomplete. Westatethisresult inadifferentmannerinthe following corollary.

COROLLARY

6.1. F-graphsaregraph-theoreticrepresentations of natural numbers.

REFERENCES

HARARY, F.,

"Graph Theory", Addison-Wesley, Reading,

Mass., ^19(9.

HARARY,

F. and

PALMER, E.,

".Graphical Enumeration", ^Acad.

Press,

New York and London, 1973.