一个关于球面和环面上嵌入图的近-三角剖分嵌入的内插定理(I)

一个近-三角剖分嵌入是指一个曲面上的嵌入图使得几乎所有的面都是三角形,至多只有一个可能的例外.文中作者证明了如下结论:如果一个图G 在球面S₀(或环面S₁)上有近-三角剖分嵌入,那么G在每一个可定向曲面S_k有近-三角剖分嵌入,其中k=h,h+1,\cdots ,\lfloor\frac{\beta(G)}{2}\rfloor$, 而h=0(或1)并且β(G)是图G的Betti数.特别地,G是上可嵌入的.     

关于循环图的曲面嵌入

该文集中探讨循环图的曲面嵌入性质.决定了所有循环图的最小亏格(其中包括可定向亏格与不可定向亏格)和最大亏格.对于固定的整数l(≥3)和充分大的 自然数n,只有一种方式将4 -正则循环图C(n,l)嵌入到环面上使得其每一个面都是4 -边形.特别地,循环图$C(2l+2,l)$在加入若干条新边后可以同时将环面与Klein瓶进行三角剖分.     

嵌入在克莱茵瓶上的图的最大亏格

设$\phi: G\rightarrow S$是图$G$在曲面$S$上的2 -胞腔嵌入. 若$G$的所有面都是依次相邻, 即嵌入图$G$的对偶图有哈密顿圈, 则将$\phi$称为一个面依次相邻的嵌入. 该文研究了在克莱茵瓶上有面依次相邻嵌入的图的最大亏格.     

基本圈与图的曲面嵌入

本文研究图的基本圈与图在可定向曲面上的嵌入之间的关系．本文结果表明：一个图G可以嵌入到亏格至少为g的可定向曲面上的充分必要条件是：对于G中任意一个支撑树T,存在一个基本圈序列C1,C2,…,Q2g,使得对于每一个i：1≤i≤g,C2i-1∩C2i≠0．特别地,在T的β（G）个基本圈中有基本圈序列C1,C2…,Q2γM（G）,使得Qt-1∩C2t≠0对于每一个i：1≤i≤γM（G）成立．这里β（G）和γM（G）分别是G的Betti数和最大可定向亏格．这个结果的意义在于：我们可以从任意一个支撑树（可以具有任意奇连通分支数）出发去构造图在可定向曲面上的嵌入．这在本质上有别于Xuong与Liu在最大亏格方面的工作（即,从具有最小奇连通分支数的支撑树出发构造图嵌入）．事实上,这个结果在本质上同时推广了Xuong-Liu与Fu等在最大亏格方面的工作．作为这一结果的直接应用,本文得到以下结果：（1）提出了用于计算图的最大亏格的新条件,它尤其适用于计算具有特定边割（edge—cut）图的最大亏格．并得到一些新的与已知的著名结果（包括Huang在曲面嵌入图方面的工作）．（2）最大亏格问题可以归结为在基本相交图中求最大对集问题．结合Micali-Vazirani的一个有效算法,我们设计出了一个用于计算图的最大亏格的多项式算法,它的复杂度是O（（β（G））^5/2）,这一算法与Furst等人的算法相比更加直接、便于计算．     

关于两类平面图及相关图的L(d1,d2)-标号问题

图G的L(2,1)标号是一个从顶点集V(G)到非负整数集的函数f(x),使得若d(x,y)=1,则|f(x)-f(y)|≥(2;若d(x,y)=2,则|f(x)-f(y)|≥1.图G的L(2,1)标号数λ(G)是使得G有max{f(v)V∈V(G)}=k的L(2,1)标号中的最小数k.Griggs和Yeh猜想对最大度为△的一般图G,有λ(G)≤△2.本文将L(2,1)-标号推广到L(d1,d2)-标号,并得出了平面三角剖分图、立体四面体剖分图、平面近四边形剖分图的L(d1,d2)-标号的上界,作为推论,本文证明了对上述几类图,有上述猜想成立.     

关于图的L(d,1)-标号问题

图G的L(2,1)-标号是一个从顶点集V(G)到非负整数集的函数f(x),使得若d(x,y)=1,则|f(x)-f(y)|≥2;若d(x,y)=2,则|f(x)-f(y)|≥1.图G的L(2,1)-标号数λ(G)是使得G有max{f(v)v∈V(G)}=k的L(2,1)-标号中的最小数k.Griggs和Yeh猜想对最大度为△的一般图G,有λ(G)≤△2.此文研究了作为L(2,1)-标号问题的推广的L(d,1)-标号问题,并得出了平面三角剖分图、立体四面体剖分图、平面近四边形剖分图的L(d,1)-标号的上界,作为推论证明了对上述几类图该猜想成立.     

可定向曲面上具有较短不可收缩圈图嵌入的唯一性

拓扑图论中的一个基本问题就是要决定图在一个(可定向)曲面上的嵌入之数目(既嵌入的柔性问题).H.Whitney的经典结果表明:一个3-连通图至多有一个平面嵌入;C.Thomassen的LEW-嵌入(大边宽度)理论将这一结果推广到一般的可定向曲面.本文给出了几个关于一般可定向曲面上嵌入图的唯一性定理.结果表明:一些具有大的面迹的可定向嵌入仍然具有唯一性.这在本质上推广了C.Thomassen在LEW-嵌入方面的工作.     

图的上可嵌入性

证明了一个连通无环图G如果能嵌入某个 (定向或不可定向 )曲面S上使得每个面的大小不超过 5 ,则G是上可嵌入的 .     

与直径和围长有关的最大亏格的下界

本文证明了如下结果:设G为直径为d的简单图,若G的围长不小于d,则当d为不小于4的偶数时,有ξ(G)≤1,即G是上可嵌入的;当d为不小于3的奇数时,有ξ(G)≤2,即γM(G)≥1/2β(G)-1.     

关于图的上可嵌入性的一个注记

任韩和李刚在图的最大亏格综述一文"Survey of maximum genus of graphs" [J East China NormUniv Natur Sci, Sep. 2010, No. 5, 1-13] 中,全面地阐述了近30 年来关于图的最大亏格及其相关问题所取得的进展,并提出了如下两个猜想:
猜想1 设G 为简单连通图, 且G 的每条边含在一个三角形K₃ 中, 则G 是上可嵌入的.
猜想2 设c 为任意的正数, 则存在一个自然数N(c), 使得对每一个图G, 若G 的点数n ≥ N(c), 且最小度δ(G) ≥ cn, 则G 是上可嵌入的.
本文的主要工作是否定上述两个猜想, 同时探讨上述猜想成立的条件且得了一些新结果, 并提出有关进一步研究的问题.     

增益图与其底图的正惯性指数之间的关系

设$\mathbb{T}$是模为1的复数乘法子群.图$G=(V,E)$,这里$V,E$分别表示图的点和边.增益图是将底图中的每条边赋于$\mathbb{T}$中的某个数值$\varphi(v_iv_j)$,且满足$\varphi(v_iv_j) =\overline{\varphi(v_jv_i)}$.将赋值以后的增益图表示为$(G,\varphi)$.设$i_+(G,\varphi)$和$i_+(G)$分别表示增益图与底图的正惯性指数,本文证明了如下结论: $$ - c( G ) \le {i_ + } ( {G,\varphi } ) - {i_ + }( G ) \le c( G ), $$ 这里$c(G)$表示圈空间维数,并且刻画了等号成立时候的所有极图.     

任意长圈覆盖指定的独立的点

An invariant σ2（G） of a graph is defined as follows： σ2（G） ：= min{d（u） ＋ d（v）｜u, v ∈V（G）,uv ∈ E（G）,u ≠ v} is the minimum degree sum of nonadjacent vertices （when G is a complete graph, we define σ2（G） = ∞）. Let k, s be integers with k ≥ 2 and s ≥ 4, G be a graph of order n sufficiently large compared with s and k. We show that if σ2（G） ≥ n ＋ k- 1, then for any set of k independent vertices v1,..., vk, G has k vertex-disjoint cycles C1,..., Ck such that ｜Ci｜ ≤ s and vi ∈ V（Ci） for all 1 ≤ i ≤ k.
The condition of degree sum σs（G） ≥ n ＋ k - 1 is sharp.     

树的导出匹配覆盖

The induced matching cover number of a graph G without isolated vertices,denoted by imc(G),is the minimum integer k such that G has k induced matchings M1,M2,…,Mk such that,M1∪M2 ∪…∪Mk covers V(G).This paper shows if G is a nontrivial tree,then imc(G) ∈ {△*0(G),△*0(G) + 1,△*0(G)+2},where △*0(G) = max{d0(u) + d0(v) :u,v ∈ V(G),uv ∈ E(G)}.     

一个六点七边图的填充与覆盖

$\lambda{K_v}$为$\lambda$重$v$点完全图, $G$ 为有限简单图. $\lambda {K_v}$ 的一个 $G$-设计 ( $G$-填充设计, $G$-覆盖设计), 记为 ($v,G,\lambda$)-$GD$(($v,G,\lambda$)-$PD$, ($v,G,\lambda$)-$CD$), 是指一个序偶($X,\calB$)，其中 $X$ 为 ${K_v}$ 的顶点集， $\cal B$ 为 ${K_v}$ 中同构于 $G$的子图的集合, 称为区组集,使得 ${K_v     

$P_m\times K_n$的邻点可区别全色数

设 $G$ 是简单图. 设$f$是一个从$V(G)\cup E(G)$ 到$\{1, 2,\cdots, k\}$的映射. 对每个$v\in V(G)$, 令 $C_f (v)=\{f(v)\}\cup \{f(vw)|w\in V(G), vw\in E(G)\}$. 如果 $f$是$k$-正常全染色, 且对任意$u, v\in V(G), uv\in E(G)$, 有$C_f(u)\ne C_f(v)$, 那么称 $f$ 为图$G$的邻点可区别全染色(简称为$k$-AVDTC).数 $\chi_{at}(G)=\min\{k|G$ 有$k$-AVDTC\}称为图$G$的邻点可区别全色数.本文给出路$P_m$和完全图$K_n$ 的Cartesion积的邻点可区别全色数.     

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

简单图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的充要条件．     

NASH EQUILIBRIUM OF TWO GAME MODELS ON THE RANDOM SOCIAL NETWORK

A graph $G$ is $k$-triangular if each of its edge is contained in at least $k$ triangles. It is conjectured that every 4-edge-connected triangular graph admits a nowhere-zero 3-flow. A triangle-path in a graph $G$ is a sequence of distinct triangles $T_1 T_2\cdots T_k$ in $G$ such that for $1\leq i\leq k-1, |E(T_i )\cap E(T_{i+1})|=1$ and $E(T_i)\cap E(T_j)=\emptyset$ if $j>i+1$. Two edges $e,e''\in E(G)$ are triangularly connected if there is a triangle-path $T_1,T_2,\cdots, T_k$ in $G$ such that $e\in E(T_1)$ and $e''\in E(T_k)$. Two edges $e,e''\in E(G)$ are equivalent if they are the same, parallel or triangularly connected. It is easy to see that this is an equivalent relation. Each equivalent class is called a triangularly connected component. In this paper, we prove that every 4-edge-connected triangular graph $G$ is ${\mathbb Z}_3$-connected, unless it has a triangularly connected component which is not ${\mathbb Z}_3$-connected but admits a nowhere-zero 3-flow.     

完全图的Cantesian积的L(2,1)-圆标定

For positive integers j and k with j ≥ k, an L（j, k）-labeling of a graph G is an assignment of nonnegative integers to V（G） such that the difference between labels of adjacent vertices is at least j, and the difference between labels of vertices that are distance two apart is at least k. The span of an L（j, k）-labeling of a graph G is the difference between the maximum and minimum integers it uses. The λj, k-number of G is the minimum span taken over all L（j, k）-labelings of G. An m-（j, k）-circular labeling of a graph G is a function f ： V（G） →{0, 1, 2,..., m - 1} such that ｜f（u） - f（v）｜m ≥ j if u and v are adjacent; and ｜f（u） - f（v）｜m 〉 k ifu and v are at distance two, where ｜x｜m = min{｜xl｜, m-｜x｜}. The minimum integer m such that there exists an m-（j, k）-circular labeling of G is called the σj,k-number of G and is denoted by σj,k（G）. This paper determines the σ2,1-number of the Cartesian product of any three complete graphs.