图的不可定向最大亏格

本文证明了:对于任何一个有圈连通图G,其不可定向最大亏格为这里,α₀,α₁分别为G的顶点和边的数目.从而,也解决了图的不可定向嵌入的存在性问题.     

关于3-点临界图的一个猜想的证明

设γ(G) 是图G的点控制数. 如果对任意的v ∈ V (G), 都有γ(G?v) < γ(G) 成立, 那么称G为γ-点临界图. 本文主要给出Ananchuen 和Plummer 提出的一个猜想的证明, 得到了如下的结果:若G是无K_1,7的3-点临界图, 且阶数为不小于18的偶数, 则除几类特殊图外, G 均有完美匹配.     

l-群的极小素子群

本文研究l-群的极小素子群,主要证明如下结果:设G是一个l-群.（1）N∈Γ_m（G）,则N=a^⊥当且仅当{P_N^C}是一个归纳集;（2）g∈G⁺,如果g是特殊的,且g的唯一值是原子,则g^⊥∈Γ_m（G）;（3）G∈B_w,Γ₁（C）是原子的当且仅当Γ_m(G）?Γ₁（G）。     

具有正交的(g,f)-因子分解的子图

仅考虑简单图.设G是一个图,g(x)和f(x)是定义在V(G)上的整数值函数,且对任意的x∈V(G),设g(x)≤f(x),H是G的一个子图,F={F₁,F₂,…,F_t}是G的一个因子分解,如果对所有的1≤i≤t, |E(G)∩E(F_i)|=1,则称F与H正交.证明了:设G是一个(mg(x)+k,mf(x)-k)-图,其中对任意的x∈V(G),g(x)≥1或f(x)≥5是定义在V(G)上的整数值函数,1≤k<m,则存在一个子图R满足对G的任意子图H，|E(H)|=k,R有(g,f)-因子分解与H正交.     

高度平面图的邻点可区别全染色

图G 的邻点可区别全染色是G 的一个正常全染色, 使得每一对相邻顶点有不同的颜色集合. G的邻点可区别全色数χ_a′′ (G) 是使得G 有一个k- 邻点可区别全染色的最小颜色数k. 本文证明了: 若G 是满足最大度Δ(G) ≥ 11 的平面图, 则χ_a′′ (G) ≤ Δ(G) + 3.     

算术图一个猜想的证明

Ａｃｈａｒｙａ和Ｈｅｄｇｅ提出猜想：(i)若圈Ｃ_4t＋１( t≥1, t∈N) 是(k, d )－算术图，则Ｋ＝２ｄｔ+ 2r ( r≥0, r∈N ) ; ( ii) 若圈C_4t＋3是(k, d )-算术图, 则k= (2t+ 1) d + 2r ( r≥0, r∈N ). 本文证明了上述猜想为真.     

关于有限Abelian群的生成子集的基数

假若G =Z_m1 Z_m2… Z_mr 为 (m₁, m₂,…, m_r)型Abelian群, 其中Z_mi 为 m_i 阶的循环群且1≤i≤ r, m₁ |m₂|…| m_r, S 为G 的满足0∈ S=-S 的生成子集. 如果 |S|>|G|/ρ, 其中ρ≥l m_r /2l且m_r=e(G) 为群 G 的所有元素的阶的最小公倍数, 则ρS=G. 更进一步作者推广了Klopsch与lev ^[1]的一个结论,有:若 G=Z₂Z_m 为 (2, m) 型 Abelian 群(m ≥8), 则 t_m/2(G)=0.     

有限秩的幂零π-群的自同构

设G 是有限秩的幂零π-群, α 和β 是G 的两个自同构. 设1=ς₀G < ς₁G < …< ς_cG=G是G 的上中心列, 把α 和β 在每个商因子ς_iG/ς_i-1G 上的诱导自同构分别记为α_i 和β_i. 如果每个Im(α_iβ_i-β_iα_i) 或者是循环群, 或者是T⊕D, 其中T 是循环群, D 是秩1 的可除群, 那么α 和β 生成一个可解的NAF-群. 特别地, 如果α 和β 是G 的两个π′- 自同构, 那么
(i) 当每个Im(α_iβ_i-β_iα_i) 都是循环群时, α 和β 生成的群是有限幂零π- 群被有限Abel π′- 群的扩张.
(ii) 当每个Im(α_iβ_i-β_iα_i) 或者是循环群, 或者是T⊕D, 其中T 是循环群, D 是秩1 的可除群时, α 和β 生成一个剩余有限π ∪ π′- 群A, A 有正规列1≤C≤B≤A, 其中C 是有限生成的无挠幂零群, B/C 是有限幂零π- 群, A/B 是有限Abel π′- 群.
此外, 对于G 的下中心列考虑了类似的问题, 得到了对偶的结果.     

最大度不小于6的伪-Halin图的完备色数

设G为2-连通平面图,若存在G的面f₀,其中f₀的边界构成的圈上无弦且V（f₀）中的点的度至少为3,使得在G中去掉f₀边界上的所有边后得到的图为除V（f₀）中的点外度不小于3的树T,则称G为伪-Halin图;若V（f₀）中的点全为3度点,则称G为Halin-图.本文研究了这类图的完备色数,并证明了对△（G）≥ 6的伪-Halin图 G有 X_C（C）=△（G）+1.其中△（G）和X_C（G）分别表示G的最大度和完备色数.     

没有4至6-圈的平面图是(1,0,0)-可染的

设d₁, d₂,..., d_k 是k个非负整数. 若图G=(V,E) 的顶点集V可剖分成k个子集V₁, V₂,..., V_k,使得对i=1, 2,..., k 由V_i 所导出的子图G[V_i] 的最大度至多为d_i, 则称G是(d₁, d₂,..., d_k)-可染的. 著名的Steinberg 猜想断言, 每个既没有4-圈又没有5-圈的平面图是(0, 0, 0)-可染的. 对此猜想已经证明每个没有4 至7-圈的平面图是(0, 0, 0)-可染的, 但还没有发现有人证明每个没有4 至6-圈的平面图是(0, 0, 0)-可染的. 本文证明没有4 至6-圈的平面图是(1, 0, 0)-可染的.     

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

利用图的直径和围长来研究图的最大亏格的下界,得到了如下结果：设G是直径为d的简单图,若G的围长不小于d（其中d为不小于3的整数）,则ξ（G）≤2,即γM（G）≥1/2β（G）-1．而且,在这种意义下,所得到的界是最好的．     

色临界图的最大度与色数的一个关系式

研究了一类简单图G的色数x(G)与最大度△(G)的关系,对满足x(G)>(S~2+S)/2的X(G)+S阶色临界图G,证明了x(G)=△(G)+1-S,或等价地,△(G)+1-[((8△(G)+17~(1/2)-3/2]≤X(G)≤△(G)+1,这一结果部分改进了Brooks经典不等式X(G)≤△(G)+1,并完全刻画n+3(n≥4)个顶点的n-临界图的结构。     

不含三角形图的正常染色路和正常染色圈

图G为边染色图,对G中的任一顶点v,定义v的色度dc（v）：G中与顶点v相关联的边中不同染色的数目.用δc（G）表示图G的最小色度,即δc（G）=min{dc（v）：v∈G}.若图G为不含三角形的边染色图,且δc（G）≥2,则G含长为4d-2的正常染色路或长至少为2d-2的正常染色圈.     

Counterexamples to a conjecture by Gross,Mansour and Tucker on partial-dual genus polynomials of ribbon graphs

Gross, Mansour and Tucker introduced the partial-dual orientable genus polynomial and the partial-dual Euler genus polynomial. They computed these two partial-dual genus polynomials of four families of ribbon graphs, posed some research problems and made some conjectures. In this paper, we introduce the notion of signed interlace sequences of bouquets and obtain the partial-dual Euler genus polynomials for all ribbon graphs with the number of edges less than 4 and the partial-dual orientable genus polynomials for all orientable ribbon graphs with the number of edges less than 5 in terms of signed interlace sequences. We check all the conjectures and find a counterexample to the Conjecture 3.1 in their paper: There is no orientable ribbon graph having a non-constant partial-dual genus polynomial with only one non-zero coefficient. Motivated by this counterexample, we further find an infinite family of counterexamples to the conjecture.     

具有最大度距离的单圈图

设U (n)是具有n个顶点的所有单圈图的集合,G(3; n- 3)是由一个三角形C3粘上一条悬挂路P_(n-3)得到的单圈图.本文将证明当n 5时具有最大度距离的单圈图是G(3; n - 3).     

K3-free图的线图的哈密顿性

设G是一个简单图，Gi G，G1在G中的度定义为d（Gt）=∑v∈v（c）d（v），其中d（v）为v在G中的度数。本文的主要结果是：设G是n≥2阶几乎无桥的简单连通K3-free图，且G≌k1,n-1、Q1和Q2，若对G中任何同构于四个顶点路的导出子图I有d（I）≥n＋2，则G有一个D-闭迹，从而G的线图L（G）是哈密顿图。     

某些中间图的邻点可区别E-全色数

设G（V,E）是简单连通图,T（G）为图G的所有顶点和边构成的集合,并设C是k-色集（k是正整数）,若T（G）到C的映射f满足：对任意uv∈E（G）,有f（u）≠f（v）,f（u）≠f（uv）,f（v）≠f（uv）,并且C（u）≠C（v）,其中C（u）={f（u）}∪{f（uv）｜uv∈E（G）}.那么称f为图G的邻点可区别E-全染色（简记为k-AVDETC）,并称χ_（at）~e（G）=min{k｜图G有k-邻点可区别E-全染色}为G的邻点可区别E-全色数.图G的中间图M（G）就是在G的每一个边上插入一个新的顶点,再把G上相邻边上的新的顶点相联得到的.探讨了路、圈、扇、星及轮的中间图的邻点可区别E-全染色,并给出了这些中间图的邻点可区别E-全色数.     

阶数极大的临界全控制图

称一个没有孤立点的图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- 临界图.     

A class of upper-embeddable graphs

In this paper, we prove the following result: Every graph obtained by connecting (with any number of edges) two vertex-disjoint upper-embeddable graphs graphs with even Betti number is upper-embeddable.