徐保根，趙麗鑫，鄒 妍

(華東交通大學(xué)理學(xué)院數(shù)學(xué)系，江西 南昌 330013)

0 引言及定義

本文所指的圖均為無向簡單圖，文中未說明的符號(hào)和術(shù)語同于文獻(xiàn)［1-2］.

設(shè)G為1個(gè)圖，用V(G)和E(G)分別表示G的頂點(diǎn)集和邊集.對(duì)于任意頂點(diǎn)v∈V(G)，定義v的鄰域，閉鄰域N［v］=N(v)∪為v點(diǎn)在G中的度，并且Δ=Δ(G)和δ=δ(G)分別表示圖G的最大度和最小度.對(duì)于2個(gè)點(diǎn)不交的圖G和H，則用G∨H表示G與H的聯(lián)圖，即在G∪H中將G的每個(gè)點(diǎn)與H的所有點(diǎn)鄰接所成的圖.

為了方便，若S?V(G)，f:V→R為1個(gè)實(shí)值函數(shù)，則記

下面給出關(guān)于圖的Fractional控制的定義.

定義1［3］設(shè)G=(V，E)為1個(gè)圖，實(shí)值函數(shù)f:V→［0，1］滿足f(N［u］)≥1對(duì)一切u∈V(G)都成立，則稱f為圖G的1個(gè)Fractional控制函數(shù)(簡稱為F-控制函數(shù)).圖G的Fractional控制數(shù)(簡稱為F-控制數(shù))定義為

γf(G)=min{f(V)︱f為圖G的F-控制函數(shù)}.且稱滿足γf(G)=f(V)的F-控制函數(shù)為1個(gè)最小F-控制函數(shù).對(duì)于任何圖G，由于常數(shù)函數(shù)f=1總是G的F-控制函數(shù)，故圖G的F-控制函數(shù)和F-控制數(shù)均存在.

若H為圖G的1個(gè)生成子圖，則圖H的任何F-控制函數(shù)也是圖G的F-控制函數(shù)，因此有下面的引理1.

引理1 設(shè)H為圖G的1個(gè)生成子圖，則γf(G)≤γf(H).

由定義1不難看出，對(duì)任意n階圖G，均有1≤γf(G)≤n，并進(jìn)一步可得引理2 對(duì)任意n階圖G，均有1≤γf(G)≤n，并且有

(i)γf(G)=n當(dāng)且僅當(dāng)為空?qǐng)D;

(ii)γf(G)=1當(dāng)且僅當(dāng)Δ(G)=n-1.

定義2［4］設(shè)G=(V，E)為1個(gè)圖，實(shí)值函數(shù)f:V→［0，1］滿足f(N［u］)≤1對(duì)一切u∈V(G)都成立，則稱f為圖G的1個(gè)F-包裝函數(shù).圖G的(上)F-包裝數(shù)定義為Pf(G)=max{f(V)︱f為圖G的(上)F-包裝函數(shù)}，并且稱滿足Pf(G)=f(V)的(上)F-包裝函數(shù)為1個(gè)最大F-包裝函數(shù).

引理3 對(duì)任意圖G，均有Pf(G)=γf(G).

由文獻(xiàn)［3］和引理3可導(dǎo)出F-控制數(shù)的界限.

引理4 對(duì)任意n階圖G，均有

特殊地，當(dāng)G為n階r-正則圖時(shí)，則

由上述2個(gè)定義及引理3可知，對(duì)于1個(gè)給定圖G，如果存在實(shí)值函數(shù) f:V→［0，1］，使得 ?u∈V(G)均有f(N［u］)=1成立，則函數(shù)f既是G的最小F-控制函數(shù)，又是G的最大F-包裝函數(shù)，從而有下面的結(jié)論成立.

引理5 設(shè)G為1個(gè)圖，如果存在實(shí)值函數(shù)f:V→［0，1］，使得 ?u∈V(G)均有f(N［u］)=1成立，則 γf(G)=Pf(G)=f(V(G)).

利用引理4可確定一些特殊圖的F-控制數(shù)，如完全二部圖Km，n等.

引理6 設(shè)2≤s≤r且它們均為整數(shù)，則

1988年，G.S.Domke等［3］首次提出且研究了圖的F-控制問題，E.O.Hare等［5-6］分別研究了關(guān)于乘積圖的F-控制數(shù)，文獻(xiàn)［7］討論了乘積圖的邊控制問題.本文先確定完全t-部圖的F-控制數(shù)(t≥2)，從而推廣了引理6的結(jié)果，并給出關(guān)于聯(lián)圖的F-控制數(shù)的1個(gè)上界，由此導(dǎo)出一些特殊聯(lián)圖的F-控制數(shù).

1 主要結(jié)果及證明

首先給出完全 t-部圖 K(n1，n2，…，nt)的 F-控制數(shù)(t≥2).

定理1 設(shè)n1≥n2≥…≥nt≥2且它們均為整數(shù)(t≥2)，，則

證 記 G=K(n1，n2，…，nt)，V(G)=V1∪V2∪…∪Vt為其t-部頂點(diǎn)劃分［8］，其中(1≤i≤t).定義圖G上的1個(gè)實(shí)值函數(shù)f:V(G)→［0，1］如下:

對(duì)于每個(gè)Vi(1≤i≤t)，當(dāng)u∈Vi時(shí)，令f(u)=1/［(T+t-1)(ni-1)］.

因t≥2且n1≥n2≥…≥nt≥2，故0≤f(u)≤1，并且有

由u點(diǎn)的任意性知，?u∈V(G)，均有f(N［u］)=1成立.由引理5得

定理1得證.

特殊地，當(dāng) t=2，n1=r，n2=s時(shí)，T=1/(r-1)+1/(s-1)，代入定理1中即得到引理6的結(jié)論.

下面考慮關(guān)于聯(lián)圖的F-控制數(shù)［9-11］.

定理2 設(shè)G和H為2個(gè)點(diǎn)不交的圖，則

由于f1和f2分別為圖G和圖H的F-控制函數(shù)，故有0≤f1(u)≤1，0≤f2(u)≤1.注意到p=γf(G)＞1，q=f2(V(H))＞ 1，可知0≤f(u)≤1.

?u∈ V(G∨ H)，不妨設(shè) u∈ V(G)，由于f1(NG［u］)≥ 1，故有

因此，實(shí)值函數(shù)f為聯(lián)圖G∨H的1個(gè)F-控制函數(shù)，從而有

即(pq-1)γf(G∨H)≤(q-1)p+(p-1)q.定理2得證.

在定理2的證明中不難看出，如果分別存在圖G和圖H的F-控制函數(shù)f1和f2，使得f1(N［u］)=1對(duì)任何u∈V(G)成立，并且f2(N［v］)=1對(duì)任何v∈V(H)成立，則定理2中等式成立.

推論1 設(shè)G和H為2個(gè)點(diǎn)不交的圖，如果分別存在圖 G和圖 H的 F-控制函數(shù) f1和 f2，使得f1(N［u］)=1且f2(N［v］)=1對(duì)任何u∈V(G)和v∈V(H)成立，則有

由推論1可以確定一些特殊聯(lián)圖的F-控制數(shù).

引理7 設(shè)整數(shù)n≥3，Pn和Cn分別表示n階路和n階圈，則

(i)γf(Cn)=n/3，且存在 Cn的F-控制函數(shù) f，使得f(N［u］)=1對(duì)任何u∈V(Cn)成立;

(ii)γf(Pn)=「n/3?，且存在Pn的F-控制函數(shù)f，使得f(N［u］)=1對(duì)任何u∈V(Pn)成立.

證 (i)由引理4知γf(Cn)=n/3，并取Cn上1個(gè)常數(shù)函數(shù)f=1/3，顯然有f(N［u］)=1對(duì)任意u∈V(Cn)成立.

(ii)記 V(Pn)={v1，v2，…，vn}，且 E(Pn)=.下面分2種情形定義Pn上的函數(shù)f如下:

不難驗(yàn)證，f(N［u］)=1對(duì)任何u∈V(Pn)成立.由引理5得

引理7得證.

由引理7及推論1可直接得出下面的結(jié)論.

定理3 設(shè)m≥4和n≥4，且它們均為整數(shù)，記

［1］ Bondy JA，Murty V SR.Graph theory with applications［M］.Amsterdam:Elsevier，1976.

［2］Haynes TW，Hedetniemi S T，Slater P J.Domination in graphs［M］.New York:Marcel Dekker，1998.

［3］Domke G S，Hedetniemi ST，Laskar R C.Fractional packings，coverings and irredundance in graphs［J］.Congr Numer，1988，66:227-238.

［4］徐保根.圖的控制與染色理論［M］.武漢:華中科技大學(xué)出版社，2013.

［5］Hare E O.K-weight domination and fractional domination of Pm× Pn［J］.Congr Numer，1990，78:71-80.

［6］ Fisher D C.Domination，fractional domination，2-packing and graph products ［J］.SIAM Discrete Math，1994，7(3):493-498.

［7］徐保根，陳悅.圖的符號(hào)邊全K控制數(shù)［J］.江西師范大學(xué)學(xué)報(bào):自然科學(xué)版，2011，35(3):316-318.

［8］徐保根，趙利芬，操葉龍，等.關(guān)于圖的控制集劃分［J］.江西師范大學(xué)學(xué)報(bào):自然科學(xué)版，2013，37(5):475-478.

［9］齊登記，梁希泉.關(guān)于圖的控制數(shù)Vizing's定理的推廣［J］.東北師大學(xué)報(bào):自然科學(xué)版，2005，37(1):24-27.

［10］周仲旺，劉書英.一類聯(lián)圖的符號(hào)邊控制數(shù)［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2013，43(16):255-261.

［11］徐保根，張亞瓊，湯友良.關(guān)于圖的符號(hào)邊控制數(shù)的一些結(jié)論［J］.河南科技大學(xué)學(xué)報(bào):自然科學(xué)版，2012，33(4):74-77.