图的多数控制数的下界

设G=(V,E)是简单图,V表示G的顶点集,E表示G的边集.对任何实值函数f∶V→R和V的子集S,令f(S)=∑u∈Sf(u).设f∶V→{-1,1}是G上的一个函数.如果对于V的至少一半的顶点v,f(N[v])≥1,则称f是G上的多数控制函数.图G的多数控制数是γmaj(G)=min{f(V)|f是G上的一个多数控制函数}.得到了这个参数的下界,推广了Henning的一些结果.     

图的符号全控制数的下界

设G=(V,E)是一个没有孤立点的简单图.对任意一个实值函数f:V→R,f的权重定义为f(V)=∑f(v).图的一个符号全控制函数f:V→{-1,1}满足对任意的顶点v∈V,有f(N(v))≥1.图的符号全控制数记作γts(G),是G的符号全控制数的最小权重.文中得到了图G的全符号控制数的一些下界,其中一个下界是已知结论的一大改进.     

关于图的逆符号边全控制

设G=(V,E),是一个图,对于图G的一个函数f:E→{-1,1},如果对任意e∈E(G),均有∑e'∈N(e)f(e')≤1,则称f为图g的一个逆符号边全控制函数.图G的逆符号边全控制数γ'st(G)=max{∑e∈Ef(e)|f是图的逆符号边全控制函数}.给出了图的逆符号边全控制数的两个上界.     

矩阵论中的图论匹配法

G.Birkhoff用代数的方法证明了如果一个矩阵是双随机矩阵,则它能表示成置换矩阵的凸线性组合.设G是具有两分类(X,Y)的二部图,则G中含有饱和X中的所有顶点的匹配M的充分必要条件为:对(A)S(∈)X,有dG(S)≥|S|.文章借助上述二部图的匹配思想,给出这一结论的图论证明.     

关于图的两类强符号控制数的下界

设图G=(V,E)为无孤立点的简单图,且f:V→{-1,1}为G上的一个函数,如果对于任意的顶点v∈V,均有f[v]≥2,则称f是图G的一个强符号控制函数。图G的强符号控制数定义为γss(G)=min{w(f)|f是图G的强符号控制函数}。设k是1≤k≤|V|的正整数,f:V→{-1,1}为图G上的一个函数,如果在图G中至少有k个顶点,使得f[v]≥2,则称f是图G的一个强k-符号控制函数。图G的强k-符号控制数定义为γkss=min{w(f)|f是图强G的k-符号控制函数}。分别得出了强符号控制数及强k-符号控制数的几种形式的下界。     

k色图的连通性

研究和讨论了图的顶点着色问题中k色图的连通性,利用归纳与迭代的方法证明了对于任何k色连通图G,存在顶点V(G)的一个着色X1,X2,…,Xk,使得对该着色类中任意顶点集Xi所诱导出的Gk的子图Gk(Xi)都是连通的.从而证明了Chen,Schelp和Shreve关于k色图的连通性的一个推测.最后将所得的结论作了进一步推广.     

关于某些新的非协调图

Graham和Slone引入了协调图的概念。一个具有q条边的图G是协调图 ,如果有一个从G的顶点集到模 q的整数群的一个单射 ,使得当每一条边xy被分配标号f(x) +f(y) (modq)时 ,所产生的边标号是不同的。利用数论的方法证明了一些新的非协调图     

一类路图的哈密尔顿圈

设G是一个图,我们用Π_k(G)表示G中所有具有k个顶点的路P_k所成之集。图G的路图P_k(G)有顶点集Π_k(G),且P_k(G)中的两个顶点相邻表示两条路P_k的并形成G中的一条路P_(k+1)或一个圈C_k。H.J.Broersma和C.Hoeda研究了路图的一些性质,并提出了两个猜想:1)若T是一颗树,△(T)≥4,则P_3(T)不是哈密尔顿图;2)若G是唯一圈图,△(G)≥5,则G不是哈密尔顿图。在本文中,我们证明了这两个猜想是对的。     

关于某些新的非协调图

Graham和Slone引入了协调图的概念。一个具有q条边的图G是协调图,如果有一个从G的顶点集到模q的整数群的一个单射,使得当每一条边xy被分配标号f(x) f(y)(mod q)时,所产生的边际标号是不同的。利用数论的方法证明了一些新的非协调图。     

对边幻图猜测的一个证明

令简单图G =(V ,E)是有 p个顶点 q条边的图。假设G的顶点和边由 1 ,2 ,3 ,… ,p + q所标号 ,且 f :V∪E { 1 ,2 ,… ,p + q}是一个双射。如果对所有的边xy ,f(x) + f(y) + f(xy)是常量 ,则称图G是边幻图 (edge-magic)。毛毛虫图是一个树 ,移走它的所有端点产生一个路 (称为T的脊或主干 )。例如 ,路和星图是毛毛虫图。证明了毛毛虫图是边幻图 ,从而证明了顶点不超过 8的树是边幻图。     

全制约数的上界

设Ｇ＝（Ｖ，Ｅ）是无孤立点的简单图．设Ｔ是Ｖ的子集，如对任意Ｕ∈Ｖ，存在ｕ∈Ｔ使得ｕｖ∈Ｅ，则称Ｔ为Ｇ的全制约集．全制约集的最小基数称为Ｇ的全制约数，记作γｔ（Ｇ）．本文证明了如Ｇ是阶数ｎ≥３，最小度至少为２的连通图，则γｔ（Ｇ）≤４「（ｎ＋ｌ）／７」     

Signed Total Domination in Graphs

Let G = (V, E) be a simple graph. For any real valued function f: V→R, the weight of f is f(V) = ∑(v) over all vertices v ∈V. A signed total dominating function is a function f: V→|- 1, 1|such that f( N ( v ) ) ≥1 for every vertex v ∈ V. The signed total domination number of a graph G equals the minimum weight of a signed total dominating function on G. In this paper, some properties of the signed total domination number of a graph G are discussed.     

Bondage and Reinforcement Number of γf for Complete Multipartite Graph

The bondage number of γf, bf(G) , is defined to be the minimum cardinality of a set of edges whose removal from G results in a graph G′ satisfying γf(G′)＞γf(G). The reinforcement number of γf, rf(G), is defined to be the minimum cardinality of a set of edges which when added to G results in a graph G′ satisfying γf(G′)＜γf(G). G.S.Domke and R.C.Laskar initiated the study of them and gave exact values of bf(G) and rf(G) for some classes of graphs. Exact values of bf(G) and rf(G) for complete multipartite graphs are given and some results are extended.     

On Minus Paired－Domination in Graphs

The study of minus paired-domination of a graph G = ( V, E) is initiated. Let S lontain in V be any paired-dominating set of G, a minus paired-dominating function is a function of the form f: V→ { - 1, 0, ｝such that f(υ) = 1 for υ∈S, f(υ)≤0 for υ∈V- S, and f(N[υ])≥l for all υ∈V. The weight of a minus paired-dominating function f is ω(f)=∑f(υ), over all vertices υ∈V. The minus paired-domination number of a graph G is γp^-(G)= min｛ω (f)| f is a minus paired-dominating function of G｝. On the basis of the minus paired-domination number of a graph G defined, some of its properties are discussed.     

关于可行图的几个新结论

设有n个集合X1,X2 ,… ,Xn,一个以X =∪ni=1Xi 为顶点集的图G称为是一个关于集合序列 (X1,X2 ,… ,Xn)的可行图 ,如果对每一个Xi(i=1 ,2 ,… ,n) ,导出子图Gi=G[Xi]是连通的。集合序列 (X1,X2 ,… ,Xn)含最少边数的可行图称为关于 (X1,X2 ,… ,Xn)的最小可行图。将n =3推广至任意的自然数n ,得出了集合序列 (X1,X2 ,… ,Xn)的最小可行图G =∪ni=1Gi,当满足∩ni=1Xi≠Φ时 ,G是关于集合序列 (X1,X2 ,… ,Xn)的最小可行图的一个充分必要条件 ,同时得出了集合序列 (X1,X2 ,… ,Xn)的最小可行图在某种条件下的两个主要结果。     

最小可行图问题的一个必要条件及总结

设有n个集合X1,X2 ,… ,Xn,一个以X =∪ni =1 Xi 为顶点集的图G称为一个关于集合序列 (X1,X2 ,… ,Xn)的可行图 ,如果对每一个Xi(i=1,2 ,… ,n) ,导出子图Gi=G[Xi]是连通的。那么集合序列 (X1,X2 ,… ,Xn)的含最少边数的可行图称为关于 (X1,X2 ,… ,Xn)的最小可行图。曾得出了n =3时集合序列 (X1,X2 ,X3 )的最小可行图的一个充分必要条件。下面得出了n =4时集合序列 (X1,X2 ,X3 ,X4 )的最小可行图的一个必要条件 ,并用一个例子说明了n =3时的判定最小可行图的充分必要条件 ,不能推广至n≥ 4的情况 ,对最小可行图问题做了总结     

整数距离图G(Dm,3)的点线性荫度

整数距离图G(D)以全体整数为顶点集，顶点u,v相邻当且仅当|u-v|∈D，其中D是一个正整数集.对于m＞3，设Dm,3={1,2,…,m}＼{3}，本文得到了G(Dm,3)的点线性荫度的上界和下界并决定出了它在某些较小的m上的确切值.     

Bounds on Fractional Domination of Some Products of Graphs

Let γ f(G) and γ~t f(G) be the fractional domination number and fractional total domination number of a graph G respectively. Hare and Stewart gave some exact fractional domination number of P n×P m (grid graph) with small n and m . But for large n and m , it is difficult to decide the exact fractional domination number. Motivated by this, nearly sharp upper and lower bounds are given to the fractional domination number of grid graphs. Furthermore, upper and lower bounds on the fractional total domination number of strong direct product of graphs are given.