CUBO 11, 07-11 (1996) 
Recibido: Abril 1995. 

Harniltonety and automorphirns group of graph 
preserved by substitution. • 

Eduardo Montenegro V. 

Abstrae t . 
Thc sube~itutlion is a graph opcration. This o pcrn.tion 

con!'{ists in rcplacing a vertex by a gTaph. The A..im of ti-his 
work is to analizc thc pr cscrvation o í ccr tNn prop<:rtics in 
thc substlit.utiion of o. graph. Spccificall y, thcsc propcrtics 
a re: (i) hnmiltoncty o.nd (ii) group o í aut.omorphis ms of n 
givc n graph C. 

lntroduction 

T hc graphs to be cons idercd will be in general si mple a.nd finitc, wit.h o. nonempty 

set o f cdgcs. For a grnph G , V(G) deno te thc set of n : r tice5 and E(G') denote thc 

~t of cdgcs. T hc cardinafüy of V(G) is CRllccl o rdc r of G a.ne! thc cnrdinaJity of 
B(C) i5 cn.Ucd s izc of G. A (p , q) graph has p ordc r and q s izc. Two vcrticcs u 1.m d 
U IUC callcd n c ighbOr.9 if { 111 U} is (Ul edge OÍ G. far l\O)' VCr t.cX U OÍ (,' , de note by 
N ., thc set o f ncighbors of 11. To sim plify the nott1.lion , l\Jl cdgc {x, y} is writ.tcn 

M :r:y (or yx). Ot.hcr concepts uscd i11 Lhis work 1rnd no t dcfincd cxplicitily can be 

found in lhc rcforenccs. 

' PMtW ~i. by DGI U PLACEO, Proj«:l 1Vo 1394~. 



CUBO 11 E. Mont~tgro \f. 

2 The subst it uti o n 

Assu me lhal e and K are two di sjoint graphs by \'C rLi ces. Fo r a vcrlex V in V(G) 
a nd a fun clion S: N,, - V(K) it will be deflned th e s ubs titut ion (9] of the vert ex v 
by the graph K , as the gmp h M = G(v ,s) K s uch that: 
( I) V ( M ) ~ ( V (G) u V(K)) - {v ) and 
(2) E(M ) ~ ( E(G)- (vx 'X E N0 } ) U (x•(x ) 'x E N0 ) 

Thc ve r tex u is s aid to be t hc ve r tex s u bstit utcd by K in G undcr t he fun ction 

·' and thi s function is cal led of s ubst it ut ion . 

Now let v1 ,· ,vn be thc ve rt iccs of a graph G ami H 1 , , fl,, a seq uence of 

graphs with no co mmon ve rt iccs runong themselves o r with C . lt will be de not ed 
by 1\h = 1\IJ,_1(v1:,s1:) flt t he graph which is obtaincd by s u b6t it ut ion of k ve r tices 
of C by graphs H., 1 :S i :S k, whcre Mo =C. In o th c r wo r ds, M 1 denotes a grap h 
obtained by s ubstitution of on ly one ver tcx of G, M 2 denotes a grap h obtained by 
s ubstitution of on ly one ver t ex of M 1 , and so on. Note that cve ry vertcx substit u t cd 

musl bclong to V( C). 
lt can be said t hat a n e<lgc of th e s ubslitut ion Mp is a.n i nte rna l e d ge if 

it is oí l hc fo r ms s , (x)s;(y). T he edge in M,. that are not interna! edgc will be 

nomin ated c xtc rna l edge. Lc t G be a graph whithout i30 lated. vcr ticcs. lf ea.ch 
vcrt cx u of G is s ubstit uted by a grap h complete with va.l(v) ve r t ices, t hrough 

a n injcctivc function, it will be said t hat t hc graph e ha.s been e xpanded. lt 
will be no tcd s uch grn.p h by G. To be wo r th whil c to obse rve that thc typc of 
graphs const ru ctcd by Sabidussi [4] will be iso mo rphi c with the expa.nded grap h 

co ns tru cled by s ubstit u t ion. 

3 T h e proble m 

Let G bes (p, q) grnp h , conncctc..~, ha miltonca.n a.mi 6(G) ~ 3. 
lf { S , } is a s cq uencc of grnp hs with no com mon vc rt ice:i a.mong thcm.~l vcs nor 

wilh G, thcn 
(i) Is M"(G ) h1un ilt one1m? and 
(;i) Aut (.lf,(G))"' Aut.(G)? 

3.1 Comp le te grap b case 

In this case G is n co py of t hc co mpl ete grnph K 1" p ~ 3, a.nd {S, } is a scq uencc o f 

jtl'f\ph.'I with no co m mon vc r ticcs tuno nR lhc1n.<1eh1es nor wilh C whcr Ct\ h S, is a 



Hamilt o 11c ty 11.ncl . CUBO 11 

copy o í 1\ co mplete grnph (or CA.ch S, is a copy oí a cyclc) . 

Thcore m 3.1 /,,et G be a co p11 o/ the com plete grnph K,., p ~ 3, wlwse vcrticcs 

are labeleti vi. · · · , vp and { S¡} is a "cqucn ce o/ grnplu u·üh no common ve rticcs 
11mong t.h c mscl.t1c3 n o r wi.th G, wh ere cach S, :::::: K~_ 1 , t.hen 

( i) M,.(G) is n hnmiltone.an and 
( ii} A ut.( M,(C))"' Aut.(C ). 

Proo f 

(i) S incc C is 1\ complete graph thcn it has a gcnerator cycle dcnotcd by 
C(C). Also cnch S; havc a gcncrntor cycle dcnoted by CM (C). Through an 
suitablc ~lcction oí t he s ubstitutfon íunctions, thc cyde C(Mr(G) ) d efint.-d by 
C(M,.(C) ~ Li,'. 1C(') (C) is o. gcnerator oí M,.(G). 

(ii) T he o nly one adm i.ssiblc movemcn t in M,.(G), through a symmetry of its 
vert ices that preserve edgc, are thc induccd by symmetry of Lhe vcrticcs o f G 
dun preserve cdgc. In fu.et t he interna! cdgc of a block o f Mr(C) only may be 
intcrcliangt.'<I by interna! edges o f o ther block o f M,.(G ) !J2]. By t his rea.son G und 
M,.(C ) luwc thc 31.~mc group of automorphisms, S,.. • 

Tboo r o m 3.2 Ld G be a copy o/ thc comple t e gmph K,., p ~ 3, whosc t1erllccs 

nr'C labclcd 111, • , ur nnd { S;} is n seque n ce o/ grnplu wit.h n.o co m mon verli.ce8 
n mong th e m.3cfvcs not• with G , whcre eac/1 5 , ~ C,,_ I • tJien 

( i) Mp(C ) is n. hn.milloncn.n a.nd 
( iiJ Aut ( M,. (G)) not. alway.'J is i3omorphic un'll1 Aut.(G). 

Proof 

(i) Since C is a complete graph then it hR.S a gcncrator cyclc denotcd by C (G ). 
Thro ugh an suiLnblc sclcct.iion o í t hc subetitution íunctions, ~he cyclc C(M,,(C)) 
dcfi ncd by C(Mr(G)):::::: Li¡'. 1S1 is n gcncrator of M,.(G). 

(ii) By cx nmplc, i f Gis thc co mplete graph K!. thcn A ut.(.M:.(G)) is Lhc dihedrnl 
group of ordcr 10 (Mont.,Scicnliinj, whi lc Aut(C) :::::: S:,. • 

J.2 Regular g raph case 

Tbcorcm 3.3 /,,e t G be a hamiltoncan grnph. r-n:gular, r > 2, whos c uerticC.'J 
11re lobelcd 111, • · , u,.. !/ {S;} is a .sequ en.ce o/ grnph.3 wi1h n.o common vcrticC.'J 
amo ng t.hcm.3elves n or wil.h C , wh crc cn ch S , ~ K ""'(~). t.h cn 

( 1) .H,.( G ) '·' hn..millommn nnd 

( ii) Aw ( M,(C))" Aut.(C). 



10 CUBO 11 

Proo r 
(i) Since G is a h1UT1iltonea11 graph lhe n it has a ge ne rator cycle de notcd by 

C(G ). Also cl.\Ch S; havc a gcnerator cycle denoted by c<1>(G) . Through a 
su itable sclection of the s ubstitution functio ns, th e cycl e C (Mp(G ) ) defi ned by 

C(M,.(C)):::::: u~~ 1 C(i)(G) is generator o f Mp(C ). 
(ii) The o nly one admissible m overnc nl in Mp(G), t hroug h a symmetry of its 

vcrtices that preserve edgcs, a.re th e induoed by symmetry of th c verticcs of G that 
preser ve edge. In fa.et the interna! edge of a block of Mp(G) may be intercha.nged 
only by internal cd ges of other b lock of M,,{G) [1 2]. F'or this reason G and Mp(G) 

have the same group of automorphisms. • 
Thoorcm 3.4 Let e be a hamiltonean gmph , r-regular, T > 2, whose verticc.s 
are la beled 11 1 , · , vp. lf { S;} is a sequence of grop/i.<j with no common verticc.s 

amon.g t11 e m.<J elves nor with G, where each S, ~ C .... 1(ur), th en 
{i} Mp (G) 1'.s a hamiltonean and 

{ii) Aut(Mp(C)) nol always is isomorphic wit.h Aut.(G). 

Proo f 

(i) Sincc C is a hamilt.oncan graph then it has a gene rator cycle denoted 
liy C(C). T ltr uug h it :m ilitUh: :;e\t:ction uf tln: :;u\Jstit.ut.iou fu 11 clio1i::;, t.ht: cydc 

C( M,(C)) defined by C(M,(G)) ~ uf,,, 1S¡ is generato r of Mp(G). 
(i i) ls obvio\Ls accord in g with Theorem 3.2,(ii). • 

R efer ences 

llJ Baba i L. O n lh e múti m un. ord cr of gmph s with giue n group., Canad. Mat)i. , 
17 ·167-<70 (1974}. 

{21 ylcy A. Th c 1.h conJ of group s , gmphical r"e prese n.tation, American Jour-
1m l o í Mnt.h c m1\t.i cs, 1 174- 1 76 (1876 ) . 

l3J Fh1cht R. // e r-s t elltm.g 11on graph en. mil uorgege bener abs trnkte r groppe, 
Co m1>00. ti o Mt\t.h. , 6 239-2 5 0 {1938) . 

{4) &b idu &q i G . C: mpM 111ith give n group and ginn gru.11 h th eo ri ca.l properties, 
C ""nad . . l. M1\t h ., 9 515-552 (1 95 7) . 

l!>J Abiduss i C. et Al. ( K oll lU' , F'rMkl , Babai ) l/nrmftonion cub ic grn ph.s and 
centmlúflrS of in.uoluli on_, , l\ nd . J . M&lh ., 31 458-464 (1979) . 



<p.,Cu'.~ 

rtro!:/111" 

CUBO 11 11 

[61 Powcr O. So m e hamillonian Cavley Groph.:J, AnmJ s of discrctc Matrhcmat-
¡.,.., 1 129-140 (1986). 

[7J C hR.rt rn.nd C ., Lemiak L. G'rapJL!I tmd Oigropks, Wll.dsworth and 

Brooks/Colc Advanccd Boo ks and Soítw!U"c P&cific C rovc C.A., (1986). 

!SI Codsil C . Cmph..~, Gmup and Polyto pea, Combinl'lLoriELI MRt hematics V6, 
Camberrn , {1917}. 

l9J Mo ntenegro E. Cmph 1vith givcn A utom o rphi.mt C roup and giuen Nuclc<w 

N umber, Proyecciones, 11 N !l 1 21-28 (1992). 

!IOJ Monl cnegro E., Powcr C., Ruiz R., SalfLZl\r C . Automorphi.sm G'roup aná 
lanmilt.on.inn pmp(wlie~ pre~erved by .mb.st ilut io n, Scicnt.ia, Serie A: Mnth. 

Scic nccs, •I 57-67 (1993). 

[l lj Mont.cncgro 8 ., Sala.zar C. Hnmi/tonúm pnth o/ .\'ft - 11, Revisen Técnica. 
lng. Uni v Z11lin, 16 N!l. 1 27-33 {1993) . 

(1 2J Mo nLcncgro E. A re.mll about tl1e irtcid cnt edge• in tJ1.e grnphs Mi,, Oiscrctc 

Mt1. t hcmn1.ics, 122 277- 280 (1993) . 

Dirocci6n del autor : 

l nstli tiuto de Matcmáticn 

U'11iversidnd Cntó licll d e VnJ¡>N'aíSO 

C nsilln 4 05 9. Vlllpuraíso