三角代数上理想包含图的自同构

设F_q为有限域,(n_1,n_2,···,n_r)为一正整数序列,B(q,r)为由F_q上对角块为n_i(1≤i≤r)阶方阵的分块上三角阵构成的代数.理想包含图In(B(q,r))是一个有向图,它以B(q,r)为顶点集,从A到B有一条有向边当且仅当I_A■I_B,其中IA表示A生成的双边理想.本文研究了理想包含图In(B(q,r))上自同构的刻画问题.通过研究B(q,r)中理想的形式,在此基础上对给定的自同构构造一些标准自同构,使得复合后的自同构固定所有的顶点,从而给出了任意自同构的具体描述,推广了文献[13]的结果.     

有限域上矩阵环的幂映射图

对于一个环或者是乘法群H和一个正整数k,我们可以定义一个有向图G(H,k),称为H上的k次幂映射图.它的顶点集合就是H,并且从a到b有一条有向边当且仅当b=ak.交换环或者交换群上的k次幂映射图一般具有较好的对称性,这方面已经有相当多的结果.本文研究有限域上二阶矩阵环的k次幂映射图,利用线性代数和群论的方法,克服了非交换性带来的困难,得到了这类图的顶点入度的分布和圈长的分布.     

有限域上矩阵环的幂映射图（英文）

对于一个环或者是乘法群H和一个正整数k,我们可以定义一个有向图G(H,k),称为H上的k次幂映射图.它的顶点集合就是H,并且从a到b有一条有向边当且仅当b=ak.交换环或者交换群上的k次幂映射图一般具有较好的对称性,这方面已经有相当多的结果.本文研究有限域上二阶矩阵环的k次幂映射图,利用线性代数和群论的方法,克服了非交换性带来的困难,得到了这类图的顶点入度的分布和圈长的分布.     

左连续环中若干链条件的等价性

(1)设R是左连续环,则R是左Artin环当且仅当R满足左限制有限条件当且仅当R关于本质左理想满足极小条件当且仅当R关于本质左理想满足极大条件.同时给出一个左自内射环是QF环的充要条件;(2)证明了左Z₁-环上的有限生成模都有Artin-Rees性质.     

一般环之因子幂零理想

本文称环Ω的左(右)理想A为因子幂零的,如果对于任意元素r∈Ω,均有正整数m=m(r),使得A^mr={0}.称Ω的一个左理想L为关于元素b∈Ω的左因子,如果Lb≠{0}.定理4 设R是环Ω的因子幂零右理想,那么R+ΩR是Ω的一个因子幂零理想.定理7 设Ω具有局部左因子极小条件,那么Ω的任意诣零左理想必是因子幂零左理想.本文指出因子幂零性是介于幂零性与诣零性之间的一种性质,更接近幂零性。     

包含圈的一些Ramsey数

用两种颜色,比如红和蓝,给完全图K_n的边着色.把着红色和蓝色的边集分别记为E_1和E_2,把K_n的边集分别是E_1和E_2的生成子图分别记为R和B,那么称R和B是K_n的一个分解,记为K_n=R⊕B.图G_1和G_2的Ramsey数,记为r(G_1,G_2),是使得K_n的任意一个分解K_n=R⊕B有R(?)G_1或B(?)G_2的最小正整数n.这里符号G(?)H表示图G包含子图H.此外,用C_n表示长为n的圈,GVH表示图G和H的联图.K_n表示n个相互独立的点,B_n指联图K_2     

正则多部竞赛图的竞争指数

设D是一个有向图,若存在无向图G满足:(1)G的顶点集与D的顶点集相同;(2)任取D中的两个顶点x,y,其在G中相邻当且仅当存在D中顶点z,使得D中包含一条从x到z的长为m的有向途径和一条从y到z的长为m的有向途径,则称G为D的m步竞争图,记为G=C~m(D).2004年,Cho和Kim首次提出竞争指数的概念.若对于某个正整数r和所有非负整数i,存在最小正整数q,使C~(q+i)(D)=C~(q+i+r)(D),则称整数q为D的竞争指数,记为cindex(D).2008年,Kim给出了竞赛图的竞争指数的上界.2009年,Akelbek和Kirkland给出了本原有向图的竞争指数.文中研究并计算了正则多部竞赛图的竞争指数.     

关于受限制的弱准素环的一点注记

交换环R称为(受限制的)弱准素环,如果R中的每个(非零)主理想都是准素理想.本文证明了一个没有单位元的交换环R是受限制的弱准素环当且仅当R是每个元素都是幂零元的交换环或者R是仅含一个真素理想P的没有单位元的交换环并且P不真包含R的任何非零理想.     

环的极小条件包含极大条件的充要性

熟知的 C.Hopking 一般定理指出:含有左单元结合环的左理想极小条件必含左理想极大条件.本文给出了结合环(不一定含左单元)的左理想极小条件包含左理想极大条件的一个充要条件.Hopking 定理是我们定理的自然推论.对于交换结合环,Cohen 指出:若此环含有单元,则理想极小条件(记为条件(i))等价于理想极大条件以及每个素理想是极大理想(记为条件(ii)).本文给出了任意交换结合环(不一定含有单元)中条件(i)等价于条件(ii)的一个充要条件.Cohen 的结果自然是我们结果的一种特殊情况.     

奇特征域上的全正交图的自同态群（英文）

令F_q~n是奇特征有限域F_q上的n维行向量空间,S_n是F_q上任一n阶非奇异对称矩阵.S_n上的全正交图O(S_n,q)的顶点为F _q~n上的任一一维子空间,图中两顶点相邻当且仅当它们所对应的子空间[α]与[β]满足αS_(nβ)~T≠0.本文刻画了O(S_n,q)的自同态群,证明当n为偶数时,其顶点集有两个轨道;当n为奇数时,其顶点集有三个轨道.     

达到渐近GV界的一种线性映射族构造方法——生成Shannon好码渐近序列的新进展

给定有限域F_q(q≥2)、任意正整数n和k(n>k),F_q上的线性映射序列(代数族){σ_i}(σ_i:F_q^k→F_qⁿ(i→∞))的构造方法已经成为信息科学中编码理论的一个中心问题,一般称为实现Shannon理想的代数族途径.迄今为止,发现这种代数族{σ_i}的更好结构,并由它导出Shannon好码渐近序列{[n_i,k_i,d_i]}仍是一个尚未彻底解决的挑战性难题和持续不断的努力目标.衡量这种代数族的好坏,除了看{σ_i}的构造是否有利于通信工程实现(构造简明,执行复杂度低)之外,最重要的一个基本标准是看{σ_i}导出的序列{[n_i,k_i,d_i]}诸参数的渐近极限结果是否不至于衰减到渐近GilbertVarshamov(GV)界之下,该问题吸引了许多数学工作者的关注.本文从矩阵映射的观点给出一种生成任意有限域F_q上代数族{σ_i}的新方法,并表明由{σ_i}导出的渐近码序列{[n_i,k_i,d_i]}可达渐近GV界之上.这种新的代数族生成途径对于信息编码理论及其工程应用都具有很重要的意义.     

The fractional metric dimension of permutation graphs

Let G =(V(G), E(G)) be a graph with vertex set V(G) and edge set E(G). For two distinct vertices x and y of a graph G, let RG{x, y} denote the set of vertices z such that the distance from x to z is not equa l to the distance from y to z in G. For a function g defined on V(G) and for U■V(G), let g(U) =∑s∈Ug(s). A real-valued function g : V(G) → [0, 1] is a resolving function of G if g(RG{x, y}) ≥ 1 for any two distinct vertices x, y ∈ V(G). The fractional metric dimension dimf(G)of a graph G is min{g(V(G)) : g is a resolving function of G}. Let G1 and G2 be disjoint copies of a graph G, and let σ : V(G1) → V(G2) be a bijection. Then, a permutation graph Gσ =(V, E) has the vertex set V = V(G1) ∪ V(G2) and the edge set E = E(G1) ∪ E(G2) ∪ {uv | v = σ(u)}. First,we determine dimf(T) for any tree T. We show that 1 dimf(Gσ) ≤1/2(|V(G)| + |S(G)|) for any connected graph G of order at least 3, where S(G) denotes the set of support vertices of G. We also show that, for any ε 0, there exists a permutation graph Gσ such that dimf(Gσ)- 1 ε. We give examples showing that neither is there a function h1 such that dimf(G) h1(dimf(Gσ)) for all pairs(G, σ), nor is there a function h2 such that h2(dimf(G)) dimf(Gσ) for all pairs(G, σ). Furthermore,we investigate dimf(Gσ) when G is a complete k-partite graph or a cycle.     

Isomorphisms of finite semi-Cayley graphs

Let G be a finite group. A Cayley graph over G is a simple graph whose automorphism group has a regular subgroup isomorphic to G. A Cayley graph is called a CI-graph(Cayley isomorphism) if its isomorphic images are induced by automorphisms of G. A well-known result of Babai states that a Cayley graph Γ of G is a CI-graph if and only if all regular subgroups of Aut(Γ) isomorphic to G are conjugate in Aut(Γ). A semi-Cayley graph(also called bi-Cayley graph by some authors) over G is a simple graph whose automorphism group has a semiregular subgroup isomorphic to G with two orbits(of equal size). In this paper, we introduce the concept of SCI-graph(semi-Cayley isomorphism)and prove a Babai type theorem for semi-Cayley graphs. We prove that every semi-Cayley graph of a finite group G is an SCI-graph if and only if G is cyclic of order 3. Also, we study the isomorphism problem of a special class of semi-Cayley graphs.     

关于拟k-连通图的一个注释

G是一个k-连通图,T是G的一个k-点割,若G-T可被划分成两个子图G₁,G₂,且|G₁|≥2,|G₂|≥2,则称T是G的一个非平凡点割。假定G是一个不含非平凡（k-1）点割的（k-1）-连通图,则称G是一个拟k-连通图。证明了对任意一个k≥5且t> $ \frac{k}{2}$的整数,若G是一个不含（K₂+tK₁）的k-连通图,且G中任意两个不同点对v,w,有d（v）+d（w）≥ $\frac{{3k}}{2} $+t,则对G中的任意一个点,存在一条与之关联的边收缩后可以得到一个拟k-连通图,且G中至少有$\frac{{\left| {V\left( G \right)} \right|}}{2} $条边使得收缩其中任意一条边后仍是拟k-连通的。     

Unavoidable doubly connected large graphs

A connected graph is doubly connected if its complement is also connected. The following Ramsey-type theorem is proved in this paper. There exists a function h(n), defined on the set of integers exceeding three, such that every doubly connected graph on at least h(n) vertices must contain, as an induced subgraph, a doubly connected graph, which is either one of the following graphs or the complement of one of the following graphs:

(1) P_n, a path on n vertices;

(2) K_1,n^s, the graph obtained from K_1,n by subdividing an edge once;

(3) K_2,ne, the graph obtained from K_2,n by deleting an edge;

(4) K_2,n⁺, the graph obtained from K_2,n by adding an edge between the two degree-n vertices x₁ and x₂, and a pendent edge at each x_i.

Two applications of this result are also discussed in the paper.     

Reconstruction of infinite locally finite connected graphs

Let G be an infinite locally finite connected graph. We study the reconstructibility of G in relation to the structure of its end set . We prove that an infinite locally finite connected graph G is reconstructible if there exists a finite family (Ω_i)_0i (n2) of pairwise finitely separable subsets of such that, for all x,y,x′,y′V(G) and every isomorphism f of G−{x,y} onto G−{x′,y′} there is a permutation π of {0,…,n−1} such that for 0i<n. From this theorem we deduce, as particular consequences, that G is reconstructible if it satisfies one of the following properties: (i) G contains no end-respecting subdivision of the dyadic tree and has at least two ends of maximal order; (ii) the set of thick ends or the one of thin ends of G is finite and of cardinality greater than one. We also prove that if almost all vertices of G are cutvertices, then G is reconstructible if it contains a free end or if it has at least a vertex which is not a cutvertex.     

关于有限秩的幂零群的自同构

设G是有限秩的幂零群,1=ζ_0Gζ_1G …ζ_cG=G是G的上中心列,End(ζ_iG/ζ_(i-1)G)是Abel群ζ_iG/ζ_(i-1)G的自同态环(1≤i≤c),End(ζ_iG/ζ_(i-1)G)可以自然地作成一个Lie环.α_1,α_2,…,α_n是G的n个自同构,把它们在ζ_iG/ζ_(i-1)G上的诱导自同构分别记为α_(1i),α_(2i),…,α_(ni)(1≤i≤c).如果由α_(1i),α_(2i),…,α_(ni)生成的Lie环End(ζ_iG/ζ_(i-1)G)的Lie子环都是完全可解的,那么α_1,α_2,…,α_n生成的AutG的子群具有良好的幂零性质.考虑G的下中心列,可以得到对偶的结果.     

On the existence of kernels and h-kernels in directed graphs

A directed graph D with vertex set V is called cyclically h-partite (h2) provided one can partition V=V₀+V₁++V_h−1 so that if (u, υ) is an arc of D then uεV_i, and υεV_i+1 (notation mod h). In this communication we obtain a characterization of cyclically h-partite strongly connected digraphs. As a consequence we obtain a sufficient condition for a digraph to have a h-kernel.     

Induced subgraphs with large degrees at end-vertices for hamiltonicity of claw-free graphs

A graph is called claw-free if it contains no induced subgraph isomorphic to K1,3. Matthews and Sumner proved that a 2-connected claw-free graph G is Hamiltonian if every vertex of it has degree at least (|V(G)|-2)/3. At the workshop C&C (Novy Smokovec, 1993), Broersma conjectured the degree condition of this result can be restricted only to end-vertices of induced copies of N (the graph obtained from a triangle by adding three disjoint pendant edges). Fujisawa and Yamashita showed that the degree condition of Matthews and Sumner can be restricted only to end-vertices of induced copies of Z₁ (the graph obtained from a triangle by adding one pendant edge). Our main result in this paper is a characterization of all graphs H such that a 2-connected claw-free graph G is Hamiltonian if each end-vertex of every induced copy of H in G has degree at least |V(G)|/3+1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant.     

不含5-圈和相邻4-圈的平面图的线性2-荫度的一个上界

图G的一个边分解是指将G分解成子图G_1,G_2,…,G_m使得E(G)=E(G_1)=∪E(G_2)∪…∪E(G_m),且对于i≠j,E(G_i)∩E(G_j)=?.一个线性k-森林是指每个分支都是长度最多为k的路的图.图G的线性k-荫度la_k(G)是使得G可以边分解为m个线性k-森林的最小整数m.显然,la_1(G)是G的边色数χ'(G); la_∞(G)表示每条分支路是无限长度时的情况,即通常所说的G的线性荫度la(G).利用权转移的方法研究平面图的线性2-荫度la_2(G).设G是不含有5-圈和相邻4-圈的平面图,证明了若G连通且δ(G)≥2,则G包含一条边xy使得d(x)+d(y)≤8或包含一个2-交错圈.根据这一结果得到其线性2-荫度的上界为[△/2]+4.