On semicomplete multipartite digraphs whose king sets are semicomplete digraphs

Reid [Every vertex a king, Discrete Math. 38 (1982) 93-98] showed that a non-trivial tournament H is contained in a tournament whose 2-kings are exactly the vertices of H if and only if H contains no transmitter. Let T be a semicomplete multipartite digraph with no transmitters and let K_r(T) denote the set of r-kings of T. Let Q be the subdigraph of T induced by K₄(T). Very recently, Tan [On the kings and kings-of-kings in semicomplete multipartite digraphs, Discrete Math. 290 (2005) 249-258] proved that Q contains no transmitters and gave an example to show that the direct extension of Reid's result to semicomplete multipartite digraphs with 2-kings replaced by 4-kings is not true. In this paper, we (1) characterize all semicomplete digraphs D which are contained in a semicomplete multipartite digraph whose 4-kings are exactly the vertices of D. While it is trivial that K₄(Q)⊆K₄(T), Tan [On the kings and kings-of-kings in semicomplete multipartite digraphs, Discrete Math. 290 (2005) 249-258] showed that K₃(Q)⊆K₃(T) and K₂(Q)=K₂(T). Tan [On the kings and kings-of-kings in semicomplete multipartite digraphs, Discrete Math. 290 (2005) 249-258] also provided an example to show that K₃(Q) need not be the same as K₃(T) in general and posed the problem: characterize all those semicomplete multipartite digraphs T such that K₃(Q)=K₃(T). In the course of proving our result (1), we (2) show that K₃(Q)=K₃(T) for all semicomplete multipartite digraphs T with no transmitters such that Q is a semicomplete digraph.     

On the periodic points of functions on a manifold

In a conference on fixed point theory, B. Halpern of Indiana University considered the problem of reducing the number of periodic points of a map by homotopy. He also asked whether the number of periodic points of a function could be increased by a homotopy. In this paper, we will show that for any map on a closed manifold, an arbitrarily small perturbation can always create infinitely many periodic points of arbitrarily high periods.

     

On weakly cospectral graphs

We prove that any set of pair-wise nonisomorphic strongly connected weakly cospectral pseudodigraphs whose set of nilpotency indices is finite also is finite.     

Linkless symmetric drawings of series parallel digraphs

In this paper, we present a linear time algorithm for constructing linkless drawings of series parallel digraphs with maximum number of symmetries. Linkless drawing in three dimensions is a natural extension to planar drawing in two dimensions. Symmetry is one of the most important aesthetic criteria in graph drawing. More specifically, we present two algorithms: a symmetry finding algorithm which finds maximum number of three dimensional symmetries, and a drawing algorithm which constructs linkless symmetric drawings of series parallel digraphs in three dimensions.     

The metric dimension of Cayley digraphs

A vertex x in a digraph D is said to resolve a pair u, v of vertices of D if the distance from u to x does not equal the distance from v to x. A set S of vertices of D is a resolving set for D if every pair of vertices of D is resolved by some vertex of S. The smallest cardinality of a resolving set for D, denoted by dim(D), is called the metric dimension for D. Sharp upper and lower bounds for the metric dimension of the Cayley digraphs Cay(Δ:Γ), where Γ is the group Z_n1⊕Z_n2⊕?⊕Z_nm and Δ is the canonical set of generators, are established. The exact value for the metric dimension of Cay({(0,1),(1,0)}:Z_n⊕Z_m) is found. Moreover, the metric dimension of the Cayley digraph of the dihedral group D_n of order 2n with a minimum set of generators is established. The metric dimension of a (di)graph is formulated as an integer programme. The corresponding linear programming formulation naturally gives rise to a fractional version of the metric dimension of a (di)graph. The fractional dual implies an integer dual for the metric dimension of a (di)graph which is referred to as the metric independence of the (di)graph. The metric independence of a (di)graph is the maximum number of pairs of vertices such that no two pairs are resolved by the same vertex. The metric independence of the n-cube and the Cayley digraph Cay(Δ:D_n), where Δ is a minimum set of generators for D_n, are established.     

关于交换群上的Cayley有向图的正规性

Cayley有向图X=Cay(G,S)叫做正规的,如果G的右正则表示R(G)在X的全自同构群Aut(X)中正规,我们定出了交换群上的小度数的非正规的Cayley有向图, 并给出了一个猜想．应用这个结果,给出了pn(n≤2)个点上的度数不超过3的有向对称图的分类,这里p是一个奇素数．     

关于有向整谱图的若干存在性问题

系统的回答了[1]在1974年提出的关于有向整谱图的两个问题：1．什么样的非对称强连通有向图是整的？是否存在这样的有向图？2．什么样的多重有向图是整的？。     

广义de Bruijn和Kautz有向图的双向控制集

设G=(V,A)是一个有向图,其中V和A分别表示有向图G的点集和弧集.对集合TV(G),如果对于任意点v∈V(G)\T,都存在点u,w∈T(u,w可能是同一点)使得(u,v),(v,w)∈A(G),则称T是G的一个双向控制集.有向图G的双向控制数γ~*(G)是G的最小双向控制集所含点的数目.提出了广义de Bruijn和Kautz有向图的双向控制数的新上界,改进了以前文献中提出的相关结论.此外,对某些特殊的广义de Bruijn和Kautz有向图,通过构造其双向控制集,进一步改进了它们双向控制数的上、下界.     

On Cayley digraphs on nonisomorphic 2‐groups

A necessary and sufficient condition is given for two Cayley digraphs X₁ = Cay(G₁, S₁) and X₂ = Cay(G₂, S₂) to be isomorphic, where the groups G_i are nonisomorphic abelian 2‐groups, and the digraphs X_i have a regular cyclic group of automorphisms. Our result extends that of Morris [J Graph Theory 3 (1999), 345–362] concerning p‐groups G_i, where p is an odd prime. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory     

平衡半传递有向图的弧连通性

有向图D=（V, E）被称为是极大弧连通的,如果λ（D）=δ（D）。此外,有向图D被称为是超弧连通的,如果每个最小的弧割都是其某个点的入弧集或者出弧集。以X1和X2为两部的一个有向二部图是半传递的,如果自同构群Aut（D）分别传递的作用在X1和X2上。在这篇论文中,证明了强连通的半传递有向图是极大弧连通的。还证明了除了少部分例外,连通半传递平衡有向图是超弧连通的。