图的孤立断裂度

连通图G的孤立断裂度isc(G)=max{i(G-S)-|S|:S∈C(G)},其中i(G-S)是G-S中的孤立点数,C(G)是G的点割集.本文研究了孤立断裂度和图的其它一些参数的关系.讨论了孤立断裂度取特殊值的一些图,证明了圈、连通二部图、连通二部图的联图以及树和圈的补图的孤立断裂度都达到最小.给出了具有给定阶数和最大度的村的最大、最小孤立断裂度.     

The Rainbow Vertex-disconnection in Graphs

Let G be a nontrivial connected and vertex-colored graph. A subset X of the vertex set of G is called rainbow if any two vertices in X have distinct colors. The graph G is called rainbow vertex-disconnected if for any two vertices x and y of G, there exists a vertex subset S of G such that when x and y are nonadjacent, S is rainbow and x and y belong to different components of G-S; whereas when x and y are adjacent, S + x or S + y is rainbow and x and y belong to different components of(G-xy)-S. For a connected graph G, the rainbow vertex-disconnection number of G, denoted by rvd(G), is the minimum number of colors that are needed to make G rainbow vertexdisconnected. In this paper, we characterize all graphs of order n with rainbow vertex-disconnection number k for k ∈ {1, 2, n}, and determine the rainbow vertex-disconnection numbers of some special graphs. Moreover, we study the extremal problems on the number of edges of a connected graph G with order n and rvd(G) = k for given integers k and n with 1 ≤ k ≤ n.     

图的下测地数和上测地数

对于图G(或有向图D)内的任意两点u和v,u—v测地线是指在u和v之间(或从u到v)的最短路．I(u,v)表示位于u—v测地线上所有点的集合,对于S(?)V(G)(或V(D)),I(S)表示所有I(u,v)的并,这里u,v∈S．G(或D)的测地数g(G)(或g(D))是使I(S)=V(G)(或I(S)=V(D))的点集S的最小基数．G的下测地数g~-(G)=min{g(D)：D是G的定向图},G的上测地数g~ (G)=max{g(D)：D是G的定向图}．对于u∈V(G)和v∈V(H),G_u H_v表示在u和v之间加一条边所得的图．本文主要研究图G_u H_v的测地数和上(下)测地数．     

图的笛卡儿积的测地数

对于图G内的任意两点u和v，u-v测地线是指u和v之间的最短路．I（u，v）表示位于u-v测地线上所有点的集合，对于．S∈V（G），I（S）表示所有I（u，v）的并，这里“u,v∈．S．G的测地数g（G）是使I（S）=V（G）的点集．S的最小基数．在这篇文章，我们研究G×K3的测地数和g（G）与g（G×K3）相等的充分必要条件，还给出了T×Km和Cn×Km的测地数，这里T是树．     

立方图的对控制数

设G=(V,E)是一个简单图, 对任意的顶点子集合 $S\subseteq V$, G[S]表示图G中由S所导出的子图. 如果S是G的一个控制集并且G[S]包含至少一个完备匹配, 则称S是G的一个对控制集. G中对控制集的最少的顶点数称为$G$的对控制数, 记为γ_p(G). 该文证明了对任意有n点的连通立方图G, γ_p(G)≤3n/ 5.     

图的双控制的一些新结果

图G=(V,E)的每个顶点控制它的闭邻域的每个顶点.S是一个顶点子集合,如果G的每一个顶点至少被S中的两个顶点控制,则称S是G的一个双控制集.把双控制集的最小基数称为双控制数,记为dd(G).本文探讨了双控制数和其它控制参数的一些新关系,推广了[1]的一些结果.并且给出了双控制数的Nordhaus-Gaddum类型的结果.     

给定匹配数和独立数时图零度的上界

设G是一个有n个点的简单图,分别记η(G),m(G)和α(G)为图G的零度、匹配数和独立数.设θ(G)是一个非负整数,定义为使图G成为二部图至少需要从G的边集中删去的边数.本文运用二部划分运算,证明了对于有n个点并且不含有圈长为2的倍数的圈为子图的简单图G,有η(G)≤n-2m(G)+20(G)和η(G)≤2α(G)+2θ(G)-n.     

CIRCULAR CHROMATIC NUMBER AND MYCIELSKI GRAPHS

For a general graph G, M(G) denotes its Mycielski graph. This article gives a number of new sufficient conditions for G to have the circular chromatic number Xc(M(G)) equals to the chromatic number X(M(G)), which have improved some best sufficient conditions published up to date.     

Bi-Cayley图的一些代数性质

设G是一个有限群,S是G的一个子集,Bi-Cayley图BC(G,S)是一个二部图:其顶点集为G×{0,1},而边集为{{(g,0),(sg,1)}:g∈G,s∈S}.本文研究了有限阿贝尔群G上的Cayley图D(G,S)和Bi-Calyley图BC(G,S)之间特征值的关系,并由此得到循环群上的Bi-Cayley图的特征值.继而得到生成树数的一些渐进性定理.     

有关循环图C(n;{1,k})的独立数的一些结果

令G=(V(G),E(G))是一个简单有限无向图.如果V(G)的子集S中任意两个顶点均不相邻,则S是图G的一个独立集.顶点独立集大小的最大值,称为图G的独立数,记作α(G).本文研究了循环图C(n;{1,k})的独立数问题,并给出了当k=2,3,4,5时的准确值.     

图和有向图的测地数

对于图G（或者有向图D）内的任意两点u和υ,u-υ测地线是指在u和υ之间的最短路（或者从u到υ）.I（u,υ）表示位于一条u-υ测地线上所有点的集合,对于S（U∣）V（G）,I（S）表示所有I（u,υ）的并,这里u,υ∈S.图G（或者有向图D）的测地数g（G）（g（D））是使J（S）=V（G）（J（S）=V（D））的最小点集S的基数.定义G的所有定向图中测地数的最小值为G的下测地数,即g-（G）=min{g（D）：D是G的定向图）;定义G的所有定向图中测地数的最大值为G的上测地数,即g＋（G）=max{g（D）：D是G的定向图）.本文的主要目的是研究G V H 的上、下测地数,此外,文章给出了g（G）=g（G×P3）的一个充分必要条件.     

EDGE-FACE CHROMATIC NUMBER OF 2-CONNECTED PLANE GRAPHS WITH HIGH MAXIMUM DEGREE

The edge-face chromatic number Xef (G) of a plane graph G is the least number of colors assigned to the edges and faces such that every adjacent or incident pair of them receives different colors. In this article, the authors prove that every 2-connected plane graph G with△(G)≥|G| -2△9 has Xef(G)=△(G).     

极大全控点临界图

图G的点集S如果满足:VG-S(或VG)中每个点相邻于S中的某个点(或而不是它本身),则称点集S是一个控制集(或全控制集).图G的所有控制集(或全控制集)中最小基数的控制集(或全控制集)中的点数,称为控制数(或全控数),记为γ(G)(或γt(G)).在这篇文章中我们特征化γt-临界图且满足γt(G)=n-Δ(G)的图特征,这回答了Goddard等人提出的一个问题.     

图的连通控制数与无赘数的一个不等式

设G是连通图,γ_C(G)和ir(G)分别表示G的连通控制数和无赘数。孙良于1990年证明了γ_c(G)≤4ir(G)—2,同时提出猜想γ_c(G)≤3ir(G)—2。本文进一步研究γ_c(G)与ir(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是可分解的;其次,给出了这个新推广定理的一些应用.     

系列平行图的边面染色

一个平面图G的边面色数xef(G)是指对G的边和面进行染色所用最少的颜色数目,并同时使得相邻或相关联的两个元素间染不同颜色.若G是一个系列平行图,也就是不含K_4的剖分作为子图的平面图,则有Xef(G)≤max{7,△(G) 1};同时如果G还是2-连通的且△(G)>6,则有Xef(G)=△.     

无$K_{1,4}$子图的图的路覆盖

For a graph G, a path cover is a set of vertex disjoint paths covering all the vertices of G, and a path cover number of G, denoted by p(G), is the minimum number of paths in a path cover among all the path covers of G. In this paper, we prove that if G is a K_(1,4)-free graph of order n and σ_(k+1)(G) ≥ n-k, then p(G) ≤ k, where σ_(k+1)(G) = min{∑v∈S d(v) : S is an independent set of G with |S| = k + 1}.     

图与其Mycielski图关联色数的关系

本文证明了对n阶图G,若其最大度△(G)的2倍不等于n,且G的关联色数等于△(G) 1,则M(G)的关联色数为△(M(G)) 1．同时还研究了树和完全二部图的Mycielski图的关联色数．文末提出了M(G)的关联色数猜想,其中M(G)为图G的Mycielski图．     

γ-稳定图

本文我们引进γ- 稳定图,γ 稳定图和γ稳定图的概念,图G是γ- 稳定图(γ 稳定图),若任意删去G(增加G)的一条边都不改变G的控制数γ(G).一个γ稳定图指既是γ- 稳定图又是γ 稳定图的图.我们给出一些γ-(γ ,γ) 稳定图的性质和实例.     

无向图可迹的一个充分条件

无向图G是简单连通图,且最小度为δ.如果G中包含一条生成路,则G是可迹的.无向图G的叶子数L(G)是G中生成树所含的叶子数的最大数.基于L(G)和δ,证明了一个充分条件使得无向图G是可迹的,即设G为连通图,最小度为δ≤4.若δ≥(1/2)(L(G)+2),G是可迹的.