Bondage Number of 1-Planar Graph

The bondage number of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph a domination number greater than the domination number of G. In this paper, we prove that for a 1-planar graph G.

关于图的bondage数的一点注记

对B.Hartnell关于图的bondage数的一个定理给出一个新的证明,并得到一些关于平面图的有用的结果.

外平面图的围长和分数色数

讨论了外平面图的围长和分数色数的关系 ,给出了分数色数的一个上界 ;对于固定的整数g ,给出了围长是g的外平面图的分数色数的上确界f0 (g) ,并得出若n为正整数 ,有f0 (2n) =f0 (2n +1) =2 +1 n成立 .

最大度至多为6的平面图的L(2,1)-标号

令Δ(G),g(G)和λ(G)分别为图G的最大度,围长,和L(2,1)-标号数.证明了若G是Δ(G)≤6和g(G)≥5的平面图,则λ(G)≤Δ(G)+13.进而关于Δ(G)≤6和g(G)≥5的平面图G,这个界要比先前的结果好.

最大度至多为5的平面图的单射染色

图G的一个单射k-染色是一个映射f:V(G)→{1,…,k},其中f满足对任意的不同顶点u,v∈V(G),若u和v具有共同的相邻顶点,则f(u)≠f(v).并称iχ(G)=min{k|G存在一个单射k-染色}为图G的单射色数.证明了若G是最大度Δ(G)≤5且围长g(G)≥5的平面图,则iχ(G)≤Δ(G)+6.此界限好于之前关于Δ(G)≤5和g(G)≥5的平面图G的证明结果.

超环面图上的约束数(英文)

非空图G的约束数b(G)是指使得图G的控制数γ(G)增大而删除的最少的边数.[Fischermann M,Rautenbach D,Volkmann L.Remarks on the bondage number of planar graphs.Discrete Math,2003,260:57-67]已经证明,对于一个围长为g(G)的平面图G,如果g(G)≥4则b(G)≤6,如果g(G)≥5则b(G)≤5,如果g(G)≥6则b(G)≤4,如果g(G)≥8则b(G)≤3.我们把这个结果推广到连通的超环面图中.

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

本文研究了围长至少为5的平面图的线性着色问题。利用反证法,通过分析最小反例图的结构,运用欧拉公式结合适当的权转移规则得出矛盾,从而证明了围长至少为5的平面图的线性色数满足lc(G)≤[△(G)/2]+4,改进了这方面的结果。

平面图的绑定数

图G的绑定数b(G)是指边集合的最少边数,当这个边集合从G中去掉后所 得图的控制数大于G的控制数． Fischermann等人在[3]中给出了两个猜想: (1)如果 G是一个连通的平面图且围长g(G)≥4,则b(G)≤5;(2)如果G是一个连通的平面图且 围长g(G)≥5,则b(G)≤4．设n3表示度为3的顶点个数,r4和r5分别表示长为4和 5的圈的个数．本文,我们证明了如果r4<(5n3)/2+10,则猜想1成立;如果r5<12,则猜 想2成立．

围长至少为5的平面图的L(p,q)-标号

令λp,q(G)为图G的L(p,q)-标号数,其中p和q是两个正整数且p≥q。证明了若G是围长g(G)≥5的平面图,则λp,q(G)≤(2q-1)Δ(G)+6p+10q-8。由此导得对于g(G)≥5且Δ(G)≥16的平面图G,Wegner的猜想成立。

围长至少为6的平面图的L(p,q)-标号

令λp,q(G)为图G的L(p,q标)-号数,其中p和q是正整数且p≥q。证明了若G是围长g(G)≥6的平面图,则λp,q(G)≤(2q-1)Δ(G)+4p+6q-5;若G是围长g(G)≥6且Δ(G)≠5的平面图,则λp,q(G)≤(2q-1)Δ(G)+10p-2q-4。这一结果暗含着对于g(G)≥6且Δ(G)≠5的平面图G,Wegner的猜想成立。

三类超越可平面图的结构及其约束数

如果一个图可以嵌入在平面内使得每条边最多被交叉一次,则称该图为1-可平面图.如果一个图可以嵌入在平面内使得任何两个交叉不共享关联点,则称该图为IC-可平面图.如果一个图可以嵌入在平面内使得任何两个交叉最多共享一个关联点,则称该图为NIC-可平面图.1-可平面图,IC-可平面图与NIC-可平面图是三类重要的超越可平面图,它们在模块网络,社交网络和生物网络上有着重要的应用.图的约束数是为了使图的支配数严格增加所需要删除的最少的边数,它是衡量网络脆弱性的一个重要参数.本文考虑1-可平面图,IC-可平面图与NIC-可平面图的结构,并利用得到的结构定理证明了它们的约束数分别最多是13,11与12.