3—连通正则无爪图的Hamilton圈

本文证明了：任一阶数不超过６ｋ－４的３－连通ｋ－正则无爪图是Ｈａｍｉｔｏｎ的。     

3-边可染的3-正则图（英文）

若一个连通图的每条边都包含在某一完美匹配中,则称之为匹配覆盖图.设G是一个3-连通图,若去掉G的任意两个顶点后得到的子图仍有完美匹配,则称G是一个brick.而brick的重要性在于它是匹配覆盖图的组成结构因子.3-边可染3-正则5的刻画问题是一个NP-完全问题.本文将此问题规约到3-正则匹配覆盖图上,进而规约到其组成结构因子brick上.我们证明了:一个3-正则图是3-边可染的当且仅当它的所有brick是3-边可染的.     

二倍无平方因子阶的3度1-正则图

一个图叫做1-正则的, 如果它的自同构群在它的弧集上作用正则. 设n是一个无平方因子的正整数. 证明了存在2n阶3度1-正则图当且仅当n=3^tp₁p₂… p_s≥13, 其中t≤1, s≥1, p_i (1≤ i≤s)为互不相同的素数且满足3|(p_i-1). 进一步, 对每个满足上述条件的整数n, 共有2^s−1个互不同构的2n阶3度1-正则图, 并且这些图均为2n阶二面体群上的Cayley图. 由此可知, 不存在4m阶3度1-正则图, 其中m为无平方因子的奇数.     

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

设G是连通图,γ_C(G)和ir(G)分别表示G的连通控制数和无赘数。孙良于1990年证明了γ_c(G)≤4ir(G)—2,同时提出猜想γ_c(G)≤3ir(G)—2。本文进一步研究γ_c(G)与ir(G)的关系,并证得上述猜想成立。     

3－连通正则无爪图的Hamilton圈

本文证明了：任一阶数不超过６ｋ—４的３－连通ｋ－正则无爪图是Ｈａｍｉｌｔｏｎ的．     

3-连通3-正则图生成树外的可去边

G是3-连通图，e是G中的一条边．若G-e是3-连通图的一个剖分，则称e是3-连通图的可去边．否则，e是G中不可去边．本给出3-连通3-正则图中生成树外可去边的分布情况及数目．     

一类3-正则图的邻强边染色

对简单图G(V,E),f是从V(G)∪E(G)到{1,2,…,k}的映射,k是自然数,若f满足(1)uv,uw∈E(G),u≠w,f(uv)≠f(uw);(2)uv∈E(G),C(u)≠C(v).则称f是G的一个邻强边染色,最小的k称为邻强边色数,其中C(u)={f(uv)|uv∈E(G)}.给出了一类3-正则重圈图的邻强边色数.     

度为奇数的正则图的上负全控制数

f:v(G)→{一1,0,1}称为图G的负全控制函数,如果对任意点V∈V,均有f[v]≥1,其中 f[v]= ∑,f(u).如果对每个点v∈V,不存在负全控制函数g:V(G)→{-l,0,1),g≠f,满u∈N(v)足g(v)≤f(v),则称f是-个极小负全控制函数.图的上负全控制数F-t(G)=max{w(f)|f,是G的极小负全控制函数},其中w(f)=∑/v∈V(G)f(v).本文研究正则图的上负全控制数,证明了:令G是-个v∈V(G)n阶r-正则图.若r为奇数,则Γt-(G)＜＝r2 1/r2 2r-1n.     

数有根近2-正则平面地图

The number of rooted nearly 2-regular maps with the valency of root-vertex, the number of non-rooted vertices and the valency of root-face as three parameters is obtained. Furthermore, the explicit expressions of the special cases including loopless nearly 2-regular maps and simple nearly 2-regular maps in terms of the above three parameters are derived.     

关于3-正则图的路分解

本文讨论了3-正则图的路分解问题,证明了任意的3-正则图都有{P3,P4}分 解,其中Rk指包含k个顶点的路.     

立方图的对控制数

设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.     

Total Restrained Domination in Cubic Graphs

A set S of vertices in a graph G = (V, E) is a total restrained dominating set (TRDS) of G if every vertex of G is adjacent to a vertex in S and every vertex of V − S is adjacent to a vertex in V − S. The total restrained domination number of G, denoted by γ _tr (G), is the minimum cardinality of a TRDS of G. Let G be a cubic graph of order n. In this paper we establish an upper bound on γ _tr (G). If adding the restriction that G is claw-free, then we show that γ _tr (G) = γ _t (G) where γ _t (G) is the total domination number of G, and thus some results on total domination in claw-free cubic graphs are valid for total restrained domination. Research was partially supported by the NNSF of China (Nos. 60773078, 10832006), the ShuGuang Plan of Shanghai Education Development Foundation (No. 06SG42) and Shanghai Leading Academic Discipline Project (No. S30104).     

关于Menger图和Menger数的若干结果

该文研究Menger图和Menger数. 主要结果如下 : (1)\ 对任意的n≥4, n立方体Q\-n不是Menger图. 解决了Sampathkumar提出的未解问题2. (2)\ 如果G是一个偶图, 则m(G)=β\-0(G),其中m(G)是G的Menger数, β\-0(G)是G的独立数. 部分解决了Sampathkumar提出的未解问题3. (3)\ “确定图的Menger数”问题是NP困难的.     

Independent Domination in Cubic Graphs

A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S. The independent domination number of G, denoted by , is the minimum cardinality of an independent dominating set. In this article, we show that if is a connected cubic graph of order n that does not have a subgraph isomorphic to K_{2, 3}, then . As a consequence of our main result, we deduce Reed's important result [Combin Probab Comput 5 (1996), 277–295] that if G is a cubic graph of order n, then , where denotes the domination number of G.     

Independence and hamiltonicity in 3-domination-critical graphs

Let δ, γ, i and α be respectively the minimum degree, the domination number, the independent domination number and the independence number of a graph G. The graph G is 3-γ-critical if γ = 3 and the addition of any edge decreases γ by 1. It was conjectured that any connected 3-γ-critical graph satisfies i = γ, and is hamiltonian if δ ≥ 2. We show here that every connected 3-γ-critical graph G with γ ≥ 2 satisfies α ≤ δ + 2; if α = δ + 2 then i = γ; while if α ≤ δ + 1 then G is hamiltonian. © 1997 Wiley & Sons, Inc. J Graph Theory 25: 173–184, 1997     

边临界图的新下界

图$G$ 为简单的第二类连通图, 且对$G$ 的任意边$e$,有$\chi^{\prime}(G-e)<\chi^{\prime}(G)$, 则称 $G$是临界的.该文给出了阶为$n$ 边数为$m$的$\Delta$ -临界图的新下界, 即$m\geq(3\Delta+6)n/10$, 这里$1\leq\Delta\leq18$     

粘合运算对图的控制参数的影响

简单图G的粘合运算G_(uv)指的是重合G的两个顶点{u,v}并且去掉重边和环所得到简单图的运算．本文考虑了粘合运算对图的4个控制参数γ(G),Γ(G),β(G),i(G)的影响．刻画了图G_(uv)与图G的控制参数γ(G),Γ(G),γ(G),i(G)之间的关系．及给出γ(G_(uv))=γ(G)-1和β(G_(uv)=β(G)-1的充要条件．     

划分图上的正影响数

一个社会网络中通常包括具有正面影响和负面影响的两类人员,为了研究这个社会网络中人们之间相互影响的某些规律,引入了一个新的概念. 用划分图G=(V,E),V=V⁺ \cup V^-表示这样的一个社会网络,其中V⁺和V^- 分别表示正面人员的集合和负面人员的集合. 图G的一个点子集D\subseteq V^-被称为G的一个正影响集,若G的每个点的至少一半的邻点在D\cup V⁺中. G的所有正影响集的最小基数称为G的正影响数. 给出G的正影响数的几个下界并证明了这些界是紧的. 此外,还证明了求正影响数问题在二部图和弦图上都是NP-完全的.     

Minimum Power Dominating Sets of Random Cubic Graphs

We present two heuristics for finding a small power dominating set of cubic graphs. We analyze the performance of these heuristics on random cubic graphs using differential equations. In this way, we prove that the proportion of vertices in a minimum power dominating set of a random cubic graph is asymptotically almost surely at most 0.067801. We also provide a corresponding lower bound of using known results on bisection width.     

具有最大控制数的连通图的刻画

设Ｇ为一个Ｐ阶图,γ（Ｇ）表示Ｇ的控制数．显然γ（Ｇ）≤［ｐ／２］．本文的目的是刻画达到这个上界的连通图．主要结果：（１）当ｐ为偶数时,γ（Ｇ）＝ｐ／２当且仅当Ｇ≈C₄或者Ｇ为某连通图的冠;（２）当ｐ为奇数时,γ（Ｇ）＝(p-1)/2当且仅当Ｇ的每棵生成树为定理３．１中所示的两类树之一．