On a class of binary linear completely transitive codes with arbitrary covering radius

An infinite class of new binary linear completely transitive (and so, completely regular) codes is given. The covering radius of these codes is growing with the length of the code. In particular, for any integer ρ≥2, there exist two codes in the constructed class with d=3, covering radius ρ and lengths and , respectively. The corresponding distance-transitive graphs, which can be defined as coset graphs of these completely transitive codes are described.     

射影线性群区传递作用于5-(q+1,7,λ)设计

设D 是一个t-(v,k,λ)设计,G 是D 的一个自同构群,CAMERON等证明了如果G 是区传递的,则t≤7并且G在点集合上是［t/2］传递的. 对t≤4,已有研究取得了一些研究成果.本文主要讨论t=5时的情形,并且假定G是特殊射影线性群PSL(2,q)3-齐次作用在5-(v,7,λ)设计上,此时v=q+1,利用这2个群在射影线上作用的轨道,讨论了5-(v,7,λ)设计的存在性,并构造出了具有给定参数的单纯5-(v,7,λ)设计.     

On cubic non‐Cayley vertex‐transitive graphs

In 1983, the second author [D. Maru?i?, Ars Combinatoria 16B (1983), 297–302] asked for which positive integers n there exists a non‐Cayley vertex‐transitive graph on n vertices. (The term non‐Cayley numbers has later been given to such integers.) Motivated by this problem, Feng [Discrete Math 248 (2002), 265–269] asked to determine the smallest valency ?(n) among valencies of non‐Cayley vertex‐transitive graphs of order n. As cycles are clearly Cayley graphs, ?(n)?3 for any non‐Cayley number n. In this paper a goal is set to determine those non‐Cayley numbers n for which ?(n) = 3, and among the latter to determine those for which the generalized Petersen graphs are the only non‐Cayley vertex‐transitive graphs of order n. It is known that for a prime p every vertex‐transitive graph of order p, p² or p³ is a Cayley graph, and that, with the exception of the Coxeter graph, every cubic non‐Cayley vertex‐transitive graph of order 2p, 4p or 2p² is a generalized Petersen graph. In this paper the next natural step is taken by proving that every cubic non‐Cayley vertex‐transitive graph of order 4p², p>7 a prime, is a generalized Petersen graph. In addition, cubic non‐Cayley vertex‐transitive graphs of order 2p^k, where p>7 is a prime and k?p, are characterized. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 77–95, 2012     

Tetravalent half‐edge‐transitive graphs and non‐normal Cayley graphs

Let X be a vertex‐transitive graph, that is, the automorphism group Aut(X) of X is transitive on the vertex set of X. The graph X is said to be symmetric if Aut(X) is transitive on the arc set of X. suppose that Aut(X) has two orbits of the same length on the arc set of X. Then X is said to be half‐arc‐transitive or half‐edge‐transitive if Aut(X) has one or two orbits on the edge set of X, respectively. Stabilizers of symmetric and half‐arc‐transitive graphs have been investigated by many authors. For example, see Tutte [Canad J Math 11 (1959), 621–624] and Conder and Maru?i? [J Combin Theory Ser B 88 (2003), 67–76]. It is trivial to construct connected tetravalent symmetric graphs with arbitrarily large stabilizers, and by Maru?i? [Discrete Math 299 (2005), 180–193], connected tetravalent half‐arc‐transitive graphs can have arbitrarily large stabilizers. In this article, we show that connected tetravalent half‐edge‐transitive graphs can also have arbitrarily large stabilizers. A Cayley graph Cay(G, S) on a group G is said to be normal if the right regular representation R(G) of G is normal in Aut(Cay(G, S)). There are only a few known examples of connected tetravalent non‐normal Cayley graphs on non‐abelian simple groups. In this article, we give a sufficient condition for non‐normal Cayley graphs and by using the condition, infinitely many connected tetravalent non‐normal Cayley graphs are constructed. As an application, all connected tetravalent non‐normal Cayley graphs on the alternating group A₆ are determined. © 2011 Wiley Periodicals, Inc. J Graph Theory     

The structure on invariant measures of <Emphasis Type="Italic">C</Emphasis><Superscript>1</Superscript> generic diffeomorphisms

Let Λ be an isolated non-trivial transitive set of a C 1 generic diffeomorphism f ∈ Diff (M ). We show that the space of invariant measures supported on Λ coincides with the space of accumulation measures of time averages on one orbit. Moreover, the set of points having this property is residual in Λ (which implies that the set of irregular+ points is also residual in Λ). As an application, we show that the non-uniform hyperbolicity of irregular+ points in Λ with totally 0 measure (resp., the non-uniform hyperbolicity of a generic subset in Λ) determines the uniform hyperbolicity of Λ.     

上连通和超连通六次点传递图

图 G 称为上连通的,若对每个最小割集C,G-C 有孤立点.G 称为超连通的,若对每个最小割集C,G-C恰有两个连通分支,且其中之一为孤立点.本文刻画了上连通或超连通六次点传递图.     

Landau's inequalities for tournament scores and a short proof of a theorem on transitive sub‐tournaments

Ao and Hanson, and Guiduli, Gyárfás, Thomassé and Weidl independently, proved the following result: For any tournament score sequence S = (s₁, s₂, … ,s_n) with s₁≤s₂ ≤ … ≤ s_n, there exists a tournament T on vertex set {1,2, …, n} such that the score of each vertex i is s_i and the sub‐tournaments of T on both the even and the odd indexed vertices are transitive in the given order; that is, i dominates j whenever i > j and i ≡ j (mod 2). In this note, we give a much shorter proof of the result. In the course of doing so, we show that the score sequence of a tournament satisfies a set of inequalities which are individually stronger than the well‐known set of inequalities of Landau, but collectively the two sets of inequalities are equivalent. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 244–254, 2001     

Number of minimum vertex cuts in transitive graphs

Let G be a k-regular vertex transitive graph with connectivity κ(G)=k and let m_k(G) be the number of vertex cuts with k vertices. Define m(n,k)=min{m_k(G): GT_n,k}, where T_n,k denotes the set of all k-regular vertex transitive graphs on n vertices with κ(G)=k. In this paper, we determine the exact values of m(n,k).     

Independent sets in tensor graph powers

The tensor product of two graphs, G and H, has a vertex set V(G) × V(H) and an edge between (u,v) and (u′,v′) iff both u u′ ∈ E(G) and v v′ ∈ E(H). Let A(G) denote the limit of the independence ratios of tensor powers of G, lim, α(Gⁿ)/|V(Gⁿ)|. This parameter was introduced in [Brown, Nowakowski, Rall, SIAM J Discrete Math 9 ( 5 ), 290–300], where it was shown that A(G) is lower bounded by the vertex expansion ratio of independent sets of G. In this article we study the relation between these parameters further, and ask whether they are in fact equal. We present several families of graphs where equality holds, and discuss the effect the above question has on various open problems related to tensor graph products. © 2006 Wiley Periodicals, Inc. J Graph Theory     

Chain Dominated Orders

We study finite partial orders which have a chain such that every element of the order either belongs to this chain or has all its covers in this chain. We show that such orders are exactly the orders being both interval orders and truncated lattices. We prove that their jump number is polynomially tractable and that their dimension is unbounded. We also show that every order admits a visibility model having such an order as host.