關于一些特殊圖類的弱控制多項式的研究

劉慧靈, 邊 紅*, 于海征, 魏麗娜

(1. 新疆師范大學 數學科學學院, 新疆 烏魯木齊 830054; 2. 新疆大學 數學與系統科學學院, 新疆 烏魯木齊 830046)

設圖G= (V(G),E(G))是簡單連通圖,V(G)和E(G)分別為圖G的頂點集和邊集.頂點集的階是指該集合中包含的點的個數.點v∈V(G)的開鄰集N(v)={u∈V(G)|uv∈E(G)},點v∈V(G)的度d(v)=|N(v)|.圖G中度為1的點稱為懸掛點.令D(G)?V(G),對圖G的任意一點v∈V(G)D(G),至少存在一個點u∈D(G),使得uv∈E(G),則稱D(G)為圖G的一個控制集.圖G的控制多項式為

其中,D(G,j)為圖G中階為j的控制集的個數,最小控制集中點的個數稱為圖G的控制數,記為γd(G).如果對任意v∈V(G),均存在u∈V(G),使得uv∈E(G)且d(u)≥d(v)成立,則稱u強控制v,或v弱控制u.令W(G)?V(G),如果對任意v∈V(G)W(G),均存在u∈W(G),使得u弱控制v,則稱W(G)為圖G的一個弱控制集.圖G的弱控制多項式為

其中Wd(G,j)為圖G中階為j的弱控制集的個數,包含點數最少的弱控制集稱為最小弱控制集,最小弱控制集中點的個數稱為圖G的弱控制數,記為γwd(G).

1996年,Sampathkumar等[1]提出了圖的強控制和弱控制這一概念,同時這篇文章也提到了Hattingh等[2]證明了與計算圖的弱控制數相關的問題是NP-完全問題.2014年,Arocha等[3]定義了圖的控制多項式,并給出了控制多項式的一些簡單性質.2008年,Bród[4]計算了一些特殊圖類的控制集及弱控制集的總數.2009年,Alikhani等[5]計算了一些特殊圖的控制多項式.2014年,Shivaswamy[6]介紹了圖的獨立控制多項式,并得到了一些圖類的獨立控制多項式,建立了圖的獨立控制多項式的一些性質.2018年,Raj等[7]介紹和建立了完全圖的弱控制集和弱控制多項式.同年,Abas[8]研究出一些特殊圖類的控制多項式、獨立控制多項式和全控制多項式,并得到了一些它們的性質和部分系數的性質,對于部分特殊圖類,也得到了一些計算這些多項式函數的新公式.2020年,徐保根等[9]研究了圖的強控制和弱控制問題,分別獲得了圖的強控制數和弱控制數的上界,并確定了幾類特殊圖的強控制數和弱控制數.2021年,包冠宇等[10]先借助Beraha-Kahane-Weiss定理給出友誼圖的全控制多項式根的極限曲線,而后證明了控制多項式的根在整個復平面上是稠密的.2022年,Yimer等[11]得出了齊次毛蟲形圖和全二元樹的完美控制多項式.

本文主要介紹了一些特殊圖類的弱控制多項式,其中包括(n,1)-棒棒糖圖、舵圖、花圖、雙星圖、三角書圖、友誼圖、荷蘭風車圖.主要結論如下.

定理 1(n,1)-棒棒糖圖Ln,1的弱控制多項式為

WD(L

定理 2舵圖Hn的弱控制多項式為

WD(H

定理 3花圖Fln的弱控制多項式為

WD(Fl

定理 4雙星圖Bsm,n的弱控制多項式為

WD(Bsm,n,x)=xm+n(x+1)2.

定理 5三角書圖TB3,n的弱控制多項式為

WD(TB3,n,x)=xn(x+1)2.

定理 6友誼圖Fn的弱控制多項式為

WD(Fn,x)=

WD(D

1 基本概念

定義 1一個圖稱為(n,1)-棒棒糖圖,如圖1(a),記作Ln,1,如果它滿足

V(Ln,1)={u1,u2,…,un,v},
E(Ln,1)={uiuj|i,j=1,2,…,n,i≠j}∪{vu1}.

定義 2一個圖稱為Kn與K1的corona積,如圖1(b),記作Kn°K1,如果它滿足

V(Kn°K1)={u1,u2,…,un,v1,v2,…,vn},
E(Kn°K1)=
{uiuj|i,j=1,2,…,n,i≠j}∪{viui|i=1,2,…,n}.

圖 1 (n,1)-棒棒糖圖Ln,1和Kn與K1的corona積Kn°K1

定義 3一個圖稱為舵圖,如圖2(a),記作Hn,如果它滿足V(Hn)={v,u1,u2,…,un,w1,w2,…,wn},E(Hn)={vui|i=1,2,…,n}∪{wiui|i=1,2,…,n}∪{uiui+1|i=1,2,…,n},其中邊unun+1就是邊unu1.

圖 2 2n+1階舵圖Hn與2m+1階Ⅰ型太陽花圖

定義 5一個圖稱為花圖,如圖3(a),記作Fln,如果它滿足V(Fln)={v,u1,u2,…,un,w1,w2,…,wn},E(Fln)={vui|i=1,2,…,n}∪{vwi|i=1,2,…,n}∪{uiwi|i=1,2,…,n}∪{uiui+1|i=1,2,…,n},其中邊unun+1就是邊unu1.

圖 3 2n+1階花圖Fln與3n+1階Ⅱ型太陽花圖

定義 7一個圖稱為雙星圖(圖4),記作Bsm,n,如果它滿足V(Bsm,n)={u,v,x1,x2,…,xn,y1,y2,…,yn},E(Bsm,n)={uv}∪{uxi|i=1,2,…,m}∪{vyi|i=1,2,…,n}.

圖 4 m+n+2階雙星圖Bsm,n

定義 8一個圖稱為三角書圖(見圖5),記作TB3,n,如果它滿足V(TB3,n)={v1,v2,u1,u2,…,un},E(TB3,n)={v1v2}∪{v1ui|i=1,2,…,n}∪{v2ui|i=1,2,…,n}.

圖 5 n+2階三角書圖TB3,n

定義 9一個圖稱為友誼圖(見圖6),記作Fn,如果它滿足V(Fn)={x,v1,v2,…,vn,u1,u2,…,un},E(Fn)={xui|i=1,2,…,n}∪{xvi|i=1,2,…,n}∪{viui|i=1,2,…,n}.

圖 6 2n+1階友誼圖Fn

圖 7 3n+1階荷蘭風車圖

2 主要結果

定理 8令Ln,1為n+1階(n,1)-棒棒糖圖,則(n,1)-棒棒糖圖Ln,1的弱控制多項式為

WD(L

證明令Ln,1為n+1階(n,1)-棒棒糖圖,V(Ln,1)={u1,u2,…,un,v},E(Ln,1)={uiuj|i,j=1,2,…,n,i≠j}∪{vu1}.因為v為懸掛點,故v點一定在弱控制集中,此時對于圖Ln,1,u2,u3,…,un共n-1個點均未被弱控制,而u1為最大度點,不能弱控制圖上其余各點,點u2,u3,…,un均彼此相鄰,且d(u2)=d(u3)=…=d(un),因此圖Ln,1的最小弱控制集W(Ln,1)={v,ui|i=2,3,…,n},故

圖Kn與K1的corona積Kn°K1,是由(n,1)-棒棒糖圖將u2,u3,…,un的每個點分別添加一個懸掛點構成的.根據定理 8,自然可以給出Kn°K1的弱控制多項式.

推論 1令Kn°K1為Kn與K1的corona積,則Kn°K1的弱控制多項式為

WD(K

綜上所述

定理 9令Hn為2n+1階舵圖,則舵圖Hn的弱控制多項式為

WD(H

WD(Hn,x)=

定理 10令Fln為2n+1階花圖,則花圖Fln的弱控制多項式為

WD(Fl

綜上所述

WD(Fl

定理 11令Bsm,n為m+n+2階雙星圖,則雙星圖Bsm,n的弱控制多項式為

WD(Bsm,n,x)=xm+n(x+1)2.

證明令Bsm,n為m+n+2階雙星圖,V(Bsm,n)={u,v,x1,x2,…,xn,y1,y2,…,yn},E(Bsm,n)={uv}∪{uxi|i=1,2,…,m}∪{vyi|i=1,2,…,n}.因為x1,x2,…,xm,y1,y2,…,yn為懸掛點,故點x1,x2,…,xm,y1,y2,…,yn一定在弱控制集中,此時點u,v均被弱控制,因此圖Bsm,n的最小弱控制集是W(Bsm,n)={x1,x2,…,xm,y1,y2,…,yn},故γwd(Bsm,n)=m+n,Wd(Bsm,n,n)=1.對于圖Bsm,n,階為m+n+1的弱控制集是由從u,v中任選一個點,與x1,x2,…,xm,y1,y2,…,yn共同構成的,故Wd(Bsm,n,m+n+1)=2.綜上所述

WD(Bsm,n,x)=1xm+n+2xm+n+1+1xm+n+2=
xm+n(1+2x+x2)=xm+n(x+1)2.

對于圖Bsm,n,若m=n,則γwd(Bsm,n)=2n,

WD(Bsm,n,x)=1x2n+2x2n+1+1x2n+2=x2n(x+1)2.

定理 12令TB3,n為n+2階三角書圖,則三角書圖TB3,n的弱控制多項式為

WD(TB3,n,x)=xn(x+1)2.

證明令TB3,n為n+2階三角書圖,其中,n為圈C3的n個拷貝,V(TB3,n)={v1,v2,u1,u2,…,un},E(TB3,n)={v1v2}∪{v1ui|i=1,2,…,n}∪{v2ui|i=1,2,…,n}.因為u1,u2,…,un為TB3,n的最小度點且互不相鄰,故點u1,u2,…,un一定在弱控制集中,此時點v1,v2均被弱控制,因此圖TB3,n的最小弱控制集是W(TB3,n)={u1,u2,…,un},故γwd(TB3,n)=n,Wd(TB3,n,n)=1.對于圖TB3,n,階為n+1的弱控制集是從v1,v2中任選一個點,與u1,u2,…,un共同構成的,故Wd(TB3,n,n+1)=2.綜上所述

WD(TB3,n,x)=
1xn+2xn+1+1xn+2=xn(x+1)2.

定理 13令Fn為2n+1階友誼圖,則友誼圖Fn的弱控制多項式為

WD(Fn,x)=

綜上所述

WD(Fn,x)=

WD(D

故

綜上所述

致謝新疆師范大學2020年一流專業、2021年一流課程項目對本文給予了資助,謹致謝意.