’ TRU Mathematics 15−1 （1979）
GRAPHS WHI（｝−I ARE n−th POWERS OF TREES
Takashi HAMADA
〔Received Jme 22，1979） ABSTRAer An algorithm is described fOr finding all n−th roots of graph G WhiCh are trees． To implement the algorit㎞it must be㎞own that G has at least one n−th root which is a tree． For this purpose we present a sufficient condition for a graph to have an n−th root whidl is a tree・ §1． Introduction Throughout this paper we shall use the gTaph theoretic notation and termi皿010gy of ［4］． Our purpose is to find an algorithm which produces all trees T砲ich areヵ一th roots of a given graph G． In other word5， we solve the gτaph equation a』ln， where C and n aTe fixed． A（；haracterization of graphs having an n−th root which is a tree， is easily obtained from ［1， theorem 2］． THEOREM A． A oo朋eoted graph C Uith p抄θ㌘tices ZαわeZed∂1．… ．びp）グαs αη η一th rooカ， η≧2， which is a tTee， if cnd onZy iゴ㌧ G oontains α ooZZeotion 「・｛G1・’”・Gp｝・fρ・・mp乙・カ・subgraphs such微力︶︶︶
臼一11⋮皿︵︵
〔血）’ （iv） ・i・Ci f・r azz z＝1・…・P； ％・Gτ⇔リゴ∈．Gi・f°アαzzち」＝1・…・P；・∂∈σ⇒鋤㌘θeSt8ts−・．ひ一Zinking L〔with ”・・ρ・・t t・
r）oμθ巧功ηoカθコceeedingηsuσh伽力uび∈鵬：uりQC ⇔が昭rθenists幽u，び一Z仇雇η9五〇f ZengがI M（m＞n）・
∫bアαZZ Z4， び一linkingS vith Zength≦iη， the 8Z4Z）9㌘aph ［伍 is oomz）Zete・ From now on， we suppose that the graphθsat isfies the conditions of Ttheorern A． The e）Φosition begins by considering the cases in whichη is even， and． n is odd． It is uユtimately showl that the 伽D cases can be merged in the latter stages of the algorit㎞． Several parameters are used throughout the pape「P。rl￨。：v瓢：fl：誌、蠕。’：。1。’：、：蒜〃壽：。、。ting．，h。㎝、．
P。i。，，。。d。nd・in。，。f T． A・d T（k） i・d・fin・d・indu・ti…y．・f・i・a・・…i・・ tree i．・．，Tn・G， th。n㌘（・）i・ca11・d th・axi・tree． P・桓t・・f th・a・・i・tree 1、 2
T．HAMADA
（r） are called the axis points． T is．Qften denoted by H． AS it occmSs thal there is a㎝e to one．corresp（mdence between the cliqμeS of G and the axis POints of a solution 〔see， Le㎜1）・we shall deng；e the a xis POints by ui・…・ ・m・The cliqu’e・・fθ訂・d㎝・t・d by C（1）・…・ C（m〕坤・r・C（i） ・・rreSP・nd・t・ui・Ndw・ we・hall gi『ve・L・㎜・1・［3， the・r㎝1］・ 〔1）㎞1・五・力乃・・tr・・cnd z・カ（芦♂ヵ・伽・−th・P・w・r．
MeかfoZZontng． hO Zd： ・（σ〕・（・（「））つア。i。。“。。． ！ ・（の・＠（・ω）〕” if・』磁． wh・r・σ（の．乙〔のCt…力乃・・z伽・9・，・rph・fθ⑳Ut the z碗9…rph・アら翅P・・励・一 （2） Zy． L㎝膿’1・h・ms廿股t鴫．αm・・品i由』th・p・桓t set・f・1iq・・9r・ph・fσ飢d that of axis tree． as id㎝tical ifηis ev㎝， and if n is odd the pomt set of the clique graph and of the line graph of the axis tree can be said to coincide・ The poillts of T not on the axis tree are called B−poillts． The B− points and the axis points to血idh any may be adj acent induce a subgraph of ㌘噸dl is a、fbrest． The trees of this fbrest are called teτmil田1 trees． 血ete㎝血1 t「ees a「e qen・t・d．by m1 t・％・by．ぬi・虫鴨鵬飢血t yZ i・att紬ed t°the ・xi・t t・ee ・t Ui・Of・・ぼ・e吃may b・t・iぬ1・出・eve・if
uゴis孤㎝伽血tノ゜f the axist t・ee・th・n d〔w．9）＝・・th・fi・・t p・就・f algorithm shows the methOd fbr finding the axis tree． The second part findS all tem皿1 trees． As it ha四㎝s， the axis tree is mi（luely（1etemined bア Gandη， whereas the terminal trees are not． §2． Finding the Axis tree曲enη is even Begin by s可）posillg that σ is given alld that ♂＝G has a solution tree． The cliques of G are delx）ted by O〔1），・．・， 0（加）；the poillts ofσat first by l to p．．Three matrices are usefU1． ． Fi「st・t品cli胆e int mat「ix㎝is th・（m，P〕一㎜t・iX（％ゴ〕r砲・・e・ピ｛：蕊θ
、To find the cliques of G㎝e can use the algorit㎞The clique intersection matrix C is the
％ゴ・o1：
if￡＝ゴ in reference【2】． （hls m）−matrix （a．．） in which t9 ifi≠ゴ，砲ere 9＝lV（a（i））∩iγ〔0（ゴ〕）1．GRAPHS WH工CH AREη一th POWERS OF TREES 3
The thiτd孤atrix is 竺］竺＿三≦1ユ三1三竺≡L，≡：一， an ‘η， m〕−matrix
（b．．t9）・ Lemma 2． tZVze nis points （1）o？（2）hoZds：％唖祝ゴ硬rα砺α゜鋤￠τ唖・°nZy if eithe？
（1〕 α・ゴ霊。α・・°’吻ηθ抄θ”’αik＞αピθ』α柵α㎡α諸ゴ・
〔2） α鯖鷺。α商゜「・wheneve「 ak・」・〉αピθ泌”θα碇η’andα・殻’
PR°°F・〔1）S卿s輌t a・ゴ＝、6㌫α・た・血㎝if卿dμゴa「en°t
adj acent・the「e is a path f「°m ui t°・ゴ・in the axist t「ee・』tμZ』a即血t °n the path between ・i and uゴ・Then V〔°〔i〕）∩7（°〔の）⊂Y〔°〔i））∩V（°の〕s°t地tαiZ・αiゴ・皿s c°nt「a血cti°n sh°wSぴatα♂、膿。α汲麺・ies
ui is adj acent’to祝ゴ・in the axis t「ee・ If ui andμゴ are adj acent・then O（i）∩0〔ゴ）＝たZ（Z≧・）・．・・th・t・ぽ・If th・re i・a’P・int tik・u・血that ・ik＞α幼th・nγ（o〔k）∩o（ゴ）〕⊂V〔°〔i）∩°（の）・h・㏄eα商≦αtゴh°1dS・ C・nve・・ely・if ・i ・nd ・g・ are P・t・qj acent・then the「e is a Peint ”k °n ・h・p・th b・t・・田u、 ・nd ・、・・Ac・・rd血・・y・（0〔i）∩C（k））・・〔・（i）∩・（ゴ））㎞1d・・ h・nce泌』泥・ik・α￡ゴ・伽・h・・㏄㎞d・・（・㈹∩b〔ゴ））⊃V〔°（i〕∩°（ゴ）〕h・ldS・ he・ce we have・縛〉・iゴ・B・t thi・c・ntradi・t・the assumPti°n↓松e「efb「e・ui and u．must be adj acel江． （2） is prσved similarly． 3 ’ We present an exa㎎）1e wherein we．．「aTe given〈；and we’find the axis tree． In Figure l we shσw the graph G（G＝T8」n＝8， r＝4，ρ＝lV（G）卜28）； in Figure 2 theclique point matriC（is shown；Figure 3 sh㎝s the cliqUe mtersect1㎝matrlx；
and Figuぽe 4 shows both the axis tree and its adj acency matrix． （n＝8 is the ，1east integer such that the equationσ＝♂has the most general solutions，see
§6 ［4］［ZI〕． G−Z8（n−8戸＝4・ly（釧＝as） Fig．14 ・ ・T．HAMADA ぶ CIique poillt matτix （〔（PM））
12345678910111213141516171819
e〔1） o〔2．） C（3）c④
C（5〕 0〔6〕 0〔7） 0〔8） 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1−1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 ．1 1 1 1 1 0 1 1．1 1 1 1 1 0 0 1 1 111100010
1①
0000000
ーム000000
11111011
11111011
Clique intersection matrix （（CIM）） C（1） C（2〕 C〔3〕 C〔4〕 σ（5） C〔6〕 0（7） C（8） C（1〕04319530
111
1占− 0（2） 0〔3） 14 13 0 1717 0
15 17 13 15 9 11 14 13 11 10 C（4）11
15
17
016
12
11 9 Fig． Fig．00000011
01000011
11．1000112
C〔5） 0〔6） C〔7） 0〔8） 9 5 13 10 ・13 9 14 11 15 11 13 10 16 12 11 9 0 13 9 713 0 5 3
9 5 0 12 7 3 12 0 3 Axis tree adj acency皿atriC（and Axis tree123耳5678
μμμμμμμμ
101000000 210100010
μ ．
301010000
L．00101000
500010100
600001000
701000001
800000010
Ul0000000
0000000
①①
u2 20 21 22 23 24 2S 26 27 2800001100
00011100
00111100
01111100
01111100
01111100
11111110
u3 lk u500000
①
00
U600111100
Fig．4
u7 Fig．4 u8 §3The constructi㎝of the axis tree when n is odd， n≧3． This case is handled s迦ilarly， the difference betwe頭the two beingGRAPHS㎜．CH ARE n−th・． ma． RS OF TR囲S that hefe we initially find the line graph of the axis tree． We define s°me mat「ices・Tl’e 1血es°fσa「e den°ted by f・・…・fg・ ［［be cli（胆eline㎜t「iX C is the mat「iX（Y萄）砲e「e ・ピ｛1ifぴ゜（iO othendse）：
コhe clique intersection matrix is defined as befbre．恥are then enabled to
・°「lstru・t the 1血e卿h°f the axis t「ee・Vith its ・djacen・；y mat「ix（β．．t9）・L・㎜3・肋吻励θ卿力・τ・Ut・加θθ・伽θθ♂s碗eθ品・θゴ
〔i・e・・βげ1〕・ザ励・吻iτ・…ア』f・ZZ・wi・σ・・nditi…．わZゐ：
（1）β・ゴ＝A㌫．、β・k°場望andβ紗ゴf°「 aZZ Z sueh微t B・・〉β・ゴ・
〔2〕β・ゴ＝A2㌫．、β匂゜鳴工唖β詩・』田鋤微力β兄〉β・ゴ・
Wh㎝the adj acenCy matriX of the line． graph of the axis tree is fbund鳩 obtain the axis tree by a theore皿of Krausz ［4］． An example is presentedbe1。w鴫s。1ve（把3．
1 13 56 T．HAMADA、 （（皿の
1234567’
W910i112131415
σ①
σ②
o（3−）o④
σ⑤
o◎
o（z） σ〔’8’）00001000
00011000．
°0011110．0
11111110000101006
010000，00°
9
1110．0000i
P
1111σ100
1110．0000
1000000010000000
0 0 0 ’O011・0111
000
01凸−占弓⊥0000011
00000
01占
（C瑚 σ（1）σω
c〔31）σ④
σ⑤
o（6） σ（7） σ（8） C（1） 044ク一
−弓乙10
C（2） 404212
−占∧U c（3） 4 4 04
2− 4’ 2 1 C〔4） 22403521
Fig・7
C〔5〕 1 1 230210
C（6） C（7） 2 12・452q31
﹁⊥フ●21307﹂
C〔8〕 0 01
1
0
1
3
0
一→
（kausi） ’ 1 一8 ＿＿ニーd「 ヱ 5一 8一 Hg：8 §4．qonstruction of the tem‡nal trees，η≡2r．Let”』』p°int・f・t・輌t・e・・tt・曲・d t…鵬qi・lfカi・th・
dis迦ce f・㎝パ・’．・i血丁・・e gi◎the cO・・d皿…（ui・疹）・・f…，・h㎝
v is On the axis tree？ pifferent points may be given the same coordi血ates，twp su血P°桓ts‘a「e ca11・d一陥us・n・tati・・胸・カ）t・・印re・ent
the set°f all PO血t・醐・…d皿t・・ロがカ）・孤d l・（ち，釧i・ca・1ed・ghe
GRAPHS WHICH ARE n−th POWERS OF TREES 7
聖〉・f （・i・t〕・ltmayh・PP・・t｝職t l晦・t）卜0・Of・・皿se
every terminal tree atta（血ed at an endpoint of the axis tree has maximal l・ngih ．r・飢d if l叫・カ〕1・0・th・n IB C・i・が）1・O f・r・all・・≧が≧カ・ In the fbllowings in this section， we assume thatγz is evel1・ Arl e（luiva−1ence relation is defined㎝the points of㌘． Ttgo points u…md沙are
eqμivalent if u∈V（0．（己）） 砲enever v∈ア（IC（i）），and vice versa． The points of T are thuS partitioned iIlto e（luivalence classes・ The eqμivalence of u，τ）is denoted by u∼び． Now if we identif）r each・et施諺・カ）t・a・i・g1・p・垣t泌9・t…present・ti㎝・f T・・an ・xis t「ee
with paths of length r attached at ea（土point， as shown in Fig．9． ・B（Ul，3） uθ Fig．9 Fr㎝this representation we shall construct all solution trees． Sinceu・、，u，飢d当are endp・int・・f the①d・t・ee・we㎞㎝t｝v・t昧￠・t）≠￠
fbr 1≦t≦4， i＝1， 6， 8． Other sets of congruent points may or皿ay mt be erXpty． We el頑asize that the points on this representation of the term血al trees correspond to sets of points． The representation is then partitioned according to our eqロivalence rela一註：，三lje：e°＆）。惣lt°：ft＝ytlle：。B㍑’㌫〕，三：㌧多1・r；；二〕1。t
・fp・血t・whi・h are at di・t・nce t・r less f・・m ・i ・nd th・・et・f p・血t・whi・hare at distanceがor leSs from u．are identica1． The criterion detemining
∂ whether points on terlninal trees are equivalent or not uses the relative sizes of t， t’，・n and the diameter of axis tree H， i．e．， 〈i（H）． The conditions are rather complicated． Figuエes 10 and ll show the partition． E（luivalence classes are enclosed by clOsed curves．8
T．HAMADA
Fig．10 一 D1 ￨”一 @ 島 r D11． @ ． E 〒．i @ 21 ， 臥 11 Do @ i 2’，﹁ 1ξ＋1 恒9．11 §5．The Parity of ηand Types of Equivalence classesS・tPPese ・h・ ・qua・i㎝ぽ・血…炉Z・…i・t・be…v・d・L・t％b・any
s°1”ti°n紐d 1・t夕♂be・・n・tru・t・d丘㎝㌘。 by・dd血9・・鵬叫・・＋1）P・血t・ f・r・eaCh…頑血・・＠ゴ・・）f￠・［［h・n・…ut・・n・f♂＋1・（・♂） n＋1has the same axis t「ee・as・T。・エf・n・・㎝・鴨・al1 P・血t・B （・i・・＋1）f・㎝…1碇i・n ・f♂＋1・〔T♂〕蝋，・h㎝㎝・g・t・a・・・・・・…f・h・・rig㎞・・q皿・・㎝・・♂・ So， it is sufficieI比 to solve our equations G−di fbr even n． The equivalence classes are divided illto fOur types．． （1）Aclass is of t；ypLs：．．：sLe E if it conrains only one B−p）int．（Fig．．10，11） （2）Aclass is of type毒if工t contains one B−Point and axis points． 〔see Fig． 10〕．GRAPHS岨ICH ARE n−th PO肥RS OF TREES 9 （3〕A・1ass i・・f tLypLtz．t SL・D if f・・aB−P・int砲Z・t）there exi・t B−P・i皿t B〔uゴ・3）（カ≠・fd・i＝ゴ）and B〔ui・カ）・B（μゴ・8）be1°ng t°every clique・ In this case， the set of B−poi皿ts and the set of axis points in the ・lass ar・d…t・d by｛B｝D。 and｛u｝D。・・spectiv・1y〔see Fig・11〕・ （4）A・1・・si・・f工鵬if fbr a B−P・int B（ui’t）血the class th・・e exi・ts ・tlea・t㎝・B−P・i・t B（・ゴ・．・〕（t≠・f・r i＝のin the’class and the class is ・・t・f・typ・D。・1・this ca・r・th・・et・f p・血t・B〔ui・t）・nd th・・et・f axi・p・血t・in the class ar・d・n・t・d by｛B（％・t）｝P、皿dω0、・e・pective− 1y 〔see Figs． 10， 11）． §6．Formias Which give numbers of B−poitnts in the classes of each type （1）
→
〔2） F19．1．2 First we introduce some special notation for the axis points・ Let’ui bean・・xi・幽t・・b・・h・d・gree・f ・i・and uゴ・…吻…・uh be the・・p°血ts
・djacent・t・ui（Fig・12〔1））・脆t・…f・・rm the皿ixi・・1 subt「ee°f the axis ．and has u．as an endpoint to a path， under tree which does not contain u t 3 the sa皿e conception of congruence as we dealt with befbre・ Si皿ilarly， we transfOrm the maximal subtrees about uZ， uk， ’°°・uh to P・th・・W・ gi・・n・w・1・b・1・in th・place・f ・i・・ゴ・…・uk・…・uZ as i・ 1・・ 2、・…・・、・u・h・that・d（・、）i≧d（2、〕≧…≧d〔・ユ〕a・Wi・ere d（k、〕i is the diliatnete「 ・fth・p・th， say P， mith・th・・rigi・i・nd p・・s th・・ugh・k、・・ th・p・int．°n P 諏i・；hi・at dist・n・・tf・㎝Zi・1ab・1・d kt（Fig・12（2〕）・N°te that p°鴫「n ls even．In the fb11・輌gs，鴨㎝umerat・necessaワf・㎜1as fr・m固t・［刀・
Proofs of these fo頂剛ユas are given i皿section 8．［1］lf姻＝°・th・n G i・a・・㎎1ete卿hκP・ ．
We assume that d（H〕≧1 in ［2］，［3］，［4］，［5］． ［2］Tl・e・numb・r， i・…㎜1tipli・ity lB〔ui・・一釧・f B−P・i皿t・in th・ ・ass°f type Eo・ F・・ea・；h a〔i・・i）・B（ち・）i・・f t）Tpe・E。： 巨］・．盈oフ1 ｜B〔i． r）lis oZ）tained direotZy f？om G o㌘ （CPM） （see Fig・ 2）・10
T．HAMへDA
（1）晒㎝8＝1，e￥，d（e）≧2， therl B（i， r−1〕 is of type EO 回．’”1・〔i・r−・〕トai、．r−ai、、・ ②ぬ㎝・≧2・1≦姪一1・・≧2・桓・a・e・f〔2SdCsエ〕≦・−1孤d 1≦カ・雲一2〕・r ．（4（r・〕湾「飢d1≦カ≦「−1）・B（’i・・一力）is°f‘ype E。…d vice v・r・a・ s 国’”IB（’・ 釧＝α・，・21i’（8−1）・i、．12、、＋一、一・・，．、2，一よ、・・、・kt＋i fbr 1声r−1， 臥”随・1）1＝a・．．、2，，、一・−1【3】N・mbe・・B（ち・−t〕mthe classe・・f触互・
It needs−to s≧2，η≧4 （10r≧2〕 hold， and（mユy B（i，1） （￠∈γ（旬）’can be’of type El・ 血cas．e・f d（・、）鍵一1 a・d ・d（2、〕言一1・ 回・”随・1）．1＝α・。、2rr、一・−1 1n cas・・f d（2、）i＝r−2 ・nd d（エ、）ぽ＠≧3）・ 囚2”iE（ち1）1＝α・t，、2，r、一α・．2，．，一・“1 ［4価・・迦b・・1｛B｝％1・fB−Peint・桓the c・おses・f・typ・・。・ 1βt 8≧2， η≧4， 〈ヱ〔日）≧1 B（i・t〕㎝・b・・f typ・ D。・’if ・nd only if d（1、〕≦カ・ In・’ca・e・f望（め・2Z≦π一4（1≦15r−2），η≧6 ana’S≧1・ し臥”1｛B｝・。1＝・、t2，−1｛u｝・。1 In case of 31≦d（日〕＝2Z＋1≦烈一3， 1≦Z文一2，η＞6 and s＞2． 固・’°1｛B｝〃・1＝α・，。12，−1｛・｝D・1 1n case of d（の＝1≦n−3，η≧4 and 3＝1 国3・・1｛B｝D。1・慨2−2・ Nbte． If i is an endpo血t of∬， d〔め≧2 and 1≦ヵ≦㌘一2， r≧3， it suffices t°・theck・XP． the t）弔・f（11・r−t）．・s桓ce at．1east昧・’fa−t；1〕・ B（11・で一力）h・1ds・［5価・．n血be・・1｛β（ち・一め｝Pil・f B一⑯麺t・i・・th…lasses・f娠ヨ・L・t
s≧2， η≧6， r≧3， d（日）≧2． For an integer ヵ（1≦ヵ≦r＿2），we ask fbr an integer 炉・（カ）・・u・品皿tit・ati・fie・・＞x≧1・d（り嘉力・1拠d∂（〔・・1〕、）iS・t・ In case of苫≧2，1etた＝1ダ2，．・・，x： 《℃ 、蕊二1麗、「−t）｝D・1＝α・’・’＋＠−1）α・’・・2’腕一α・，・・2，一・1、α・’・，。、−1ω〃・1・ 固・”1｛B〔ちr−t）｝〃・1＝・・、2，一・・，．、2，−1｛・｝D・1・、
GRAPHS㎜CH ARE n−th POWERS OF TREES
F・・tSd（21〕i＋1・in case・f㌘≧4・d〔2、）≦3孤d 4（2、）i≦d（1、）i−2・w・ ．have fbllowing fbエ獅ula： 回’°°1｛B（ちr一力）｝Dl 1＝α1’2，． i一αユ、＋1 a、．1−1｛u｝Dl 1−・ §7．Construction of Solution Trees Nbw we dete】mine the nu血ber of points in classes of each type （Fig．10）． B・t・the classes・f typ・DO d・n・t r・d・t・rince d（E）＝6＞5＝・−3〔by［4］〕・ （1〕Class EO：Fr㎝（（測（Fig・2〕鳩have IB（1，4）［・IB（6，4）131， IB（8，4）卜2， 1β（’・4）1＝°（’＝2・3・4・5・7）・砂四B（1・．3）1㌔、一慨鼻2−clL・＝14−13＝1・（・、2・13・t・・are fbmd桓（醐・Fig・』3）・S皿1・軌「IB（6・3）1
・6ゴ短＝％5−％戸3−12＝1・IB（8・ 一鰺＝句了一句2＝12−11＝1・by固・
IB（4， 3）1 ＝a3S＋α26一α25−a36＝15’9−13−11＝0・ E（…）・唖、・IB（…）1・・k、，−2−…68−3・3−3・・・…ce・・… IB（3， 2〕1＝IB（3， 3〕1＝IB（3， 4）1＝0． E（31）・by回、・1・〔…〕1・・k 4−・“4−2・…、6−・86−・・5−3−・… （皿）・・ass・、・・（ ¥）…3， i・・，・t＝・，・・塾・，・（・、）≧・，・・炉・． by ＠、， 1｛B（2・2）｝D・1 ＝α・i a，一・“−1鋤・1＝α48−・58−1＝9−7−1＝1・Acc・・d血・・y・血 ・（11）・IB（・，・〕1・・，1・（・，・）H・（・，・）1・・．・・nce，竺…IB（・，・〕1・ lB〔2ゴ 4〕1＝IB〔7， 2）1＝IB（7， 3）1＝lB（7，4）1＝o． ・（21）・s・3，i・・，…，・（・、）≧・・…，・d（・、）S・，・・炉・． By ＠， 3）1＝％k IB（3・3）1＝・・、、2、＋（2−1）・品砲、、4・＝aU、・・57一α52一αtS7・・5・9−・3−・・… IB（3・Z）1＝α5、・α6、一α65・9・5−13・1・ （・・〕・・ass・E、・E（o） IB（…）1・ak、4、一・k、4−3・…58一α68−3…7−3−2…
1｛B（2・・3）｝D・1’a・、2、＋（2−1）・靖一α晃・、一・、、q−1｛u｝D、1・・37・・hS−a47−a38−・・ 13＋9−11−10＝1． Hence， IB（1， 2）1−1， IB（2． 3）卜0． ・（31）・ IB（8，1）1＝1． ・（1）・ IB（8，2）1＝1． D（1）・ ＝9−5−1＝3 By ．国、・1｛β（7・2〕｝D、1・1・acc・・dingly lB（7・2〕1・0・ by固呈1｛み〔7・3）｝D、卜1・acc・rdingly lB（7，3〕1・0， by固・・1｛B（4・2）｝D・卜・h 4−a㌔・4一岡・、1・α、6一α、6−・11
2 1
T．HAMADA
・（P）・B・ M，
・（o・by ＠、，
1｛B（5， 1｛B（5， 2）｝D、1＝α，， ・，一αk・a−°＝・36−・・6＝11・−9＝2・ 3）｝D・．1＝α・、2、・一・U・、一゜＝aU6一α・6＝12−11＝1・ By at）ove calcuユation， we have a solution as depicted in Figure 13・ We canobtain other solutions by changing multiplicity：of B−points血the same class
・f・typ・D、・r・。・皿d・r th・ apP・・p・i・t・re・t・i・ti・n・F・r e・卿1e・anρthe「 solution tree of G is shown in Figure 14． Fig．13．L「
A u1 U2 衡 u4 u5 u6 u7 u8 49・14］］
−つ乙［［
§8． Proofs of Fo㎜ユas in the Section 6． This is easily verified． 口］ is also easily verified． 〔1） s＝1， i．e．，i＝ui is an endpoint of H． There exists one path ρ＝（i・ 11・12， ◆°°）・ since s＝1 and d〔E）≧2・ The point血ich is con− t・m・d垣0の∩0（11〕−0〔勾∩0〔12〕i・・n・B〔ち・−1）・h・nce B〔ち「−1） i・・f・typ・E。，・nd fb11・輌9・quality h・1d・・IB〔ち・−1）ト 1・〔°（i）∩°〔・、〕）1−IV「（°〔勾1∩°〔・、〕〕1・・i、、一αi、、・・hi・i・回・ 〔2〕 1・et B（i， ve一古〕 be of type EO・ If d（s1）i＝1 and r takes its least velue 2， then t＝1． But in this case B〔i’・−1）∼s・h・1d・・thi・i・ac・ntradi・ti㎝…th・t・ d（・ユ〕≧2・L・t 2≦d（・、〕≦・−1・S・pP・se血tカ≧d（・、）i・th・n召〔ち・−t〕ha・a…Iuiv・1・nt P・血t… that 1≦t≦d〔・、〕i−1≦・−2・In・qualiti・・d（・、）i≧・・1≦t≦’−1 areGRAPHS WHICH ARE n−th POWERS OF TREES
13
obtained si皿ilarly． The converse is easily verified． He・e・給int・・duce n・w n・t・ti・n・・｛id＜1｝（i・V（め）is a set°f p°ints 砲i・hhave di・t・nces fr・m i n・t gr・at5・ than Z・n T・and・｛id．Z｝〉・i・ th・・ubgr・ph・fθ・spa皿・d by th・p・血t・・f｛id．Z｝・Eq・・lity−’． ・｛id．。｝y°（i） h・1d・by t輪abbve d・f血iti・n・−N・w・声es』11P・・v・国・f・㎝2エ〔・、）￡望一1狙d1≦ご一2・鴨㎞泥
0（1t）∩0（2t）・〈｛iden．t｝〉…①・0（lt＋1）∩0〔2ヵ＋1〕・＜｛id〈”．t．ユ｝〉…②・ and・（・t．、）∩1・（2チ・｛id．，，．か、｝U・｛・、d．。．レ、｝・…③・う・rた・2・…・㍉・・ we have O（1t〕∩0〔kt．1）・云｛id〈，，−t．ユ｝urkld〈r．t．1｝〉…④・Fr㎝①and ②・we｝tave l 7〔0（1ヵ）∩0（2tj）1−IV「（0〔1t．□∩0（2t．1））1・1｛id”’．t｝1… that ． ・・，・，一・x・峠、＝1｛”・…−t｝1”°⑤・F・㎝①and③・we have
｜V〔σ（lt）∩・（2t〕）1−17（σ（lt．エ）∩・（2t））H｛id！。−t｝・（｛1、d．，．凶・acc・rding“ 1y・α1，2，一αユt−i 2 t＝1｛id・r−t｝∩｛11d＝r−t＋1｝1…⑥・Similarly・fr㎝① and④α1，2，一α1、kt・1＝1｛id＝r−t｝∩｛kld．．．培｝卜…⑦・（k＝2・3・・…・8〕・SuM・・rP・equalities・f⑥and⑦，and apPly⑤，then
ssa
?f2’一〔α・，、、2t㌦1、α・，た…〕：1：：；；2籔：ll：）：「lt！，・一釧． s The「ef°「e・臨’一釧＝α・，・’t＋（s＿1〕α・，．、2肘一α・t。、2、− 求?Aαi，・kt… This is ［匡〕， （see Fig． 15〕．If・d（・、〕夢・nd 1≦’t≦・−1・…bt・in−f・㎜1・固・
● ＼，，一 C（1，）i∩tCC2t） C（2t） C（kt＋r） C（．lt＋1）1∩IC（2t＋1） kt＋1 Ng．15●
14
T．HAMADA
［3】B（ち1）i・・f切・E、if’孤d・㎡y if・・岨ti皿・ω4（・ユ）≦・・1・
∂（2、）≧−1・r’（B）h∂（2、）i＝・・−2・d（1、）ぽ（・≧3）知1d・Fi「st we sha11 sbOw ・uffi・i・岬・㈹d（・、）≦・−1 is e頑斑tly・ecessary・S卿se廿・・t・d（21）ぽ一1・mthi・ca・e微e exi・t・ap・血t°f aXis t「ee・
砲i・th・i・ eqUlvalent・t・β（ち1〕・say・、・蹴n・B−P・桓t・c・n be ・qui・a1・nt・t・B（ち1）・S・・B（ち1）i・・f t）？・E、・．（B）S卿se t』t d（21）β一2（Y≧3〕㎞1白・〔・）（la・e．r−3・血㎝d（2、）i＝1・if d（1ユ）”‘2・ then・w・・h・v・・B（i・1）一β（1、・1）・皿t thi・i・ac・nt・adirti㎝・s°dロtd（1、）≧3㈲・（b）（ns・・≧4・lf d（2、）β一3・th㎝鳩』
β（i・1）・B（11・1）・thi・i・c・nt・町t・th・a・・卿ti。・… i・d（2、）i＝・−2・ If・d（1、〕碁・−1・・g・in we ha・・ a c・・t・a血・ti㎝…伽t』d（1、）梧…血e necessity・i…bOwn・by・th・fa・t th・t・t 1・おt B（ち1）∼・、㎞1白・b・t．the「e are no 日一points e（叫valent to B〔i， 1）・ ft・・f・f回、・W・ iPve・（1。．、）∩ヒ〔2。．、）・・｛㌔．、｝・・而・・ig比・id・・f． this equality is a cc唾plete griph on s＋2 points’ B（ち1）・ち1、・2、・…・・、・H㎝ce・鴨』v・ lyて0（1rLl）∩σ〔2r＿1）〕1＝1β（ち1）1＋8＋L・ 血lus 随・1〕lr・1、．．、2；，、一・−1・ lt・・f・f回2・恥廊σ（1。，、）∩σ（2。．、）＝＜｛娠、｝・∪董1、d〈、｝〉綱 σ（1。〕∩・0（2。．2）＝＜｛lld．1｝…脈・〔σ（1，三）∩0〔2，．b））一 （C（1）∩・σ（2，．2〕）・〔・石・mp1硫e．肝卿㎝輌並t・・∂（ち・1）・ 2、・…・・、）・㏄・・曲9コylγ（σ（1，．、）∩・〔2。．2〕〕1− 1γ（o（1，）∩・・〔2。．2））1・IB〔ち1）1＋・−1・． ts・IB（ir−1）｛＝α・，．、2。，一α・、2，，，−s＋1・ 【4］Ifβ（ちt）−∈．∩0の， then・the・e．・XdstS at least ・ne・B−P・血t Bσ・・、（ぴ。，fb・ψ＝きq血W・泣t・B＠，め，触・≦⑭≦・−3皿・・t・h・ld−
lP…f・bf ’N、・国，・・国3訂e eおi・y・carried。碇・W・・ve・ify・・nly・f・・国・ （・ee Fig・11）・d（H）・2Z・1≦π一3・8−3・5・hence Z＝2・・＝2・i（咋）・ ．2ト囮D。1・ 1｛・｝・。1＝1・（・（1z．、）∩・（2z））1−1ωD。1’＝al ’1十’1．’ 【5】（1）（ぬt｝le・・1uti・n tree T w・ q・t・輌・th・．・1・｛・・e・・f t）rP・Dユ・孤d nu血bers of point in these classes． Let B（i，㌘）be a B−point in a te血1 tTee・lf・・1・th・n・B（ち1〕i・・f触、宮。・．If・”2・β〔ち2）i・・f・typ・E。・鎚d・（ち・）i・・f．触8。プ6r．弓㌶興・．輌姻＝1・B（ち1）is・ft四・
D。・H㎝ce鴨may ass珊趾健6・．・≧3．・．4（∬！≧2・lf 8＝1・then at least ・（i・・）・B（・、・2）・tmd．d・g（1i）・S≧2・・血C・d（め≧2・H㎝ce・鳩㎜y’ass㎝・． that η≧16， ヱ・三≧3， 8≧2， d（且）≧2： The conditi・n・fb・B（ち・−t）t・b・・f t）rp・ D、 ar・（1）、孤d（1）2・GRAPHS WHI〔H ARE n−th POWERS OF TREES （1）1 B〔ちT−t） t「・・f・f（11）・ When 2＜r＿t＜？＿1 （1）2B（i’1〕 fr・・f・f（1）2・ ， i・・ftyp・D、∼‘d（・、〕EtEd〔1ユ）i−1
〔司S・rPP・・e血t 4〔1、）≦輌1d・・th・・B（い一t〕is°f
typ・D。・・血ce・d（め≦2t≦2（・−2）＝・−4（・e・［4］．°f this sec− ti・・）・H㎝…d（1、〕i≧t＋！・S・rPP・se th・t d〔・、）τ≧t＋1 holds， then B〔i，？−t）cannot．have an e（lulvalent B−po皿t， contradicting the assumPtion． 〔d〕 The converse is easily veTified． （2〕 In any class of type ヱ）1 〔ゴが品∂・’…・ ・一刀E・一培・一古≧…㎞1ds・甦lf順f血d th・high・・t p・int血aclass・f type D
suppose the class is determined． The pヱ℃of of existence of the highest point： SupPose that there are at lea・t蜘・p・血t・ちゴ㈱）wh・・e・−tx・・e・m・xima1，血｛B（⑳・r−tx）｝D、・ Let the maximal value be㌘一t． Then B〔i，アーt〕∼β〔ゴ， r＿t）， （2≦アー，t≦r−1）． i・・ft）P・D、e d（2ユ）＋3≦r≦d（1、）i （ゴ〕S・rPP・se th・t d（2、）i≧・−2 h・1dS・ ・fd（・、）i・・−2・r・一・・th・n・〔ち1）i・・f type D・and if d（・、）i≧・，・he・・（ち1）i・・f・yp・E、・迦・・d〔2、）≦・−3・ 〔r≧4）・1・thi・ca・e， if・ne・et・d（1、〕≦・−1・th・n B（i・1） i・・f・typ・D。・th…fb…d〔1、）il・・mu・t h・1d・〔色〕 ・〔i・・〕一・〔・、・2）・…（i・．1）i・・f・typ・D。°「D、・血d・B（i，1）Pt，・・it i・mt・f t）rP・D。・i・…B（ち1）is°f
t）「pe Dl・ ・ ・・就・桓ing B−PO桓t・（ゴα・？−ta）・’ th・・e exi・t・m麺・B−P・血t B（㌔・・一古。〕・u・h that th・B−P・i皿t B〔i。・・一㌔）i・ca11・d th・highest then we may 1， L・tth・n・ghbO…fi in・・xi・tτee b・1、・…・・u、・…’・・、〔1≦u≦・〕・ （i〕S・tゴ・uZ〔u≠・・Z≧・）・thgn・（i・・−t）∈C〔1t〕・B〔」・・−t）∈C〔lt）・hence B（．ちr一力〕？6B（ゴ，τ一力〕，this is a contradiction・ （ii）S・tゴ・・Z（Z≧・）・脆di・id・i・t・three ・ubca・e三〔a）・fO）・（c）・ （・〕d（2エ）i≧ちth・n・B（i・・−t〕∈・（2t〕コ（ゴ・・−t）∈°（2t）・hence B〔i，r−t〕76B〔」， r−t），this is a contradiction・ fO）・f d〔2、〕i・カー・・〔t≧・）・th・n・〔い一t）？6B（1、・・−t）・，since d〔1・〕i≧t＋1・ If・t≧2， th・n・B（i，・−t）∈C（2t．、〕・nd B（ゴ・・−t）て゜（2t．、）・｝’ence B〔i，ユ。−t）吻．〔5〆fa−t）．，．theSe contradict the．assumption・ （・〕・fd〔2、〕i≦t−2（t≧3）・th・n・〔i・・一か召（1、・・−t“1）・but this contradicts the assumption that B（i， r−t）is a highest point of thi・．・・・…ft）rpe・D、・H・nce・d（2、）ilt−1・C・n・equently・this case reduces to 〔a〕， （b〕． 卜 Thus， the highest point is uni（lue・15
16
T．HAMADA
〔3）L・tu・tak・any・i〔文）・A11が・whi・h give th・highest・P・int・・f
｛B〔i・ r−t）｝D、（2y−tsr−1）ar・decid・d・・fb11㎝・・ 〔1）ln ca・e・f d（2、）i≦・−2・〔・）if d（2、）t＝d〔1、〕a ・nd d（2、）i・d〔・、）i・ then d〔・、）t≦e≦d〔2、）i−1・〔β）if d（2、）i≦d（1、）i−1・th・n d（sユ）i≦tsd〔2、）i・（β’）if・r≧4・d（2、）i≦・−3・・nd d（2、）i≦d〔1、〕i・−2・ th・n斑（21）i＋1・ （II）ln ca・e・f d（2ユ〕i≧・−1・ Proof of （3〕：Proof of
固： cases（A）and〔B）・（i）（A）x＝1（t＝d（2、）i皿〔β）〕・ have O〔1t〕∩0（2t〕＝＜｛㌔．。．t｝・・0（1t．、）∩0（2t〕 ＝＜｛％．，．t．、｝U｛1、d．．一ヵ：、｝・・acc・rdingly ｜V〔・（「t）∩・（2t））1−Tv（・（1t．ユ）∩C〔2t〕）1 ＝1｛．B（i・・−t）｝D、1＋1’｛u｝D、1・H・nce l｛B（i’・・−t）｝D、｜＝ α・t・t−aユt．、2，−1｛・｝”・1’”固・’（B）ag2． We have C〔1t）1∩0〔2t）・＜｛id〈r．t｝〉…①・C（1t＋1）∩C（2t＋1）・ ・㌦。．t一工｝…②÷C（・t．、〕（・〔2ナ ＜｛・ ＝Zd≦r−t−1｝∪｛1、c（S．．t−・｛…⑤ x・we』°（lt）∩°〔kt・・）＝く｛id≦・−t−・｝U｛k、4≦・−t−・ d（・、）≦y−2・（Y）d（・ユ〕i≦t≦・−2・ We give a p「°°f °nly f°「（1）（・）・By（1）ユ・〔1）（・）（and all other cases in （3）） satisfy that B（i，？＿t） （1＜t＜r＿2） are the p・int・in a class・f・typ・D、・S・rPP・・e th・t B〔 z）？−t） is not highest point fdr some t in sipte of t satisfies （1〕〔or）． Hence， we can assume that there exists an integer乏z〔s＞u＞1〕 such that B（i・ ・一かB〔u、・・−t＋1）（・≧u≧1）・…〔δ）・lf・望≧2・th・n B（i・・−t）∈0（lt）a・d B（u、・・−t＋1）1・0（lt）・If炉1・th・n B（ち・−t〕・0（2t〕・B（uユ…−t＋1）∈・〔2t）・S・・it bec・me・ t・刀（■t，？−t）卿、・・−t＋1〕…t・adi・t≒th・a・・urTIPti・）n 〔δ）． Thus， B（i， r＿t） is the highest point． For t of （α）， 〔β）， （Y） in 〔3），we subdivide into two WeForた＝2，3，…， ｝〉…・
④
Fr㎝①，③鴨｝遭ve
（0（1 t）∩°（2カ））〔〔0〔1t．、）∩σ（2ヵ）〕＝〈｛㌔，。．カ｝・∩｛1、d．．。．カ・・｝・according1γ
1・（0（1t）∩・〔2，〕）1−1・（C〔1t．、〕∩・（2、〕）卜1・・〔・｛㌔．，．t｝∩｛1、di．。．，．、｝・1・Hence
・、，、，一・、，＋12，＝1・（＜｛id．。一・｝∩1、d．，，…｝・〕・・⑤・S迦Zlarly， fr㎝①，④，おrた・2，3，…，x， we have
GRAPHS WHICH ARE n−th POWERS OF TREES
