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

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

On the sphericity testing of single source digraphs

A digraph D=(V,A) is called spherical, if it has an upward embedding on the round sphere which is an embedding of D on the round sphere so that all edges are monotonic arcs and all point to a fixed direction, say to the north pole. It is easy to see that [S.M. Hashemi, Digraph embedding, Discrete Math. 233 (2001) 321-328] for upward embedding, plane and sphere are not equivalent, which is in contrast with the fact that they are equivalent for undirected graphs. On the other hand, it has been proved that sphericity testing for digraphs is an NP-complete problem [S.M. Hashemi, A. Kisielewicz, I. Rival, The complexity of upward drawings on spheres, Order 14 (1998) 327-363]. In this work we study sphericity testing of the single source digraphs. In particular, we shall present a polynomial time algorithm for sphericity testing of three connected single source digraphs.     

Note on a min‐max conjecture of Woodall

In 1978 Woodall [ 6 ] conjectured the following: in a planar digraph the size of a shortest cycle is equal to the maximum cardinality of a collection of disjoint tranversals of cycles. We prove that this conjecture is true when the digraph is series‐parallel. In fact, we prove a stronger weighted version that gives the latter result as a corollary. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 36–41, 2001     

系列平行图的边面染色

一个平面图G的边面色数xef(G)是指对G的边和面进行染色所用最少的颜色数目,并同时使得相邻或相关联的两个元素间染不同颜色.若G是一个系列平行图,也就是不含K_4的剖分作为子图的平面图,则有Xef(G)≤max{7,△(G) 1};同时如果G还是2-连通的且△(G)>6,则有Xef(G)=△.     

有向图n·_3优美的进一步性质

本文在我们以往研究基础上 ,得到了有向图 n· C 3优美的进一步性质 :两个无交有向图 n· C 3各自的公共顶点与一个新增加的顶点 ,分别用有向弧来连接 ,使该新增加顶点的出度为 2或入度为 2时 ,这样连接而得的有向图为优美图     

The Directed Geodetic Structure of a Strong Digraph

By a ternary structure we mean an ordered pair (U ₀, T ₀), where U ₀is a finitenonempty set and T ₀is a ternary relation on U ₀. A ternary structure (U ₀, T ₀) is called here a directed geodetic structure if there exists a strong digraph Dwith the properties that V(D) = U ₀and T ₀ (u,v, w)if and only if d _D (u,v)+ d _D (v,w)= d _D (u, w) for all u, v, w U ₀, where d _Ddenotes the (directed) distance function in D. It is proved in this paper that there exists no sentence sof the language of the first-order logic such that a ternary structure is a directed geodetic structure if and only if it satisfies s.     

路图P3(G)的色数

设G是一个图,G的路图P3(G)的顶点集是G中所有三个顶点的路P3, 当G中的两个P3路形成P4路或C3圈时,在P3(G)中它们所代表的两个顶点相邻. 在这篇文章中,我们得到对于一个无三角形的图G, χ(P3(G))≤β(G),其中β(G)表G的点覆盖数. 对于顶点数至少为3的连通图G,χ(P3(G))≤2当且仅当G是二部图, 并且χ(P3(G))=1当且仅当 G是星图. 对于K4的剖分图G,2≤χ(P3(G))≤3. 对于系列平行图和外可平面图G,χ(P3(G))≤3.     

Circulant digraphs determined by their spectra

Inspired by Ádám's conjecture the isomorphism problem of circulant digraphs is widely investigated. In the literature, the spectrum method was to solve the isomorphism problem for the circulants of prime-power order by some people. In this paper, we develop the spectrum method to characterize the circulant digraphs of orders p^a and p^aq^b, where p and q are distinct primes.     

n阶本原极小强连通有向图k-指数的最小值

本文证明了:当1≤k≤︱n/4︱时,n阶本原极小强连通有向图k指数的最小值是4。     

有向图4-→Cn的优美性

研究了有向图m→C n 的优美性,利用搜索图的标号的算法与数学证明相结合的方法,证明了有向图4→ Cn 为优美图,其中n为任意正整数。