ON A STRUCTURE OF GRAPHS WITH W-SETS

TRD MEithemmatics 1 5 一 2 （1979）

ON A STRUCTURE OF GRAPHS WITH W−SETS

Jin AKIYAMA and Mroshi ERA 〔Received NOvemiber 16， 1979）       AbstTact     ln our−previous paper ［1】，we investigated the propeτties on the cohesive− ness of a point． As a natural extension， we define the cohesiveness fbr a point subset． The co力e⑤エve孕ess c（且ノ of a po」tロt sロbset H of a graph G is dbfined by the differenceκ‘GノーK‘G一即． A point subset H of a graph is called a旬」se亡if it satisfies‘ユノσ‘日，＜0， f2／c‘互り＞a（H， for aロリ5ロbset 日゜⊂冴， and （3） σf冴っ ≧σ‘冴ノ fb’ang●ロbset H“⊃日． The mtion of a w−set is ageneralizati㎝of a cut−set of a graph． Our purpose of this paper is to detelnnine tbe structures of graphs with at least two ”−sets・ §1．1班…FINITIONS AND NO肛ATION．     The connectivゴtg K＝K‘G／of a graph G of oτdeτρ唾th point set v is the miniiiu皿．コ画〕er of POints whose removal results ヰn a disconnected or a trivial gra画・th・・。σa・。。垣ec・ゴ鞠・G‘w♪・f加・n。脳1j㏄㎝t p・int・・孤d・・f G is the minimm nu血ber of points 諭ose removal separates ロ and v．  Ifロ and v are adj acent and H ＝ G 一 ロv， then colmectivity Kσfロ，ワ， in G is defilled as KHr・・vノ… Clea・ly f・・飢y・。nt・ivi・1 9r・ph・G・we｝Vave・K‘G，＝

曲｛KG‘u’v）：ロ’vεy’ufv｝・th・・eighb。urh・w川且，。f・p°int subset

H⊂vis the set of all po加s w垣dl are adjac㎝t to at least one of points in H・L・t s−｛・、’・2’…’・。｝⊂γ鋤・εv−5・1識e・eare・P・廿「s bet“reen uand s which are paiτ顧se disjoint apart fr㎝・， we call the subgraph consisting of these paths a ロ ーsfan． All other definitions and terminology not presented here can be fbund in Harary 【4］．     輪will req唾re the foll．owi’ ng two le肋mas曲ich are derived readily 丘㎝ Menger・s lheoren［4， p．47］． The first was given in Dirac【2］， a西1 they are stated without pro《》fs．

    ㎜A． F◎ragraρhθ，K‘Gノ＝n工faηdo且1リエfp≧⑰＋1aηdfρエaロ9

subset s⊂Vof cardinaユity n and fbr a卯」poエロ亡ロεγ一S，亡he’e工s aロー5 加．

    蹴B・Th・ヱ。…。。nneati・ity・σf・’・ノ・σ・a1・仙・蹴畑㎝n輌゜f

u 一 ワρaths 臓h工⊂h haveηo co皿肋on po1ηts othεr セ九an u and v・

43

44 _{J．AKIYAMA AND H． ERA} §2． T団ECCHESIVENESS OF A POINT SUBSET AND A W−SEr．       Throughout the paper， we assume G is connected with connectivity K． The oo力esゴveness a （H）of a subset H of v is defined by          σ但，＝K （G）−K‘G−H，． AsUbset H of v is a w−s白七 if it satisfies the following conditions〔1），〔2） and（3）： （ユノ   σ但ノ＜0， （2／   cfHり＞cイH， for ang subse亡H’⊂H， and r3ノ      σ（H，り ＞ a（H， for aηり subse亡 H”⊃H．      Figures 1，2 illustrate graphs with one ”−set， two va−sets， respectively．     Fゴguτe 1． ゑ graph wi亡力a W−set．       Fi gure 2． A 9エaph wi亡力 2”−se亡5．     Since the structure of graphs with exactly one w−set is simple， we s｝1all determine the structures of graphs with at least two”−sets in the fbllowing theorems．     THEOREM 1．  Let H  a虜id H  be two distinσt w−se亡s of G and        ユ    2 ・一…｛・r・、）’・rH2）｝・Th・・亡h・・e e・i・t・P。i・ts・’・1・HユーH2’・2−H、’ 「espectiveiy’・・σ力亡h・亡KGイ・’の＜K一α・      PROOF． We divide the proof into two cases．      Case 1・H1∩H2＝9・ Since・（G−・∂≧・一α・・，fb…y・P。i・t・・’w in vイσ，−Hユ’th・i呵・alities KG‘・〃，≧・G−H伽ノ〉・h・1d・Sinilarly・f・r any p。ints・’w in v（σ）−H2’

・G触，…ヱH・nce，・here exi・t・P・i・…’・汕、’H、’re・pecti…y，・uch

that KG r…）＝KくK一α・      Case 2・H、∩H2 f Q・ Assume that the theorem d6es not hold， then for any pair of points u and v in v−・ユ佃2’・Gru’・ノ≧・一α・A・d…rHユ∩∬2ノ≦・・Whi・h・。・t・・di・t・t・ the・lefiniti・n（2）。f・w−set・since H、 and H2 are di・tinct・by th・h）rP。thesis

of the theorem．       口

ON A STRUCTURE OF GRAPHS WITH W−SETS

45      LE附A 1． α＝max｛c（Hユ）t Let H  aηdガ  be 亡wo d工s亡工nc亡 ”−se亡s of G aηd     ユ    2 ・‘H2）｝’then th・エ・eσ・・ヱエ・り1昭ノーH21・K−・h。ヱd・・      PROOF・S・pP・・e th・t l・（H、，−H21≧・一α鋤th・t 5 is any・ub・et。f N（Hユ，一・2・ith l・1−・一・・By・Lenma A there exi・t・a・一・』i・G−H2 f・r any poi・t・i・HユーH2・L・t pi’i＝ユ’2’…’・一・・b・p・th・i・th・・’s f・n・and ・」b・th・fi・st p・i・t（・tarting f・・m・）㎝ead・P工曲i・th i・n・t i・Hユ・P・t 5’・｛・ユ’・2’…’・K−。｝・th・n・w・ ha…−5’』with s’∩HヱーP・and。f course all the points other than the lx）ints of s’㎝each path of theローs’ f・n be1。・g t・H、・Qn th・・ther h・nd・by・Leirma A there exists a・−s’fan in

G−H

??E・any・POint・in ・2−・、・Tl・us…mbini・g th・・−s’fan with the・−s’ fan， we have K 一αpairwise disjoint u−v paths． That is， there are K 一α pairwise disjoint ローv paths fbr any points u・vin H1 −H2・H2 −Hユ・「espec− tively． By lemma B， we have a contradiction to Theorem 1．       口 THEOREM 2．  Le亡 ∬  a刀d H       ヱ     2

     V一ち⊂H2U晒ノ・

be 亡w◎ disti刀ct va−se亡s of G， 亡力en     PROOF． Assume that the theorem is not true． Let ロbe a point of G such that u t HIU H2U N（H2ノ・ Clearly・for any point v in H2−H1・ ・G．H（・’・ノ≦1・・（H、ノー・、1・hence・by・L・mm・1・鴨』 ・6．ll1（・’・ノ・K−・三・（・一・、ノ・whi・h i・ac・・tradi・ti・n・   ロ     ユ     Theorem 2 together with temna A delivers the fbllowing two j噸）rtant corollaries． 00ROLLARY 1．     N（Hi，°     COROLLARY 2． is ηo other W−5et 亡 ＝

岳

 H2

工fa

i ユn G． H  and H  be twr） d工s亡ゴ刀ct w−se亡s of G， tlen 1     2 N（H2）一

_{ｿ＝V−（Hl UHノ・}

口 肝se亡of G COIIsist50f aロ㎡gue eヱement， then there       口     ㎜（． The last corollary is a generalization of the rnain theorem of ［1】，whidh is stated as follows；     THE冊…OREMOF［1］．ヱf vエs a p。エn亡。f G wエthσ（v）＜0， then nO O亡力er釦ch poエn亡， and degfv，＝δ＝K． there is

46

J．AKIYAMA AND H． ERA

REFERENCES

［1］ ［2］

︼］

34

［1

J．Akiyaina， H． Era and F． Harary：The coheciveness of a POint of a graph，   NetworkS， to appear． G．A． Dirac：（lin6ralisation du th60rbrn de Menger， C． R． Acad． Sci． Paris   250（26） （1960）， 4252−4253． P．Harary：StructUral duality， behavioral Sci． 2 〔1957）， 255−265． F．Harary：Graph Theory， Addison一脆sley 〔1969）・       Nihon Ika Uhiversity       KA⊂JAPAN       Department of Math．       Tokai uぬiversity       HIRATSUKA JAPAN