ON A FEW CLIQUE−GRAPH EQUATIONS
Iwao SATO （Received Nbvember 10， 1978〕 Abstract We shall give the solutions of graph equations C rL rG））＿C」C（MrG〃＝G and cr夕rGノ）＝G． 1 Definitions AIl graphs which we treat in the paper are finite mdirected without nrultipule edges a皿d loops・ We denote by VrGノ。ErG） the vertex set and the edge set of a graph G」 respectively． 〃rO／ ofσ is an intersection graph St（F／3where 匹｛｛・｝1・∈γrω｝U醐・Definiti・ns・・t・presented・here， may b・f・md血［3］． 2Theorems th・・r㎝1th…Z・ti・n 9・qph G・f・9・uph・〈櫛鋤c伍rG〃−G i・the・鳩 graphs whi・h・atisfy f・ Z Z・・7ing』θθ・・nditi・η8ω。r2ノαnd r3方 ωne deσree・了⑳ery ve？tex・了G isαカZeast tU。． 「2／be・iY P・ir・かω・励・ηgZθ8・アσ・is e・ig・臨ゴ・仇力． 「3／Ev・rg tni・ngZ・・f G ha・e・a・tZy…vertec・f d・ev・・鋤． f「・。f〔・→SupP・se thatθis a g・aph satisfying th・three c。nditi。n，． Ifσh・・n・t any t・i鋤91・， th・n the eq・・ti・・CrLrG））−G bec㎝・・0・rG）．G． ，ince in thi・ca・e L俳・rの・Acc・・di・gly，・（L‘σ〃＝G h・1d・if飢d・nly if・v。ry ve「tex・f C i・・fd・g・ee at least t・。 by（【1］，S・t・4）． W・m・y・・n・ider i。 th。 f°11。・i㎎・ca・e wh・nσ・・nt・ins t・iang1・・． C…truct th・1i・・g・aph．LrGノ。f σ・ｱen the「e c°「「es恥t。・v・ry・・i孤・…」rゴ・・・・・…随・一・ry
ve
Ftlcesり声・…・s） excePt f・r v・・tice・・」rゴ……・・）・f d・gree加・・n・h・鵬e。1「1瀞跳；ll・熾蹴さ；・。ll：1嘘elllse竺1N認1認aa「e
mapPil19 φ of VrG） onto VrC（L rGノ）） as follows：恥羅i；i篇蕊illl：欝i；：d：蕊；膓’一・1・
（・〕th・ma即ingφi・abij・cti・n・f VrGノ・nt。 VrOrLrσノ〃．1鷲・ご惣2二1㌶ぷ跳罐。㌔
3132 1．．SATO ．1 adj acent in o rz｝rσノ）． （・）L・tb・th’∂k・・〆k・ゴ」・・…・・ノb…tvertices°f deg・ee tw°°f t「i孤91es
聯蹴ム，a霊慧’nG⇔X晒侮ソ͡ 〉φ「桝d
Fr㎝（α〕，（β〕and（Y〕，we know thatφis an iscmK）rphisin of G o直toσr乙rG〃． Therefore， the graphσ satisfying three conditions （1）， 〔2〕 al且 〔3〕’satisfies the equation C CLCG）▲−C・． 、 ←〉） Let G sa土isfy the equation OrZ｝CG）ノ＝G and conaition （2），except・for （1） or （3〕． If all vertices of a triangle of G have degrees greater than ltwo， th・・1@we h・v・0．r五rG〃−G⊃K4（Fig・1）・Tl・i・c。就radi・t・t・．（2）・｝le・ce・at m°st σ 、 、 @ @ @ @ @ @ @＼ @ @ @ @_、一
、 ●9，−⑪‘A’．一
／ 一 @ @ @ @ @hか
@
@
@
@
@
@
@．
^
’G
℃ げ O‘ L（G） 、b
C（T（G）） （Fi・9．1） two vertices of evefy triangle are of degree・greater than two・ Then， a cliqUO 1ζof 1｝（G） ’is one of the following（c．f．［4］〕： ． （・）K−Lr・、，ρr。ノ＝＝K，r。ノ・砲・・e eith…醐G”is°n a t「i㎎1e鋤ρf∂ノ 華．．・rびis・n n・tri孤91e飢dρω≧2・ 〔2〕醐・ゴ）’「ゴー1・…・・）・油・re『｛ち・…・T．｝is a set°f t「iangles°f G・’ Now， we consider the follσwipg mappヰ㎎ψfr㎝V（C（LでG川toγrω：‡f醐ち。ρωノ・κρω』th㎝ψω⇒・ ’ ．．
if X≒Z｝r㌘J r右2⊃．．．3r）5 thenψ（K）＿．v， where∂ is a vertex of degree七wo of 』9 at麺91e㌘ゴ・ It．is clear that’ψis a inj ecti㎝． Thus， the nmi）er of clique§ of Z｝rσノ is at most lγr釧． Consequent1γ， if eitherσhas．avertex of degree』㎝e， or蜘o vertices・of a triangle of G are of degree two， then we obtain an inequality IγrO伍rω．川く1』γ‘ω1． T厄s contradictS the assu叩ti㎝Or砲〃−C． Next， 1et G do not satisfy the condition （2〕．and contaill an induced sUb− graph K4−x whi・h・。ns．ist・・f加・tri・ngles・h・ving・・n・ve「t朕mC㎝∞n・Ktl♪ Ktn
⇒
k1 2 k （Fig．2） If G satisfies the eqμとtion O（LrG〃＝G． then there is a subgraph冴of G・・d血t血it・1桓・9r・ph・LrH）． c・卿1・t・・ubg・、p㎏Xω．〆2㌔f乃㈲㎞。
・・rtex・in・ctm・・舳・each・f t㎞ee d卿1・t・鋤・gra旗・叉ω。・i，b。 th孤itself， ・eSP・・tiV・1y」魂・卿1・t・ ・ubgr・ph、 K「3ノ．K「4） 。f L（E） h。。 a v。rt，）x・in。⑩㎝ ・i・head・・f・K’（’）・nd・K「2ノ，・・SPec・iv・・y（Fig．2）． Ac。。。di。g，。 ICrausz’s Theorem，there may be such a graph． But・these °ccu「s伽・t・i・㎎1es＜｛vユ・・2・・3｝・・く｛・、・v4・・5｝・・i・五伽血i・h罐裁篇竺：li。、㌻e。：蒜11霊el。竪ll㌶e：。w纂
・T㎞s・G㎜・t・・砲㎞…bg・・ph K4・Since・CrLrσ〃−C．鋤G・・就・mS・・ub二．
graph K4・G・mu・t・・nt・in crLrK4」ノ〔Fig・3）・ K4 L（K4） C（L（K4）） （Fig．3） H°weve「・0‘五「K4”c°nt・ins K4・紐d・・C・・武・in・2K4・S血丘1・・1y・σr五rG〃−C ：c°ntains 2C「L（K4”＝4㌦・C。nt迦ing this p・㏄ess，σb㏄㎝・・飢血・finit・9r・ph， but this is a c㎝tTadiction．｝lence， if G does not satisfy condition（2）， th㎝θd・es n・t・ati・fy．th・equati・n CrL‘θ〃＝G．／34
1．SATO
Theor㎝2tZVIe soZution 9i・aph G of graph equαtion c rMrσ〃＝σのθthe o殉 gmaPhe whiσh oontainπo’triangZes． Proof． 1・et G be a gTaph obtained by adding to G new p vertices v撒ri＝23…・《・一垣ges・砲・r・・−1・・釧輌ω一｛・、・・・…，｝・…n…あi・
is㎝oτphic to丑f（Gノ （［2］，Th 1）・ Hence・the equation CθM（G〃＝G considered may be rewrittell as O r五r（；＋））＝G． 〔1）L・tθ・・nt・桓n・t・i飢91・・． Dra疏g th・1in・g・・．ph・Lrめ・fσチ。 ・i㏄・σ・・nt・in・n・t・i孤91・・， in thi・case e・ch・liqy・・f五rめi・th・1in・ graph of the sゆgraph induced by some vertex of G and its neighboエho（K【in G （Fig．4）・？ ↑ ↑ ♀ ♀ 9
‘ ‘ t ω’ 1 」 1 ∂ 1 ‘ ‘ o−一一一 ー←‘1Φ G＋ ‘1−10 一一一，r 《》一6 6
L（G＋）（heavy lines） 一◎ 儂。b：：1：㍑芸＆「e） ・ （Fig．4）th・・， th・n迦b・f・f・1iqu…f五rめi・equa1 t・17r釧．
Each vert・）x・f五（めb・1・㎎・t・at m・st tw・cliqu・・〔［3］，Tl・ 8．4）． lh・蒜’s㌶鑑。’；，蒜三，lxえt霊。麟（：，監；瀞∫tc；。’n
thi・ca・e， by n・glecti・g・uni・1iq・・1・・rtice・，ガヱb㏄㎝。、 th。叩eratエ㎝・， and then， G is obtained． （2〕S”pP°se．thatθc°ntains t「iangl…Al1 three v・垣ce・・〆ゴ・vk°f㌫三e。1；㌶｛認＞tlil，IC、hceale；：：：t°1。：t，li三：．曲「㌘：、篇lll・
rめ〃li．・．・〔〃（G〃−C〔LCめ），‘G．／th…㎝．3 th…Z・ti・n 9卿h G・丁θ・鋤・（1・・iti・n crTrG〃−G鯉・殉 ，totaZZy〈iisconneeカed gra穀hs． Proof・If G is a totally disco皿ected graph， then it is clear that O「a’「G）」−T（・［［heref・・e・1・t G b・an・nt・ivi・1・・m・ct・d・9r・ph， and。x、㎜。 th。 cliques of its tota］：graph． e3 e e 3 e2＝｛Vl，v3｝ 2 5 θ5 4 4 り （Fig．5）
