完全图与完全n部图的完全多部图分解

§ 1　IntroductionLet V(G) and E(G) be the vertex setand the edge setof a graph G,respectively.Fori=1 ,...,p,if V(Gi) V(G) ,E(Gi)∩ E(Gj) = for i≠ j,and∪pi=1 E(Gi) =E(G) ,then wecall{ G1 ,...,GP} a decomposition of G.Let[i,j] be the integer interval including i and j.Let Knbe a complete graph with the vertex set[1 ,n] .For m disjointsubsets A1 ,...Amof[1 ,n] ,let K(A1 ,...,Am) be a complete m-partite graph having partite-sets A1 ,...,Am.If| Ai| =1 ,Ai is called a S-set;otherwi…     

树的补图的区间图完全化问题

一个图G的区间图完全化问题包含两类子问题:侧廓问题和路宽问题,分别表示为P(G)和PW(G),其中侧廓问题是寻求G的一个边数最小的区间超图;路宽问题是寻求G的一个团数最小的区间超图.这两类子问题分别在数值代数、VLSI-设计和算法图论等学科领域中有重要的应用.对一般图来说,两类子问题都是NP-完全问题;但是对一些特殊图类来说,它们在多项式时间内可解.本文给出了树T的补图的具体侧廓和路宽值.     

完全多部图的区间图完全化问题

The interval graph completion problem of a graph G includes two class problems: the profile problem and the pathwidth problem, denoted as P(G) and PW(G) respectively, where the profile problem is to find an interval supergraph with the smallest possible number of edges; the pathwidth problem is to find an interval supergraph with the smallest possible cliquesize. These two class problems have important applications to numerical algebra, VLSI-layout and algorithm graph theory respectively; And they are known to be NP-complete for general graphs. Some classes of special graphs have been investigated in the literatures. In this paper the exact solutions of the profile and the pathwidth of the complete multipartite Graph Kn1,n2,…,nr(r≥2) are determined.     

一般赋权图上的运输问题

针对实际应用,定义一般赋权图上的运输问题,建立数学模型解决该问题,并给出了一个简单的应用.     

九树十行问题的完全解答

九树十行问题的完全解答齐齐哈尔教育学院刘毅本文约定把满足“九树十行问题：把九棵树栽成十行，使每行信有三棵”的图形叫做构图，其中通过各个点（称树为点）的直线（称行为直线）的条数叫做该点的叉数．本文以构图表（类似［１］中的构形表）为工具．讨论构图的必要条...     

完全多部图的树划分数的直观证明

r-边染色图G的树划分数tr(G)定义为最小的正整数k,使得只要用r种颜色对图G进行边染色,则存在至多k个顶点不交的单色树覆盖图G的所有顶点.K aneko等确定了t2(K(n1,n2,…,nk))的精确表达式.本文给出了该表达式的一个直观证明.     

完全三部图K(n-k,n,n)的色唯一性

通过对图的特征子图个数的比较,给出了图K(n-k,n,n)色唯一性的数值条件.     

关于完全三部图K(n,n,n+4)的色唯一性

通过比较两个图的色多项式的系数(本文使用了五独立集数)、顶点集、边集、三角形和四圈的个数,证明了K(2,2,6)是色唯一图,从而部分地回答了文[5],[7]中遗留的一个问题,并得到图K(n,n,n 4)(n=2或n 4)是色唯一的.     

树的线图的图扩充问题

图G的弦图扩充问题包含两个问题:图G的最小填充问题和树宽问题,分别表示为f(G)和TW(G);图G的区间图扩充问题也包含两个问题:侧廓问题和路宽问题,分别表示为P(G)和PW(G).对一般图而言,它们都是NP-困难问题.一些特殊图类的填充数、树宽、侧廓问题和路宽具体值已被求出.主要研究树T的线图L(T)的弦图扩充问题;其次涉及到了两类特殊树—毛虫树和直径为4的树的线图的区间图扩充问题.     

最优场址问题的研究进展

３０年代以来，最优场址问题一直是运筹学界阳活跃的研究领域之一。此问题具有深镔实验背景和广泛的实用价值。本文综述了最优场址问题研究进展并对其发展历史进行了简单的回顾，主要介绍近年来最优场址问题研究的一些重要成果，对每一种成果进行了基本的评论。     

伪完全二分图PK_(n,n)奇优美标号的计算机实现

给出了伪完全二分图PK_(n,n)的定义及性质,提出了该类图的奇优美标号算法,证明了算法的正确性及时间复杂度,从而证明了伪完全二分图的奇优美性.并给出了伪完全二分图PK_(n,n),当n=3,4,5的一种标号方法.     

分裂图的区间图完全化问题（英文）

The interval graph completion problem on a graph G is to find an added edge set F such that G + F is an interval supergraph with the smallest possible number of edges. The problem has important applications to numerical algebra, V LSI-layout and algorithm graph theory etc; And it has been known to be N P-complete on general graphs. Some classes of special graphs have been investigated in the literatures. In this paper the interval graph completion problem on split graphs is investigated.     

关于完全3-部图K1,6,n的交叉数

早在上世纪五十年代,Zarankiewicz猜想完全2-部图Km,n(m≤n)的交叉数为[m/2][m-1/2][n/2][n-1/2](对任意实数x,[x]表示不超过x的最大整数)．目前这一猜想的正确只证明了当m≤6时成立．本文主要证明了若Zarankiewicz猜想对m=7成立,则完全3-部图K1,6,n的交叉数为9[n/2][n-1/2] 6[n/2]．     

路与完全图的笛卡尔积图和广义图K(n,m)的关联色数

Richrd A.Brualdi和J.Quinn Massey在[1]中引入了图的关联着色概念,并且提出了关联着色猜想,即每一个图G都可以用△(G)+2种色正常关联着色.B.Guiduli[2]说明关联着色的概念是I.Algor和N.Alon[3]提出的有向星荫度的一个特殊情况,并证实[1]的关联着色猜想是错的,给出图G的关联色数的一个新的上界是△(G)+O(Log(△G)).[4]确定了某些特殊图类的关联色数.本文给出了路和完全图的笛卡尔积图的关联色数,而且利用此结果又确定了完全图Kn的广义图K(n,m)的关联色数.     

3-正则图的分割问题是NP-完全问题

证明了3-正则图的最小平分问题和最小α-分割问题都是NP-完全问题.     

关于q-树二次整子图和n阶加点q-树色多项式的注记

在这篇文章中我们成功地仅用色多项式表征了最小度不等于q-3的q-树的二次整子图和n阶加点q-树,即当图的最小度δ(G)≠q-3时,n阶图G具有色多项式P(G;λ)=λ(λ-1)…(λ-q+2)(λ-q+1)~3(λ-q)~(n-q-2), n≥q+2,当且仅当G是n阶q-树的二次整子图或n阶加点q-树.     

有关完全图的图的紧性

双随机矩阵有许多重要的应用,紧图族可以看作是组合矩阵论中关于双随机矩阵的著名的Birkhoff定理的拓广,具有重要的研究价值.确定一个图是否紧图是个困难的问题,目前已知的紧图族尚且不多,给出了三个结果:任意多个完全图的不交并是紧图;圈C_3与圈C_n(n3)的不交并是非紧图;当n是大于等于3的奇数时,完全图K_n与图K_(n+1)的不交并是非紧图,其中图K_(n+1)是从完全图K_(n+1)删去一因子而得到的图.     

图的完全正则自同态

作为图的代数分析的一部分，对图的自同态幺半群的研究近年来有一定的进展（参见［３］及［４］）。这类研究的主要目的在于将半群理论应用于图论。文献［５］研究了图的正则自同态及其逆。在此基础上本文进一步描述了图的完全正则自同态的组合特征；同时对含有完全正则自同态ｆ的极大子群，文中也明确给出了其单位元素及ｆ的逆     

图的最小控制树问题（英文）

A dominating tree T of a graph G is a subtree of G which contains at least one neighbor of each vertex of G.The minimum dominating tree problem is to find a dominating tree of G with minimum number of vertices,which is an NP-hard problem.This paper studies some polynomially solvable cases,including interval graphs,Halin graphs,special outer-planar graphs and others.