从节点度数生成无向简单连通图

许多现实问题可以抽象成无向简单连通图的生成问题。为了从节点的度数序列得到所有可能的无向简单连通图,针对度数序列设计了适合用计算机实现的去点回溯算法,证明了算法的正确性,通过每一步去点回溯后的变化矩阵,得到生成无向简单连通图所需的邻接矩阵,并最终用计算机实现了该算法,解决了节点度数已知时无向简单连通图的生成问题。

简单连通图的反比度和几何反比度

反比度和几何反比度是Graffiti猜想程序中首先出现的关于图的两个量 .本文研究了它们的性质 。

最少边数的n阶3-点连通简单图及其构造

从图的度数列入手,采用一种特殊的构造方法,不仅得到了3-点连通简单图的最少边数c(G)的值,还得到了图的边数最少时的连通简单图.

二连通三正则简单图的最大亏格及结构性质(英文)

已知二连通三正则简单图的最大亏格至少为其圈秩的三分之一 .且 ,此下界可以达到 .本文表明这种达到最大亏格下界的图具有特殊结构 ,而且其节点数可被三整除 .同时 ,还证明了当节点数不可被三整除时 ,这种图最大亏格的下界可提高一个亏格 .

关于最大亏格达到下界的三连通三正则简单图(英文)

已被证明二连通三正则简单图的最大亏格至少为其圈秩的三分之一 且 ,当节点数可被三整除时 ,这个下界可以达到 本文提供了达到最大亏格下界的三连通三正则简单图所具有特殊结构 。

关于非广义多边形路的2连通简单MCD图

令 Sn 是具有 n个顶点没有两个等长圈的简单图的集合 .若 Sn 中不存在图 G′使|E(G′) |>|E(G) |,则称图 G是简单 MCD图 .若简单 MCD图 G是 2连通的 ,则称 G是 2连通简单 MCD图 .若 G中一条路 P的每个内点 v都有 d G(v) =2 ,则称 P为 G的简单路 .一个 2连通可平面图 G称为广义多边形路 ,如果用下述方法得到图 G*是路 :对应于 G的每个内部面 f (G是G的平图 )有一个 G*的顶点 f * ,G*的两个顶点 f*和 g*在 G*中相邻当且仅当 G中相应的两个内部面的边界交于一条 G的简单路 .作者证明了下述结果 :当且仅当 n∈ {1 0 ,1 1 ,1 4,1 5,1 6,2 1 ,2 2 }时 ,存在 n个顶点的非广义多边形路的 2连通简单 MCD图 .

2－连通简单MCD图边数的一个新的下界

设Ｇ是具有ｎ个顶点的２－连通简单ＭＣＤ图，ｆ２（ｎ）表示Ｇ的边数．本文证明了当ｎ≥８时，其中ｘｍ＝ｕｍ－２ｕｍ－５，ｕｍ是Ｆｉｂｏｎａｃｃｉ数．

连通简单图的典型着色

本文用图论知识利用连通简单图G的邻接矩阵来寻求其互不相交的极大独立集的方法,解决连通简单图G的典型着色问题.

点可迁图的限制边连通度

设Ｓ是连通图Ｇ的边子集．如果Ｇ－Ｓ不连通而且不含孤立点，那么称Ｓ是Ｇ的一个限制边割，Ｇ中所有限制边割中最小边数称为Ｇ的限制边连通度，记为λ＇（Ｇ）．限制边连通度是对传统边连通度的推广，而且是计算机互连网络容错性的一个重要度量．点可迁图是一类重要的网络模型．本文证明了如下结论： 设 Ｇ是连通的点可迁图．如果 Ｇ的点数ｎ≥ ４，而且点度ｋ≥ ２，那么或者λ＇（Ｇ）＝ ２ｋ－２，或者ｎ是偶数，Ｇ含三角形且存在整数ｍ≥２，使得ｋ≥λ＇（Ｇ）＝ｎ／ｍ≤２ｋ－３．

特征值不超过2的连通图

设Γ是简单连通图 ,AΓ 是Γ的连接矩阵 ,λ1 表示AΓ 的最大特征值 .证明了λ1 <2当且仅当Γ是Dynkin图 ,λ1 ≤ 2当且仅当Γ是Euclidean图 .

关于连通图端片的一些结果

设G=(V,E)为简单连通图,A V.G[A]称为G的断片,如果存在极小割S,使得G[A]是G-S的分支.G[A]称为G的端片,如果G[A]为G的断片,且对A的任何真子集B,G[B]不是G的断片.给出G的端片的一些性质,得到端片个数Σ≤|V|的结论,并给出等号成立的一些必要条件及充分条件.

关于邻点可区别全染色的几个新结果

邻点可区别全染色是在正常全染色的定义下,使得任两相邻顶点的色集不同.顶点v的色集是v的颜色及其与v关联的所有边的颜色.我们给出了几类特殊图的邻点可区别全色数.

双圈图的Laplace谱半径

利用图的度序列和顶点的邻域 ,根据图的阶数n研究了双圈图的Laplace矩阵的最大特征值 .确定了最大Laplace矩阵特征值为n的双圈图 ,以及最大Laplace矩阵特征值介于n与n -

C3n^2，C4n^2邻点可区别的全染色

设G(V ,E)是阶数不小于 2的简单连通图 ,n是自然数 ,V∪E到 { 1,2 ,… ,k}的映射f满足 uv∈E(G) ,f(u)≠f(v) ,f(u)≠f(uv) ≠f(v) ; uv,uw∈E(G) ,(v≠w) ,f(uv)≠f(uw) ; uv∈E(G) ,G(u) ≠C(v) .其中C(u) =f(u) ∪ {f(uv)｜uv∈E(G) } .f称为G(V ,E)的一个邻点是可区分的全染色法 ,简记为k AVDTC .其中最小的k称为G的邻点可区别的全色数 .G2 是G再加上G中点间距离为 2时连边后的图 .本文得到了 3n、4n阶圈C23n,C24n 的邻点可区别的全色数 .

关于冠图的关联着色

证明“每个 G图能用 Δ+2种颜色进行关联着色”的 ICC猜想对一些图的冠图是成立的 .

哈密顿线图的一个充分条件

对于图G的任意边e=uv,边的度定义为d(e)=d(u)+d(v),其中d(u)和d(v)分别为顶点u和v的度.本文的主要结果是: 设G是几乎无桥的p≥2阶简单连通图,且G(?)K_(1,p-1),若对任意相距为2的两边e_1和e_2,d(e_1)+d(e_2)≥2p-6,则G有一个D—闭迹,从而G的线图L(G)是哈密顿的.

图K( r,2 )的邻强边色数(英文)

本文给出了每部有2个点的完全r-部图(r≥2 )的邻强边色数.

谱半径前六位的n阶单圈图

恰含一个圈的简单连通图称为单圈图.Cn记n个顶点的圈.Δ(i,j,k)记C3的三个顶点上分别接出i,j,k条悬挂边所得的图,其中i≥j≥k≥0.Sn-ll记Cl的某一顶点上接出n-l条悬挂边所得到的图.Δ(n-4+1,0,0)记Δ(n-4,0,0)的某个悬挂点上接出一条悬挂边所得到的图.本文证明了:若把所有n(n≥12)阶单圈图按其最大特征值从大到小的顺序排列,则排在前六位的依次是Sn-33,Δ(n-4,1,0),Δ(n-4+1,0,0),Sn-44,Δ(n-5,2,0),Δ(n-5,1,1).

几类有趣图的邻点可区别全染色

在正常全染色的定义下,使得任两相邻顶点的色集不同,这就是邻点可区别全染色.顶点v的色集是v的颜色其与及v关联的所有边的颜色.我们给出了几类有趣图的邻点可区别全色数.

P_n×P_m图的邻点可区别全染色和邻点强可区别全染色

对Pn×Pm图的邻点可区别全染色和邻点强可区别全染色问题进行了探讨,给出了染色数公式Xat(Pn×Pm)={4 n=m=2 5 n=2 m≥3,ast(pn×pm)=6 n≥3 n≥3{5 n=m=25 n=2 m≥3 6 n≥3