弦图的补图的最小填充

从图论观点讲,最小填充问题就是在一个图G中添加边集F,使得图G的母图G F是一个弦图而且所添边的边数| F|是最小的,其中最小值| F|称为图G的填充数,表示为f( G) .对一般图来说,最小填充问题是NP-困难的,但是对一些特殊图类来说,这个问题是在多项式时间内可解的.本文给出了弦图的补图-G的填充数f(-G) .     

k-树的补图的最小填充和树宽

一个图的最小填充问题是寻求边数最少的弦母图,一个图的树宽问题是寻求团数最小的弦母图,这两个问题分别在稀疏矩阵计算及图的算法设计中有非常重要的作用．一个k-树G的补图G称为k-补树．本文给出了k-补树G的最小填充数f(G) 及树宽TW(G)．     

标定自补图的计数

标定自补图的计数问题是“组合计数”理论中的著名难题，至今毫无进展，本文通过构造出阶≤９的全部自补图，获得了阶数的４，５，８和９的标定自补图的数目分别是１２，７２，１１２１４０和４６２７２２４。     

补图具有悬挂点且连通的图的最小特征值

图的最小特征值定义为图的邻接矩阵的最小特征值,它是刻画图的结构性质的重要参数.在给定阶数且补图为具有悬挂点的连通图的图类中,刻画了最小特征值达极小的唯一图,并给出了这类图最小特征值的下界.     

自补图中的三角形

该文证明了具有ｐ个顶点的自补图中三角形的数目至多是，当ｐ≡０（Ｍｏｄ４）时为ｐ（ｐ－４）（２ｐ－１）／４８，当ｐ≡１（ｍｏｄ４）时为（ｐ－１）（２ｐ２－７ｐ－３）／４８，并且此二数是最好可能的．     

关于图与补图的带宽的一个简单证明

关于图与补图的带宽,P.Z.Chinn,F.R.K.Chung,P.Erd?s和R.L.Graham证明了B(G)+B(G)≥n-2.本文给出一个简单证明.     

全局优化问题的一个单参数填充函数方法

利用改进的填充函数的定义,对一般的无约束最优化问题给出了一个新的单参数填充函数,分析并证明了此填充函数的性质.利用该填充函数,构造了新的算法,对此算法进行了数值实验,并将此算法做了比较,结果表明此填充函数算法是可行的.     

路的补图的色唯一性

设Pn表示n阶的路。[2]中刘猜测：如果n是偶数且n≠4,则/Pn色唯一的。本得到/Pn色唯一的充要条件,从而肯定的回作了刘提出的猜测。     

具有八个节点的自补图

In this note we deduce that there are exactly 10 self complement graphs on 8 vertices (G=G), which is characterized in the sort of degree sequences . It is a correction to the assertation made by Harary ( [ 1 ]) .     

k—一致超图的补图的Laplacian

引入了k-一致超图的补图的概念,并讨论了它的Laplacian与其补图的Laplacian之间的关系。     

The Minimum FIll—in for the Corona of Two Graphs

Ｔｈｅ　Ｍｉｎｉｍｕｍ　Ｆｉｌｌ－ｉｎ　ｆｏｒ　ｔｈｅ　Ｃｏｒｏｎａ　ｏｆ　Ｔｗｏ　ＧｒａｐｈｓＴｈｅＭｉｎｉｍｕｍＦｉｌｌ－ｉｎｆｏｒｔｈｅＣｏｒｏｎａｏｆＴｗｏＧｒａｐｈｓ￥ＪｉｎＺｈｉｙｏｎｇ；ＬｉＷｅｎｑｕａｎ（ＨｅｎａｎＵｎｉｖｅｒｓｉｔｙ...     

图的最小填充的分解定理

在计算数学领域,稀疏矩阵的最小填充排序问题由于其重要的实际意义而受到重视。本文从图论的观点提出一种处理方法,即运用分解定理来处理一些特殊结构,从而导出一些特殊图的最小填充数。     

序列平行图的最小填充

起源于稀疏矩阵计算和其它应用领域的一个图G的最小填充问题就是在G中寻找一个边数| F |最小的添加边集F,使得G+F是弦图.这里最小值| F |称为图G的填充数,表示为f(G).对一般图来说,这个问题是NP-困难问题.一些特殊图类的最小填充问题已被研究.本文给出了序列平行图G的最小填充数的具体值.     

最小填充问题的可分解性

起源于稀疏矩阵计算和其它应用领域的图G的最小填充问题是在图G中寻求一个内含边数最小的边集F使得G F是弦图.这里最小值|F|称为图G的填充数,表示为f(G).作为NP-困难问题,该问题的降维性质已被研究,其中包括它的可分解性.基本的可分解定理是:如果图G的一个点割集S是一个团,则G经由S是可分解的.作为推广,如果S是一个"近似"团(即只有极少数边丢失的团),则G经由S是可分解的.本文首先给出基本分解定理的另外一个推广:如果S是G的一个极小点割集且G-S含有至少|S|个分支,则G经由S是可分解的;其次,给出了这个新推广定理的一些应用.     

图的倍图与补倍图

计算机科学数据库的关系中遇到了可归为倍图或补倍图的参数和哈密顿圈的问题．对简单图C,如果V（D（G））：V（G）∪V（G′）E（D（G））=E（C）∪E（C″）U{vivj′｜vi∈V（G）,Vj′∈V（G′）且vivj∈E（G））那么,称D（C）是C的倍图,如果V（D（G））=V（C）∪V（G′）,E（D（C））：E（C）∪E（G′）∪{vivj′}vi∈V（G）,vj′∈V（G’）and vivj∈（G））,称D（C）是G的补倍图,这里G′是G的拷贝．本文研究了D（G）和D的色数,边色数,欧拉性,哈密顿性和提出了D（G） 的边色数是D（G）的最大度等公开问题．     

Complement and Isomorphism on Bipolar Fuzzy Graphs

In this paper, we discuss some properties of the self complement and self weak complement bipolar fuzzy graphs, and get a sufficient condition for a bipolar fuzzy graph to be the self weak complement bipolar fuzzy graph. Also we investigate relations between operations union, join, and complement on bipolar fuzzy graphs.     

以完全二部图作为星补的正则图的刻画

设$G$是一个$n$阶图, $\mu$是$G$的一个$(k\ge 1)$重邻接特征值. 图$G$中关于$\mu$的星补$H$是指$G$的不含特征值$\mu$的$n-k$阶诱导子图,且顶点集$X=V(G-H)$称为图$G$中关于$\mu$的星集.星补技术提供了利用部分子结构来重建满足特定性质的整个图的谱工具. 本文我们研究了关于特征值$\mu$的以$K_{t,s}~(s\ge t\ge 2)$作为是补的正则图, 特别地, 我们完全刻画了$t=3$的情形, 获得了当$t=s$时的一些性质, 并提出了有待进一步研究的问题.