两类特殊图的逆符号边控制数

设G=(V,E)是一个图,对于图G的一个函数f:E→{-1,1},如果对任意e∈E(G),均有Σe′∈N[e]f(e′)≤1,则称f为图G的一个逆符号边控制函数.图G的逆符号边控制数γ′s(G)=max{Σe∈E(G)f(e)|f为图G的一个逆符号边控制函数}.在逆符号边控制数定义基础上,得到了所有轮图和扇图的逆符号边控制数.     

图的逆符号边控制数的上界

设G=(V,E)是一个图,对于图G的-个函数f:E→{-1,1},如果对任意e∈E(G),均有∑f(e')≤1,则称,为图G的一个逆符号边控制函数.图G的逆符号边控制数(～γ's)(G)=e'∈N[e]max{∑,(e)|f,为图G的一个逆符号边控制函数}.本文在定义了逆符号边控制数的基础上,得到了图e∈E的逆符号边控制数的几个上界.     

图的k符号边控制数

设G=(V,E)是一个图,一个函数f:E→{-1,+1},如果对于G中至少k条边e有sum from e'∈N[e]f(e')≥1成立,则称f为图G的一个k符号边控制函数.一个图的k符号边控制数定义为γ_(ks)^/(G)=min{∑_(e∈E(G))f(e)|f为图G的一个k符号边控制函数}.主要给出了一个图G的k符号边控制数γ_(ks)/(G)=min{∑_(e∈E(G))f(e)|f为图G的一个k符号边控制函数}.主要给出了一个图G的k符号边控制数γ_(ks)^/(G)的若干新下限,并确定了路和圈的k符号边控制数.     

一类联图的符号边控制数

设G=(V,E)是一个简单图,一个函数f:E→{-1,1},若满足∑_(e′∈N[e])f(e)≥1对E(G)中的每个边e都成立,则称f是图G的一个符号边控制函数,图G的符号边控制数定义为γ′_s(G)=min{∑_(e∈E)f(e)|f是G的符号边控制函数}.给出了联图C_(2k)+C_(2k)的符号边控制数.     

几类图的符号控制

设G=(V,E)是一个图,一个函数f:V→{-1,+1}如果满足Σv∈N[υ]f(ν)≥1对于每个点u∈V成立,则称f为图G的一个符号控制函数,图G的符号控制数γs(G)定义为γs(G)=min{Σv∈vf(v)|f为图G的符号控制函数},类似地,可定义图G的上符号控制数Γs(G).研究了几类特殊图的符号控制问题,获得了完全l等部图和乘积图P_3×P_n的符号控制数,并确定了P_2×P_n和P_3×P_n的上符号控制数.     

关于图的符号星控制数

设G=(V,E)是一个图,u∈V,则E(u)表示u点所关联的边集.一个函数f:E→{-1,1}如果满足■f(e)≥1对任意v∈V成立,则称f为图G的一个符号星控制函数,图G的符号星控制数定义为γ'_(ss)(G)=min{■f(e):f为图G的一个符号星控制函数}.给出了几类特殊图的符号星控制数,主要包含完全图,正则偶图和完全二部图.     

完全多部图的符号边控制数的界

$f: E(G)\rightarrow\{-1,1\}$称为图$G =(V,E)$的一个符号边控制函数 (简称SEDF),如果$f[e]=f(N[e])=\sum_{e''\in N[e]}f(e'')\geq1$对于图$G$的每条边$e\in E$都成立. $w(f)=\sum_{e\in E}f(e)$称为函数$f$的权. $G$的符号边控制数$\gamma_{s}\,''(G)$是指$G$的所有符号边控制函数的最小权.本文对完全多部图的符号边控制数进行研究.对于完全$r$-部图, 当$r$为偶数并且各部的顶点数相同的情况下,我们得到了这一参数的若干下界和上界.     

图的符号星k控制数

引入了图的符号星k控制的概念.设G=（V,E）是一个图,一个函数f：E→{-1,＋1},如果∑e∈E[v]f（e）≥1对于至少k个顶点v∈V（G）成立,则称f为图G的一个符号星k控制函数,其中E（v）表示G中与v点相关联的边集.图G的符号星k控制数定义为γkss（G）=min{∑e∈Ef（e）｜f为图G的符号星k控制函数}.在本文中,我们主要给出了一般图的符号星k控制数的若干下界,推广了关于符号星控制的一个结果,并确定路和圈的符号星k控制数.     

图的符号星部分控制数

引入了图的符号星部分控制的概念.设G=(V,E)是一个简单连通图, M是V的一个子集.一个函数f:E→{-1,1}若满足∑e∈E(v)f(e)≥1对M中的每个顶点v都成立,则称f是图G的一个符号星部分控制函数,其中E(v)表示G中与v点相关连的边集.图G的符号星部分控制数定义为γM(85)(G)=min{∑e∈Ef(e)|f是G的符号星部分控制函数}.在本文中我们主要给出了一般图的符号星部分控制数的上界和下界,并确定了路、圈和完全图的符号星部分控制数的精确值.作为我们引入的这一新概念的一个应用,求出了完全图的符号星k控制数.     

关于给定符号圈控制数的图的刻画（英文）

设G=(V,E)是简单图.称一个函数f:E→{+1,-1}为图G的符号圈控制函数,若对G的每一导出圈C,有Σ_(e∈)E(C)f(e)≥1.G的符号圈控制数被定义为γ′_(sc)(G)=min{∑_(e∈E)f(e)|f是G的符号圈控制函数}.本文刻画了所有具有γ′_(sc)(G)=|E|-4的连通图G.     

完全图全符号控制数的较小上界和下确界

设图G=G(V,E),令函数f∶V∪E→{-1,1},f的权w(f)=∑x∈V∪Ef[x],对V∪E中任一元素,定义f[x]=∑y∈NT[x]f(y),这里NT[x]表示V∪E中x及其关联边、邻点的集合.图G的全符号控制函数为f∶V∪E→{-1,1},满足对所有的x∈V∪E有f[x]1,图G的全符号控制数γT(G)就是图G上全符号控制数的最小权,称其f为图G的γT-函数.本文得到了完全图全符号控制数的一个较小上界和下确界.     

两类图的逆符号边控制数

研究了图G的逆符号边控制数■.利用穷标法及分类讨论法,主要得到了两类图n·C_m和n-C_m逆符号边控制数的精确值,从而推广了已知结果.这里C_m表示长为m的圈,n·C_m和n-C_m分别表示恰有一个公共点和有一条公共边的n个圈的拷贝.     

图的逆符号边全控制数

设γ_(st)(G)是图G的逆符号边全控制数,p(n,k)是广义Petersen图.得到了γ_(st)(G)的两个上界,并且确定了γ_(st)(p(n,k)).     

关于图的符号边全控制数

引入了图的符号边全控制的概念,给出了一个连通图G的符号边全控制数γs′t(G)的下限,确定所有n阶树T的最小符号边全控制数,并刻划了满足γs′t(G)=E(G)的所有连通图G,最后还提出了一个关于γs′t(G)上界的猜想.     

几类图的Fractional星控制数

设G=(V,E)是一个无孤立点的图,一个实值函数f:E(G)→[0,1]若对所有的点u∈V(G),均有∑uv∈Ef(uv)≥1成立,则称f为图G的一个Fractional星控制函数.图G的Fractional星控制数定义为γ_(fs)(G)=min{∑uv∈Ef(uv)|f为图G的一个Fractional星控制函数}.研究了几类乘积图的Fractional星控制问题,给出了一些常见特殊图的Fractional星控制数,主要确定了积图P_m×P_n和C_m×P_n的Fractional星控制数.     

图 P2×Cn的均匀邻强边色数

对图G(V,E),一正常边染色f若满足(1)对(V)uv∈E(G),f[u]≠f[v],其中f[u]={f(uv)|uv∈E};(2)对任意i≠j,有||E|-|Ej||≤1,其中Ei={e| e∈E(G)且f(e)=i}.则称f为G(V,E)的一k-均匀邻强边染色,简称k-EASC,并且称Xcas(G)=min{k|存在G(V,E)的一k-EASC为G(V,E)的均匀邻强边色数.本文得到了图P2×Cn的均匀邻强边色数.     

关于图的减控制与符号控制

给定一个图G=(V,E),一个函数f:V→{-1,0,1}被称为G的减控制函数,如果对任意v∈V(G)均有∑_μ∈N[v]f(μ)≥1。G的减控制数定义为γ^-(G)=min{∑_v∈Vf(v)|f是G的减控制函数}。图G的符号控制函数的正如减控制函数,差别是广{-1,0,1}换成{-1,1}。符号控制数γ_s(G)是类似的。本文获得γ^-G)和γ_s(G)的一些下界。同时也证明并推广了 Jean Dunbar等提出的一个猜想,即对任意 n阶 2部图 G,均有γ^-(G)≥ 4(n+1^1/2-1)-n成立。     

Petersen图的Hamilton性和边色数

对简单图G(V,E),定义图G的关联图I(G)为V(I(G))={(ve)|v∈V(G)且e∈E(G)和v与e关联},E(I(G))={(ue,vf)Iu=v或e=f或uv=e或uv=f}.本文证明了Petersen图可被分解为边不交的Hamilton-圈和一个1-因子的并.     

Halin图的邻和可区别边染色与边权点染色

记[k]={1,2,…,k),称为颜色集.设φ:E(G)→[k]为图G的边集合到[k]的映射,令f(v)表示与顶点v关联的边的颜色的加和.如果对任意一条边uv∈E(G),都有φ(u)≠φ(v),f(u)≠f(v),则称φ为图G的邻和可区别[k]-边染色,k的最小值称为图G的邻和可区别边色数,记为ndi_Σ(G).若对任意一条边uv∈E(G),都有f(u)≠f(v),则称φ为图G的k-边权点染色,称图G是k-边权可染的.运用组合零点定理证明了对于最大度不等于4的Halin图有:ndi_∑(G)≤Δ(G)+2,并证明了任一Halin图是4-边权可染的.     

度为奇数的正则图的上负全控制数

f:v(G)→{一1,0,1}称为图G的负全控制函数,如果对任意点V∈V,均有f[v]≥1,其中 f[v]= ∑,f(u).如果对每个点v∈V,不存在负全控制函数g:V(G)→{-l,0,1),g≠f,满u∈N(v)足g(v)≤f(v),则称f是-个极小负全控制函数.图的上负全控制数F-t(G)=max{w(f)|f,是G的极小负全控制函数},其中w(f)=∑/v∈V(G)f(v).本文研究正则图的上负全控制数,证明了:令G是-个v∈V(G)n阶r-正则图.若r为奇数,则Γt-(G)＜＝r2 1/r2 2r-1n.