Irreducible matrices with reducible principal submatrices

Let A be a (0, 1)-matrix of order n 3 and let s_i⁰(A), i = 1, …, n, be the number of the off diagonal 0's in row and column i of A. We prove that if A is irreducible, and if all its principal submatrices of order (n − 1) are reducible, then s_i⁰(A) n − 1; i = 1, …, n. This establishes the validity of a conjecture by B. Schwarz concerning strongly connected graphs and their primal subgraphs.     

Galois Graphs: Walks, Trees and Automorphisms

Given a symmetric polynomial (x, y) over a perfect field k of characteristic zero, the Galois graph G() is defined by taking the algebraic closure as the vertex set and adjacencies corresponding to the zeroes of (x, y). Some graph properties of G(), such as lengths of walks, distances and cycles are described in terms of . Symmetry is also considered, relating the Galois group Gal( /k) to the automorphism group of certain classes of Galois graphs. Finally, an application concerning modular curves classifying pairs of isogeny elliptic curves is revisited.     

常微分方程系统中内部激变现象的研究

应用广义胞映射图论方法研究常微分方程系统的激变.揭示了边界激变是由于混沌吸引子与 在其吸引域边界上的周期鞍碰撞产生的,在这种情况下,当系统参数通过激变临界值时,混 沌吸引子连同它的吸引域突然消失,在相空间原混沌吸引子的位置上留下了一个混沌鞍.研 究混沌吸引子大小(尺寸和形状)的突然变化,即内部激变.发现这种混沌吸引子大小的突然 变化是由于混沌吸引子与在其吸引域内部的混沌鞍碰撞产生的,这个混沌鞍是相空间非吸引 的不变集,代表内部激变后混沌吸引子新增的一部分.同时研究了这个混沌鞍的形成与演化. 给出了对永久自循环胞集和瞬态自循环胞集进行局部细化的方法. 关键词： 广义胞映射 有向图 激变 混沌鞍     

含正元个数最少的本原矩阵

设(n,d)={A|A是含d个正对角元的n阶本原矩阵,r(A)=k}.对d=1,2,…,n,k=2,3,…,n-2,本文分别刻划了(n,d)中含正元个数最少的矩阵.     

一类具有全实Laplacian谱的有向图

分别研究了一类带有Hamiltonian路和带有Hamiltonian圈的有向图的基本有圈性（essential cyclicity）,给出了这种有向图的Laplacian谱,表明这些图具有全实的Laplacian谱.     

有向循环图的直径与覆盖指数

本文给出了有向循环图的直径的一个关系式,并讨论了直径与覆盖指数之间的关系。     

一类极小本原对称图的指数集

运用有向图方法完全确定出顶点带环的n阶极小本原对称有向图的本原指数集,所得的结论是:1)顶点全部自带环的n阶极小本原对称有向图所成的子图类之本原指数集E1={2,3,…,n-1};2)顶点不全带环的n阶极小本原对称有向图所成的子图类之本原指数集E2={2,3,…,2n-2}\S,其中S是{n,n+1,…,2n-2}中的所有奇数之集;3)顶点带环的n阶极小本原对称有向图所成的特殊图类之本原指数集En=E1∪E2={2,3,…,2n-2}\S.     

Small degree out‐branchings

Using a suitable orientation, we give a short proof of a strengthening of a result of Czumaj and Strothmann 4 : Every 2‐edge‐connected graph G contains a spanning tree T with the property that for every vertex v. As an analogue of this result in the directed case, we prove that every 2‐arc‐strong digraph D has an out‐branching B such that . A corollary of this is that every k‐arc‐strong digraph D has an out‐branching B such that , where . We conjecture that in this case would be the right (and best possible) answer. If true, this would again imply a strengthening of a result from 4 concerning spanning trees with small degrees in k‐connected graphs when k ≥ 2. We prove that for acyclic digraphs the existence of an out‐branching satisfying prescribed bounds on the out‐degrees of each vertex can be checked in polynomial time. A corollary of this is that the existence of arc‐disjoint branchings , , where the first is an out‐branching rooted at s and the second an in‐branching rooted at t, can be checked in polynomial time for the class of acyclic digraphs © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 297–307, 2003     

具有有限周期的无限布尔方阵的传递指数

给出了无限布尔方阵周期的概念,研究了无限布尔方阵伴随有向图的若干性质,研究了有限布尔矩阵幂的图论性质,最后给出了无限布尔方阵传递指数的上、下界估计.