覆盖数不超过3的图上渡河问题

1000多年前,英国著名学者Alcuin曾提出一个古老的渡河问题,即狼、羊和卷心菜的渡河问题。2006年,Prisner把该问题推广到任意的冲突图上,考虑了一类情况更一般的渡河运输问题。所谓冲突图是指一个图G=(V,E),这里V代表某些物品的集合,V中的两个点有边连结当且仅当这两个点是冲突的,即在无人监管的情况下不允许留在一起的点。图G=(V,E)的一个可行运输方案是指在保证不发生任何冲突的前提下,把V的点所代表的物品全部摆渡到河对岸的一个运输方案。图G的Alcuin数定义为它存在可行运输方案时所需船的最小容量。本文讨论了覆盖数不超过3的连通图的Alcuin数,给出了该类图Alcuin数的完全刻画。     

平面图的Alcuin数

广义渡河问题是一类重要的组合优化问题,它是经典的狼-羊-卷心菜游戏的推广。冲突图是一个图,这个图的任意两个点所代表的物品不相容时(例如,狼和羊代表的物品不相容),则在这两个点之间连结一条边。渡河覆盖问题的目的是确定冲突图全部点所代表的物品从河的一岸安全地摆渡到河的对岸时所需船的最小容量,而冲突图的Alcuin数定义这个最小容量。本文讨论了平面图的Alcuin数, 给出了该类图Alcuin数的完全刻画。     

超图的Alcuin数与其横贯数的关系

1000多年前, 英国著名学者Alcuin曾提出过一个古老的渡河问题, 即狼、羊和卷心菜的渡河问题. 最近, Prisner和Csorba等考虑了一般``冲突图"上的渡河问题. 将这一问题推广到超图$H=(V,\mathcal{E})$\,上, 考虑一类情况更一般的运输计划问题. 现在监管者 欲运输超图中的所有点\,(代表``items")\,渡河, 这里$V$的点子 形成超边 当且仅当这些点代表的``items"在无人监管的情况下不能留在一起. 超图$H$的Alcuin数是指超图$H$具有可行运输方案\,(即把$V$的点代表的``items" 全部运到河对岸)\,时船的最小容量. 给出了 $r$-一致完全二部超图和它的伴随超图, 以及$r$-一致超图的Alcuin数, 同时证明了判断$r$-一致超图是否为小船图是NP 困难的.     

匹配数与控制数相等的图的结构性质

我们分别用γ(G)，β(G)和α(G)表示图G的控制数、匹配数和覆盖数，对任意连通图，有γ(G)≤β(G)≤α(G)成立，1998年，Randerath和Volkmann给出了控制数等于覆盖数的图的特征，本文首先证明了匹配数与控制数相等的图其最小度不超过2，而后给出了最小度为2的图的结构性质。     

Δ(G)≤4的外平面图的邻强边色数

研究了Δ(G)≤4的外平面图的邻强边染色,证明了Δ(G)≤χ′as(G)≤Δ(G)+1,且χ′as(G)=Δ(G)+1当且仅当存在两个最大度点相邻,其中Δ(G)和χ′as(G)分别表示图G的最大度和邻强边色数,并且提出了如下猜想:如果G是一个|V(G)|≥3(G≠C5)的2-连通图,则Δ(G)≤χ′as(G)≤Δ(G)+2.     

若干图的点强全着色

图G(V,E)的一正常k-全着色σ称为G(V,E)的一个k-点强全着色,当且仅当v∈V(G),N[v]中的元素着不同颜色,其中N[v]={u|vu∈E(G)}∪{v}.并且vχsT(G)=min{k|存在G的一个k-点强全着色}称为G(V,E)的点强全色数.本文得到了一些特殊图的点强全色数χvTs(G),并提出猜想:对于简单图G,有k(G)≤χvTs(G)≤k(G)+1,这里k(G)表示图G中所有顶点间距离不超过2的点集的最大顶点数.     

平面图上的团横贯数与独立数

设G为简单图,若G的点子集S与图中的每个团都有非空的交,则称S是图G的一个团横贯集,这里G的团是指图中的极大完全子图且至少包含两个点.图G的最小团横贯集所含点的数目称为G的团横贯数,记作τC(G).如果G的每条边至少包含在一个t阶完全子图中且τC(G)≤|V(G)|/t,则称G具有〈t〉一性质.提出了平面图分离4-团的概念.首先证明了最大度不超过5的平面图具有〈t〉-性质.其次,对任意平面图G,若它不含分离4-团且每条边都包含在一个4-团之中,得到了它的横贯数的上界和独立数的可达下界.     

不含相交6-圈的曲面图的列表单射染色

图G的一个点染色称为单射染色,如果任何两个有公共邻点的顶点染不同的颜色·一个图G称为单射κ-可选择的,如果对于顶点V(G)的任何一个大小为κ的允许颜色列表L,都存在一个单射染色φ,使得对于v∈V(G),有φ(v)∈L(v)使得G为单射κ-可选择的最小κ,称为G的单射可选择数,记作X_i~l(G).设G是最大度为Δ,围长为g的可嵌入到欧拉示性数X(∑)≥0的曲面∑的一个图,证明了若Δ≥7,g≥6,且不含有相交6-圈,则x_i~l(G)≤Δ+2.     

最大度不小于6的伪-Halin图的完备色数

设G为2-连通平面图,若存在G的面f₀,其中f₀的边界构成的圈上无弦且V（f₀）中的点的度至少为3,使得在G中去掉f₀边界上的所有边后得到的图为除V（f₀）中的点外度不小于3的树T,则称G为伪-Halin图;若V（f₀）中的点全为3度点,则称G为Halin-图.本文研究了这类图的完备色数,并证明了对△（G）≥ 6的伪-Halin图 G有 X_C（C）=△（G）+1.其中△（G）和X_C（G）分别表示G的最大度和完备色数.     

若干圈限制平面图的星边染色

图G的星边染色是指G的一个正常边染色,使得G中任一长为4的路和长为4的圈均不是2-边染色的.图G的星边色数χ’_st(G)表示图G有星边染色的最小颜色数.设G是最大度为Δ的平面图,我们证明了:(1)若G不含4-圈,则χ’_st(G)≤[1.5Δ]+15;(2)若g≥5,则χ’_st(G)≤[1.5Δ」+10;(3)若g=7,则χ’_st(G)≤[1.5Δ」+6.     

The Ferry Cover Problem on Regular Graphs and Small-Degree Graphs

The ferry problem may be viewed as generalizations of the classical wolf-goat-cabbage puzzle. The ferry cover problem is to determine the minimum required boat capacity to safely transport n items represented by a conflict graph. The Alcuin number of a conflict graph is the smallest capacity of a boat for which the graph possesses a feasible ferry schedule. In this paper the authors determine the Alcuin number of regular graphs and graphs with maximum degree at most five.     

The Ferry Cover Problem on Regular Graphs and Small-Degree GraphsThe Ferry Cover Problem on Regular Graphs and Small-Degree Graphs

The ferry problem may be viewed as generalizations of the classical wolf-goatcabbage puzzle. The ferry cover problem is to determine the minimum required boat capacity to safely transport n items represented by a conflict graph. The Alcuin number of a conflict graph is the smallest capacity of a boat for which the graph possesses a feasible ferry schedule. In this paper the authors determine the Alcuin number of regular graphs and graphs with maximum degree at most five.     

某些中间图的邻点可区别E-全色数

设G（V,E）是简单连通图,T（G）为图G的所有顶点和边构成的集合,并设C是k-色集（k是正整数）,若T（G）到C的映射f满足：对任意uv∈E（G）,有f（u）≠f（v）,f（u）≠f（uv）,f（v）≠f（uv）,并且C（u）≠C（v）,其中C（u）={f（u）}∪{f（uv）｜uv∈E（G）}.那么称f为图G的邻点可区别E-全染色（简记为k-AVDETC）,并称χ_（at）~e（G）=min{k｜图G有k-邻点可区别E-全染色}为G的邻点可区别E-全色数.图G的中间图M（G）就是在G的每一个边上插入一个新的顶点,再把G上相邻边上的新的顶点相联得到的.探讨了路、圈、扇、星及轮的中间图的邻点可区别E-全染色,并给出了这些中间图的邻点可区别E-全色数.     

围长至少为5的平面图的线性染色

如果图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色.图G的线性色数用lc(G)表示,是指G的所有线性染色中所用的最少颜色的个数本文证明了对于每一个最大度为△(G)且围长至少为5的平面图G有lc(G)≤[△(G)/2]+5,并且当△(G)∈{7,8,…,14...     

围长至少为4的平面图的邻点可区别边色数

图G的邻点可区别边染色是G的正常边染色,使得每一对相邻顶点有不同的颜色集合．G的邻点可区别边色数X＇a（G）是使得G有一个k-邻点可区别边染色的最小正整数七．本文证明了：若G是围长至少为4且最大度至少为6的平面图,则X＇a（G）≤△＋2．     

平面图线性色数的一个上界

如果图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色．图G的线性色数用lc（G）表示,是指G的所有线性染色中所用的最少颜色的个数．证明了：若G是一个最大度△（G）≠5,6的平面图,则lc（G）≤2△（G）．     

完全图及完全二部图的点可区别Ⅳ-全染色

设G是简单图,图G的一个k-点可区别Ⅵ-全染色(简记为k-VDIVT染色),f是指一个从V(G)∪E(G)到{1,2,…,k}的映射,满足:()uv,uw∈E(G),v≠w,有,f(uv)≠f(uw);()u,V∈V(G),u≠v,有C(u)≠C(v),其中C(u)={f(u)}∪{f(uv)|uv∈E(G)}.数min{k|G有一个k-VDIVT染色}称为图G的点可区别Ⅵ-全色数,记为x_(vt)~(iv)(G).讨论了完全图K_n及完全二部图K_(m,n)的VDIVT色数.