拓扑遍历映射的一些性质

本文研究拓扑遍历映射.指出对于由不可约方阵所决定的符号空间有限型子转移而言,或紧致交换群的仿射变换及线段上连续自映射而言,拓扑遍历与拓扑可迁这两个概念是一致的.同时还通过例子,指出拓扑遍历是不同于拓扑可迁与拓扑混合的概念.     

三类有向三元系之间关系的一种猜想

一个Mendelsohn (Directed, 或Hybrid)三元系 MTS$(v, \lambda)$~(DTS$(v, \lambda)$,或HTS$(v,\lambda))$, 是由$v$元集$X$ 上的一些循环（可迁,或循环和可迁）三元组(简称区组)构成的集合${\cal B}$, 使得$X$上每个由不同元素组成的有序对都恰在 ${\cal B}$的$\lambda$个区组中出现.本文主要讨论了这三类有向三元系之间的一种关联关系,给出猜想：任意MTS$(v,\lambda)$的区组关联图$G(\     

Completing orientations of partially oriented graphs

We initiate a general study of what we call orientation completion problems. For a fixed class of oriented graphs, the orientation completion problem asks whether a given partially oriented graph P can be completed to an oriented graph in by orienting the (nonoriented) edges in P. Orientation completion problems commonly generalize several existing problems including recognition of certain classes of graphs and digraphs as well as extending representations of certain geometrically representable graphs. We study orientation completion problems for various classes of oriented graphs, including k‐arc‐strong oriented graphs, k‐strong oriented graphs, quasi‐transitive‐oriented graphs, local tournaments, acyclic local tournaments, locally transitive tournaments, locally transitive local tournaments, in‐tournaments, and oriented graphs that have directed cycle factors. We show that the orientation completion problem for each of these classes is either polynomial time solvable or NP‐complete. We also show that some of the NP‐complete problems become polynomial time solvable when the input‐oriented graphs satisfy certain extra conditions. Our results imply that the representation extension problems for proper interval graphs and for proper circular arc graphs are polynomial time solvable. The latter generalizes a previous result.     

Edge‐transitive homogeneous factorizations of complete uniform hypergraphs

For a finite set V and a positive integer k with , letting be the set of all k‐subsets of V, the pair is called the complete k‐hypergraph on V, while each k‐subset of V is called an edge. A factorization of the complete k‐hypergraph of index , simply a ‐factorization of order n, is a partition of the edges into s disjoint subsets such that each k‐hypergraph , called a factor, is a spanning subhypergraph of . Such a factorization is homogeneous if there exist two transitive subgroups G and M of the symmetric group of degree n such that G induces a transitive action on the set and M lies in the kernel of this action. In this article, we give a classification of homogeneous factorizations of that admit a group acting transitively on the edges of . It is shown that, for and , there exists an edge‐transitive homogeneous ‐factorization of order n if and only if is one of (32, 3, 5), (32, 3, 31), (33, 4, 5), , and , where and q is a prime power with .     

Diffeomorphisms with C 1-stably average shadowing

Let M be a closed smooth manifold M, and let f : M → M be a diffeomorphism. In this paper, we consider a nontrivial transitive set Λ of f . We show that if f has the C1-stably average shadowing property on Λ, then Λ admits a dominated splitting.     

On Finite 2‐Path‐Transitive Graphs

The class of graphs that are 2‐path‐transitive but not 2‐arc‐transitive is investigated. The amalgams for such graphs are determined, and structural information regarding the full automorphism groups is given. It is then proved that a graph is 2‐path‐transitive but not 2‐arc‐transitive if and only if its line graph is half‐arc‐transitive, thus providing a method for constructing new families of half‐arc‐transitive graphs. © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 225–237, 2013     

Vertex‐Transitive Cubic Graphs of Square‐Free Order

A classification of connected vertex‐transitive cubic graphs of square‐free order is provided. It is shown that such graphs are well‐characterized metacirculants (including dihedrants, generalized Petersen graphs, Möbius bands), or Tutte's 8‐cage, or graphs arisen from simple groups PSL(2, p).     

Unitary Graphs

Unitary graphs are arc‐transitive graphs with vertices the flags of Hermitian unitals and edges defined by certain elements of the underlying finite fields. They played a significant role in a recent classification of a class of arc‐transitive graphs that admit an automorphism group acting imprimitively on the vertices. In this article, we prove that all unitary graphs are connected of diameter two and girth three. Based on this, we obtain, for any prime power , a lower bound of order on the maximum number of vertices in an arc‐transitive graph of degree and diameter two.     

Smallest Vertex‐Transitive Graphs of Given Degree and Diameter

For every d and k, we determine the smallest order of a vertex‐transitive graph of degree d and diameter k, and in each such case we show that this order is achieved by a Cayley graph.