图与补图全独立数间的关系

对图G(V,E),V∪E中既不相邻、又不相关联的最大元素个数,称为G的全独立数,并简记为α_T(G)。本文研究了图和补图全独立数之间的关系,得到α_T(G) α_T(G~C)≤「3y 1/2」。其中y=|V(G)|,G~C是G的补图,「x」为不大于x的最大整数,且界可达。     

弦图子类的全控制函数

本文首先证明了k-全控制问题和符号全控制问题在双弦图上均为NP-完全的.其次,在强消去序已给定的强弦图上,给出了求解符号全控制、负全控制、k-全控制和k-全控制问题的统一的O(m+n)时间算法.     

高度正则图的全着色

一个图$G$的全色数$\chi_T(G)$ 是对$G$的边和顶点着色的最小数, 使得相关联或相邻元素着不同色. 证明了如果$G$是正则图并且$d(G)\ge\cfrac{2}{3}|V(G)|+\cfrac{23}{6},$ 这里$d(G)$ 表示在$G$中顶点的度, 则$\chi_T(G)\leq d(G)+2$.     

阶数极大的临界全控制图

称一个没有孤立点的图G 为临界全控制图, 如果G 满足对于任何一个不与悬挂点相邻的顶点v, G - v 的全控制数都小于G 的全控制数. 如果G 的全控制数记为γ_t, 则称这样的临界全控制图G 为γ_t- 临界的. 如果G 是γ_t- 临界的, 且阶数为n, 则n ≤ Δ(G)(γ_t(G)- 1) + 1, 其中Δ(G) 是G 的最大度. 本文将证明对γ_t = 3, 这个阶数的上界是紧的, 并给出所有满足n = Δ(G)(γ_t(G)- 1) + 1 的3-γ_t- 临界图.     

5-正则图的全控制数的一个注记

设G是不含孤立点的图,S是G的一个顶点子集,若G的每一个顶点都与S中的某顶点邻接,则称S是G的全控制集.G的最小全控制集所含顶点的个数称为G的全控制数,记为γt(G).Thomasse和Yeo证明了若G是最小度至少为5的n阶连通图,则γt(G)≤17n/44.在5-正则图上改进了Thomasse和Yeo的结论,证明了若G是n阶5-正则图,则,γt(G)≤106n/275.     

图的全控制数和匹配数的可比较性

设tγ(G)为G的全控制数.证明了:(1)对广义θ-图G,tγ(G)≤α(G) 1;(2)对任意k-正则无爪图G,k≥3,有tγ(G)≤α(G).这里α(G)表示G的匹配数.作为结果(2)的推论,对k-正则无爪图(k≥3),证明了Favaron猜想是成立的.即对最小度不小于3的简单图,有tγ(G)≤12 V(G).此外,举例说明了当图的最小度不超过2时,对一般图而言,匹配数与全控制数不可比较.     

图的全符号控制数

本文考虑的图G均为有限简单连通图, 是一个有顶点集合V边集合E的有限简单连通图，用V(G) 和E(G) 分别表示G的顶点集和边集. f 是一个从V(G)∪E(G)→{-1, 1}的函数. f 的权重定义为 w(f)=∑_{x∈V(G)∪E(G)}f(x). 对任一元素x∈V(G)∪E(G), 定义f[x]=∑_y∈NT[x]f(y). 图G的全符号控制函数f : V(G)∪ E(G)→{-1, 1}是一个对所有的x∈ V(G)∪ E(G), 都满足f[x]≥1的函数. G的所有全符号控制函数中最小的权定义为G 的全符号控制数，记作γ_s^*(G). 讨论了图的全符号控制数, 证明了图的全符号控制数的下界, 并对一些特殊的图类C_n 和P_n本文得到了全符号控制数的精确值.     

一些联图的均匀全染色

对-个正常的全染色满足各种颜色所染元素数(点或边)相差不超过1时,称为均匀全染色,其所用最少染色数称为均匀全色数.本文证明了图在若干情况下的均匀全色数定理,得到了Cm VSn,CmVFn和CmVWn的均匀全色数.     

一些联图的均匀全染色

对一个正常的全染色满足各种颜色所染元素数(点或边)相差不超过1时,称为均匀全染色,其所用最少染色数称为均匀全色数.本文证明了图在若干情况下的均匀全色数定理,得到C_m∨S_nC_m∨ F_n和C∨W_n的均匀全色数.     

关于给定控制数的连通二部图的极大图的刻画

本文研究了给定控制数的连通二部图的极大图的结构问题.利用分类讨论思想和数学归纳法,刻画了控制数等于3和大于等于4这两类边数达到极值时的连通二部图.本文所得结果可用于进一步研究给定全控制数的连通二部图的极大图问题.     

有向路和有向圈的控制集数

1引言设G=(V,E)为无向图．子集D (?)V(G)是无向图G的控制集,如果对于任意的y,∈V(G)-D,都存在x∈D,使xy∈E(G)．G的控制集D是G的分裂控制集,如果G中由V(G)-D导出的子图G〈V(G)-D〉是不连通的．G的一个控制集D是G的一个强(弱)控制集,若dG(x)≥d_G(y)(d_G(x)≤d_G(y)),其中d_G(x)表示G中与点x关联的边数．对于有向图H=(V,A),子集D(?)V(H)称为H的控制集,如果对于任意的y∈     

求解群体多目标最优化问题的联合有效数法

群体多目标最优化是群体决策和多目标最优化相交叉的一个边缘研究领域,其主要特点是对由多个决策者提供的具多个目标的最优化问题,进行定量和定性相结合的方案选优或决策排序.因此,它的理论和方法在现代社会的重大决策中有着广阔的应用前景.     

On Domination Number of 4-Regular Graphs

Let G be a simple graph. A subset S V is a dominating set of G, if for any vertex v V – S there exists a vertex u S such that uv E(G). The domination number, denoted by (G), is the minimum cardinality of a dominating set. In this paper we prove that if G is a 4-regular graph with order n, then (G) ⁴/₁₁ n     

研究国际证券投资及其有效集的多目标线性规划方法

本文给出国际证券组合投资决策的多目标线性规划模型，以及求解有效国际证券组合的偏好系数加权法．在此基础上，应用线性多数规划技术研究有效国际证券组合集的几何特征，并给出相应结论和简单算例．     

图的强符号圈控制数

本文研究了图的强符号圈控制数γ′_(ssc)(G).利用最大独立集最大匹配等方法,刻画了满足γ′_(ssc)(G)=|E|-2的所有连通图,给出了γ′_(ssc)(G)的一个下界,求出了两类特殊图的强符号圈控制数.     

Domination number in graphs with minimum degree two

A set D of vertices of a graph G = （V, E） is called a dominating set if every vertex of V not in D is adjacent to a vertex of D. In 1996, Reed proved that every graph of order n with minimum degree at least 3 has a dominating set of cardinality at most 3n/8. In this paper we generalize Reed＇s result. We show that every graph G of order n with minimum degree at least 2 has a dominating set of cardinality at most （3n ＋IV21）/8, where V2 denotes the set of vertices of degree 2 in G. As an application of the above result, we show that for k ≥ 1, the k-restricted domination number rk （G, γ） ≤ （3n＋5k）/8 for all graphs of order n with minimum degree at least 3.     

ON THE PROJECTION OF THE EFFICIENT SET AND POTENTIAL APPLICATIONS

Abstract

We study the efficient set X _E for a multiple objective linear program by using its projection into the linear space L spanned by the independent criteria. We show that in the orthogonally complementary space of L, the efficient points form a polyhedron, while in L an efficiency-equivalent polyhedron for the projection P(X _E ) of X _E can be constructed by algorithms of outer and inner approximation types. These algorithms can be also used for generating all extreme points of P(X _E ). Application to optimization over the efficient set for a multiple objective linear program is considered.     

几类Mycielske图的Smarandchely邻点可区别染色

本文根据路和圈、星的Mycielski图的结构性质.利用穷染递推,反证的方法,研究了图M(Pm)和M(Cm),以及M(Sm)的Smarandchely-邻点可区别边染色,得到了相应的边色数,分别给出它们的一种染色方案,推广了文献[9]的结果.     

树T中γL=γt的若干充分条件

全九γt和小控制数γL是图的两个重要的控制参数。本文探讨并给出了在树中γL与γt相等的一些充分条件。同时，利用中介点组理顺了树中不同点集之间的关系，为证明关于γL与γt比值的上界不超过3／2的猜想提供了一个重要思路。