Super-connected arc-transitive digraphs

A digraph is said to be super-connected if every minimum vertex cut is the out-neighbor set or in-neighbor set of a vertex. A digraph is said to be reducible, if there are two vertices with the same out-neighbor set or the same in-neighbor set. In this paper, we prove that a strongly connected arc-transitive oriented graph is either reducible or super-connected. Furthermore, if this digraph is also an Abelian Cayley digraph, then it is super-connected.     

ON ARC-TRANSITIVE CIRCULANT DIGRAPHS

Denote by c,(s)the circulant digraph with vertex set zn=[0,1,2……n-1]and symbol set s(≠-s)∈zn\[0].let x be the automorphism group of cn(S)and xo the stabilizer of o in x.then cn(S)is arctransitive if and only if xo acts transitively on s.in this paper,co(S)with xo is being the symmetric group is characterized by its symbot set .by the way all the arctransitive clcculant digraphs of degree 2are given.     

Some constructions of highly arc-transitive digraphs

We construct infinite highly arc-transitive digraphs with finite out-valency and whose sets of descendants are digraphs which have a homomorphism onto a directed (rooted) tree. Some of these constructions are based on [4] and [5], and are shown to have universal reachability relation.     

Point-symmetric graphs and digraphs of prime order and transitive permutation groups of prime degree

In this paper the following two problems are solved: Given any point-symmetric graph or digraph Γ of prime order the automorphism group of Γ is explicitly determined and given any transitive permutation group G of prime degree p the number of digraphs and graphs of order p having G as their automorphism group is determined.     

Bounded degree acyclic decompositions of digraphs

An acyclic decomposition of a digraph is a partition of the edges into acyclic subgraphs. Trivially every digraph has an acyclic decomposition into two subgraphs. It is proved that for every integer s2 every digraph has an acyclic decomposition into s subgraphs such that in each subgraph the outdegree of each vertex v is at most . For all digraphs this degree bound is optimal.     

ISOMORPHISMS OF CIRCULANT DIGRAPHS OF DEGREE 3

Abstract. In this paper, we introduce a new approach to characterize the isomor-phisms of circulant digraphs. In terms of this method, we completely determine the isomorphic classes of circulant digraphs of degree 3. In psrticular, we characterize those circulant digraphs of degree 3 which don‘‘t satisfy JkdAm‘‘s conjectttre.     

Maximum directed cuts in digraphs with degree restriction

For integers m, k≥1, we investigate the maximum size of a directed cut in directed graphs in which there are m edges and each vertex has either indegree at most k or outdegree at most k. © 2009 Wiley Periodicals, Inc. J Graph Theory     

On labeled vertex-transitive digraphs with a prime number of vertices

We enumerate, up to isomorphism, several classes of labeled vertex-transitive digraphs with a prime number of vertices.     

On isomorphisms of circulant digraphs of bounded degree

C.H. Li recently made the following conjecture: Let Γ be a circulant digraph of order n=n₁n₂ and degree m, where gcd(n₁,n₂)=1, n₁ divides 4k, where k is odd and square-free, and every prime divisor of n₂ is greater than m, or, if Γ is a circulant graph, every prime divisor of n₂ is greater than 2m. Then Γ is a CI-digraph of Z_n. In this paper we verify that this conjecture is true.     

Neighborhood and degree conditions for super-edge-connected bipartite digraphs

A graph or digraph D is called super-λ, if every minimum edge cut consists of edges incident to or from a vertex of minimum degree, where λ is the edge-connectivity of D. Clearly, if D is super-λ, then λ = δ, where δ is the minimum degree of D. In this paper neighborhood, degree sequence, and degree conditions for bipartite graphs and digraphs to be super-λ are presented. In particular, the neighborhood condition generalizes the following result by Fiol [7]: If D is a bipartite digraph of order n and minimum degree δ ≥ max{3, ?(n + 3)/4?}, then D is super-λ.     

Complete characterization of almost Moore digraphs of degree three

It is well known that Moore digraphs do not exist except for trivial cases (degree 1 or diameter 1), but there are digraphs of diameter two and arbitrary degree which miss the Moore bound by one. No examples of such digraphs of diameter at least three are known, although several necessary conditions for their existence have been obtained. In this paper, we prove that digraphs of degree three and diameter k ≥ 3 which miss the Moore bound by one do not exist. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 112–126, 2005     

Indices of Kummer extensions of prime degree

Let p be a prime and let ${\zeta }_p$ be a primitive p-th root of unity. For a finite extension k of $\mathbb{Q}$ containing ${\zeta }_p$, we consider a Kummer extension $L/k$ of degree p. In this paper, we show that if $k=\mathbb{Q}({\zeta }_p)$ and the class number of k is one, the index of $L/k$ is one. We also show that if $L/k$ is tamely ramified with a normal integral basis, the index is at most a power of p. In the last section, we show that there exist infinitely many cubic Kummer extensions of $\mathbb{Q}({\zeta }_3)$ for both wildly and tamely ramified cases, whose integer rings do not have a power integral basis over that of $\mathbb{Q}({\zeta }_3)$.     

Roots of solvable polynomials of prime degree

An explicit formula for the most general root of a solvable polynomial of prime degree is stated and proved. Such a root can be expressed rationally in terms of a single compound radical determined by the roots of a cyclic polynomial whose degree divides μ−1$\mu -1$, where μ$\mu$ is the prime. The study of such formulas was initiated by a formula of Abel for roots of quintic polynomials that are solvable, and was carried forward by Kronecker and a few others, but seems to have lain dormant since 1924. A formula equivalent to the one given here is contained in a paper of Anders Wiman in 1903, but it seems to have been forgotten.