【正文】 the value 2 can be attained by 39。 ()(2stffNf????constructing a SETDF such that for edges e and for edges. )e?1?()1f?m華東交通大學(xué)畢業(yè)論文 27 If m is odd, then, according to Proposition 4, we have . We may construct a SETDF f 39。()3stT??such that f(e) = 1 for edges e and for edges e. 32m?()1f??2mWe finish again by an existence theorem.References[1] E. Xu: On signed domination numbers of graphs. Discr. Math. (submitted).[2] . Haynes, , P. J. Slater: Fundamentals of Domination in Graphs.Marcel Dekker, New York, 1998.Author’s address: Bohdan Zelinka, Technical University Liberec, Voron..ska 13, 460 01Liberec 1, Czech Republic, .①：摘自 MATHEMATICA BOHEMICA 127(2022)No. 1, 劉峰 關(guān)于圖的邊控制數(shù) 28 B 外文翻譯 譯文部分?關(guān)于樹的符號邊控制數(shù) ①Bohdan Zelinka, Liberec (Received April 18, 2022)摘要：圖的符號邊控制數(shù)是隨著符號控制數(shù)的變化而改變的一個變量。 表示邊 e 在圖 中的閉鄰域，它是由邊 e 和所有與 e 相鄰的邊組成的集合。假設(shè)函[]GNG數(shù) 是圖 的邊集 到集合 的映射。如果對任意 都有f()E{1,}??()EG?成立的話，則 稱為圖 的符號邊控制函數(shù)。同時在關(guān)于圖 的所有符號[]()1xNe???fG邊控制函數(shù) 中，得到 的最小值， 稱作為圖 的符號邊控制數(shù)，記為 。f()xE? 39。()sG?同理，若用開鄰域 替閉鄰域 ，我們得到圖 的符號全控制數(shù)的定[]{}GeNe??[]GNeG義，我們把它記為 。在這篇論文中研究的對象是樹。39。()st?數(shù) 表示 的星圖，路徑，或者 毛蟲樹的符號邊控制數(shù)。此外還有 表示一39。()sT? 39。()snC?個長度為 n 的圈的控制數(shù)。樹滿足不等式條件 是確定的。對于給定邊數(shù)，和39。39。()sT??給定符號邊控制數(shù)的樹 ，已經(jīng)證明了它的存在性定理。最后，得到了完全控制數(shù) 的一些類似結(jié)果。39。()stT?關(guān)鍵字：樹，符號邊控制數(shù)，符號全控制數(shù)MSC 2022: 05C69, 05C05 在這里我們考慮的都是沒有自環(huán)和沒有重邊的有限無向簡單圖。圖 的邊集記為G且頂點集記為 ，圖 的兩條邊 稱為鄰邊， 如果他們是有一個共同頂點的()EG()VG12,e兩條不同的邊。對于邊 的開鄰域 表示的是與邊 相鄰的所有邊組成的集合。eE?()GNe它的閉鄰域則為 。[](){}GN??如果我們考慮映射 且當(dāng) ，我們記 。:1,f???()sE?()()xsff???一個映射 稱為關(guān)于圖 的符號邊控制函數(shù)（或全符號邊控制函數(shù)） ，:(){,}fE華東交通大學(xué)畢業(yè)論文 29 如果 （或 分別成立）對任意一條邊 都成立。同時在關(guān)于([])1GfNe?()1GfNe?()eEG?圖 的所有符號邊控制函數(shù)（或全符號邊控制函數(shù)） 中，得到 的最小值， 分ff別稱為圖 的符號邊控制數(shù)（或符號邊全控制數(shù)， ）關(guān)于符號邊控制數(shù)在文獻(xiàn) B. Xu [1]有介紹且記為 。圖 的符號全控制數(shù)記為 。39。()s? 39。()st?符號邊控制函數(shù)簡記為 SEDF，全符號邊控制函數(shù)簡記為 SETDF， 的值是隨邊39。()sG?控制數(shù)的變化而改變的一個邊變量[2]。另外還有一種有關(guān)圖的控制數(shù)。是一個邊集合 映射到圖 的一個函數(shù) ， （當(dāng)D()F的每一條邊都在 中時或者鄰接于 時，圖 的邊集 的子集 稱為 中的邊控GDG()FD制數(shù)） 若稱 是圖 的邊控制函數(shù)，當(dāng) 的每一條邊都在 中或者鄰接于 。在圖()FG邊控制集合中最小的邊集數(shù)目就稱為圖 的邊控制數(shù)，記為 。39。()G?接下來我們研究的 和 都是關(guān)于樹的結(jié)論。39。()s?39。()st引理 假設(shè)圖 有 m 條邊那么 39。()mod2)sG??證明：假設(shè) 是 的一個 SEDF，且 。令 表示 (或 fG39。 (sfE?()m??或 )1fe?)這類邊的數(shù)目。我們有 同時， ，因此(1fe????39。)s?，故結(jié)論成立。 39。 2sGm?引理 若 是樹 的 3 個頂點，且 是 的一個懸掛頂點 的兩個鄰接頂點分別,uvwTuTv是 ，定義 為 的 SEDF 則有：,uf ()1fvfw?證明：我們知道 且 故結(jié)論成立。 []{,}Nuvw?[]()Nuvf?引理 若 是一個星圖，它含有 條邊，當(dāng) 為奇數(shù)時， ，當(dāng) 為偶數(shù)Tm39。()1sT??m時， .39。()2s??證明：在星圖中所有的邊都連接在一起，因此 對任意一條邊 都[]()TNeE?()eE?成立若 是 的 SEDF，則有 ，故 .設(shè) 表示圖 中fT()([])1TfEf??39。1s?m?T劉峰 關(guān)于圖的邊控制數(shù) 30 的邊數(shù)，那么 .如果 為奇數(shù)時，我們可以取一個函數(shù) 使得()1fe??()2fETm?? f滿足 ，因此有 .如果 為偶數(shù)時， 也是偶數(shù)我們可()2m39。()1sf?m2m?以選擇一個函數(shù) 使得 ，因此 . f1(2)??39。()(sfET??當(dāng) ，則 的鄰域子樹 ，是由 的頂點集， 和 的邊集構(gòu)成的圖。()eET?[]NTe[]Te[]TNe若 是 的一條懸掛邊，那么 是以邊 的一個頂點為中心，且中心度數(shù)大于 1 的星圖。這就得到了包含邊 且直徑為 2 的最大生成子樹，.相反地 是以邊 為中心且直徑為e []Ne3 的最大生成子樹。把所有的生成子樹 （其中 ）構(gòu)成的集合記為[]NTe()ET?NT定理 在樹 中存在一個 的子集 ，滿足 所鄰接的樹的并是 ，則有T00.39。39。()s??證明：令 是 中的邊集，對任意一條邊 ，則集合 是邊 e 的鄰域0E0[]Ne?0eE?[]TN集，且所有集合的并是 .因此 是 .()T0E39。0()??令 是 的一個 SEDF 所以 .由于 中的樹是關(guān)聯(lián)，:(){1,}f???39。()(sfT??我們有如下結(jié)論 . 0039。 39。()()[]1)s TeeETffNT???????我們已知 對任意一個樹都成立，所以有如下推論。39。()1?推論 當(dāng) 滿足定理 1 的條件時，則有.39。()1sT??猜想：對任意一個樹 ，我們有 成立。T39。s表示長度為 的路徑，也就是說含有 條邊以及 個頂點的路徑。 則表示mPm?mC長度為 的圈。定理 對于路徑 （ ） ，它的符號邊控制數(shù)有如下結(jié)論：mP2?華東交通大學(xué)畢業(yè)論文 31 39。39。39。1()2 0(mod3)3) 11() 2(od3)3smssmP?????證明：令 是路徑 的 SEDF 則 ，取 ，fP39。())smfEP??{()1}mEePfe?????.很明顯對 中任意一條邊必須至少鄰接兩條 中的邊，且{()1}mEee?????? ?中的任意一條邊至多只能鄰接 中的一條邊。據(jù)引理 2 可知， 的端點和 的邊之? mE?間至少含有兩條 中的邊，同理兩條 中的邊之間至少含有兩條 中的邊。因此E?E? ?且 .如果我們選擇 中的一個端點1(2)3E?????? 1()2()3mfP??????mP開始對其邊標(biāo)號，我們可以這樣選定函數(shù) ，當(dāng)且僅當(dāng)邊 的序號數(shù)能被 3 整除，且小于fe時，令 .這時有 ，且它就是 .這個數(shù)值對對1m?()1fe??1()2()3mfE??????39。()sm?模 3 值分開表示，則得到定理給出的形式。 令一方面我們來考慮圈的情況，證明方法十分類似于定理 2.定理 對于圈 ，它的符號邊控制數(shù)有如下結(jié)論：mC39。39。39。1() 0(mod3)3(2) 11() (od3)3smssmC?????下面我們來考慮毛蟲樹. 把毛蟲樹 的所有懸掛邊刪除后得到的是一條路徑：也就是說，得到的這條路是毛蟲樹的主干。毛蟲樹的一些個別情況包括星圖和路徑。另 的主體頂點標(biāo)記為 和邊 （ ）.令 （ ）為頂點C1,ku? 1iu?,1k??? ip1,k??上的懸掛邊的數(shù)目。有限序列 決定了毛蟲樹的唯一性。根據(jù)定義所知很明顯有iu??ip?且 .若 k = 1，則這個毛蟲樹就是一個星圖。若 ，1p?k 1kp?（ ， ）則它是一條路徑。0i?,1i??劉峰 關(guān)于圖的邊控制數(shù) 32 定理 令 為一個整數(shù)有限序列，且 ， ， ， 。令??1kip? 12p?k1ip?21ik??表示 中所含奇數(shù)的數(shù)目則 就是由此序列控制的毛蟲樹，得知0k12,k?? C.39。0()sC???證明：由這個定理的假設(shè)可知 的主體中每個頂點至少有一條懸掛邊令 為 （iMip）中所含的所有邊構(gòu)成的邊集。令 為 的主體中一個頂點，當(dāng) e 為這個頂點的1,ik? ipC一條懸掛邊，則有 ，且 ，[]iNeM?111(),{,}kiiiiijiEMu?????????故有 .我們可以這樣地定義函數(shù) ：當(dāng) 或2ij??111()(){}kkiiifECffu?????f1i，且 為偶數(shù)時，令 中 條懸掛邊 e 的函數(shù)值 .當(dāng) 或 ，且 為ik?ipi2ip()1fe??ik?ip奇數(shù)時，令 條懸掛邊 e 的函數(shù)值 .若 ，且 為偶數(shù)時，令1()2i?()1f?2ik?ip中 條懸掛邊 e 的函數(shù)值 .若 且 為奇數(shù)時，令 條懸掛iMi ()f?iip(1)2i?邊 e 的函數(shù)值 對于 的主體中的邊 e 總有 .當(dāng) 或 ，且 為偶數(shù)()1f?C()f??1ik?i時，則 ， 為奇數(shù)時，則 .當(dāng) ,且 為偶數(shù)時，則iip()2ifMik??i ()ifM?為奇數(shù)時，則 ,所以 故結(jié)論成立。 ip()2if 1011,()ki ii iffu????我們得出了 的一個存在性定理39。sT?引理 4 一個具有 條邊的圖 ,且所有子圖中不含有 ,那么有mG2K.39。()mod)st??此證明與引理 1 的證明很相似。引理 若在圖 中所有子圖中不含有 ，且 對某些邊 成立，則2()2Ne?()eEG?對所有 有 .()xNe?fx??這個結(jié)論是很明顯的。這個引理得出了兩個推論。推論 對于長度 的路徑 ，有2m?mP39。().sm??推論 對于長度為 m 的圈 ，有C39。s華東交通大學(xué)畢業(yè)論文 33 也就是說，在這兩種情況下，SETDF 只有一個常數(shù)值為 1.定理 圖 表示一個邊數(shù) 的星圖，若 是奇數(shù)，則 .若 是偶數(shù)，T2m?39。()3stT??m則 .39。()2st??證明：令 是圖 的 SETDF，則 .很明顯至少存在一條邊 使f 39。()()stfET??()eET?得 .我們有 ，且 ，若 m()1fe(){}ETNe??39。 ()(12stffNef???是偶數(shù)，我們可以取 條邊使得組成 SETDF 的 為 ，取 條邊使得組12m???成 SETDF 的 為 若 m 為奇數(shù)，據(jù)引理 4 有 ，我們可以取 條邊f(xié)()e?39。()3stT?32?使得組成 SETDF 的 為 ，取 條邊使得組成 SETDF 的 為 . f?32?f()1e?我們再一次得出了一個存在性定理。參考文獻(xiàn)[1] B. Xu: On signed domination numbers of graphs. Discr. Math. (submitted).[2] . Haynes, , P. J. Slater: Fundamentals of Domination in Graphs.Marcel Dekker, New York, 1998.Author’s address: Bohdan Zelinka, Technical University Liberec, Voron..ska 13, 460 01Liberec 1, Czech Republic, .①：摘自 MATHEMATICA BOHEMICA 127(2022)No. 1,