Minimal n-fach zusammenhängende Digraphen

For a minimally n-connected digraph D, the subgraph spanned by the edges (x, y) with outdegree of x and indegree of y exceeding n is denoted by D₀. It is proved that D₀ corresponds to a forest. This implies that in a finite, minimally n-connected digraph D, the number of vertices of outdegree n is at least n and that the number of vertices of outdegree or indegree equal to n grows linearly in |D|. For almost every integer m, the maximum number of edges in a minimally n-connected digraph of order m is determined and the extremal digraphs are characterized.     

Spectral radius of digraphs with given dichromatic number

Let D be a digraph with vertex set V(D). A partition of V(D) into k acyclic sets is called a k-coloring of D. The minimum integer k for which there exists a k-coloring of D is the dichromatic number χ(D) of the digraph D. Denote G_n,k the set of the digraphs of order n with the dichromatic number k≥2. In this note, we characterize the digraph which has the maximal spectral radius in G_n,k. Our result generalizes the result of [8] by Feng et al.     

On the structure of strong 3-quasi-transitive digraphs

In this paper, D=(V(D),A(D)) denotes a loopless directed graph (digraph) with at most one arc from u to v for every pair of vertices u and v of V(D). Given a digraph D, we say that D is 3-quasi-transitive if, whenever u→v→w→z in D, then u and z are adjacent or u=z. In Bang-Jensen (2004) [3], Bang-Jensen introduced 3-quasi-transitive digraphs and claimed that the only strong 3-quasi-transitive digraphs are the strong semicomplete digraphs and strong semicomplete bipartite digraphs. In this paper, we exhibit a family of strong 3-quasi-transitive digraphs distinct from strong semicomplete digraphs and strong semicomplete bipartite digraphs and provide a complete characterization of strong 3-quasi-transitive digraphs.     

Wielandt type theorem for Cartesian product of digraphs

We show that mn-1 is an upper bound of the exponent of the Cartesian product D×E of two digraphs D and E on m,n vertices, respectively and we prove our upper bound is extremal when (m,n)=1. We also find all D and E when the exponent of D×E is mn-1. In addition, when m=n, we prove that the extremal upper bound of exp(D×E) is n²-n+1 and only the Cartesian product, Z_n×W_n, of the directed cycle and Wielandt digraph has exponent equals to this bound.     

Longest path partitions in generalizations of tournaments

We consider the so-called Path Partition Conjecture for digraphs which states that for every digraph, D, and every choice of positive integers, λ₁,λ₂, such that λ₁+λ₂ equals the order of a longest directed path in D, there exists a partition of D into two digraphs, D₁ and D₂, such that the order of a longest path in D_i is at most λ_i, for i=1,2.We prove that certain classes of digraphs, which are generalizations of tournaments, satisfy the Path Partition Conjecture and that some of the classes even satisfy the conjecture with equality.     

On the immersion of digraphs in cubes

We consider some problems concerning generalizations of embeddings of acyclic digraphs inton-dimensional dicubes. In particular, we define an injectioni from a digraphD into then-dimensional dicubeQ _n to be animmersion if for any two elementsa andb inD there is a directed path inD froma tob iff there is a directed path inQ _n fromi(a) toi(b). We further define the immersion to bestrong iff there is a way of choosing these paths so that paths inQ _n corresponding to arcs inD have disjoint interiors, and we introduce a natural notion of “minimality” on the set of arcs of a digraph in terms of its paths. Our main theorem then becomes:Every (minimal) n-element acyclic digraph can be (strongly) immersed in Q _n. We also present examples ofn-element digraphs which cannot be immersed inQ _n?1 and examples of 9n-element non-minimal digraphs which cannot be strongly immersed inQ10n _?1. We conclude with some applications.     

Infinite families of 2-hypohamiltonian/2-hypotraceable oriented graphs

A digraph D of order n is r-hypohamiltonian (respectively r-hypotraceable) for some positive integer r < n ? 1 if D is nonhamiltonian (nontraceable) and the deletion of any r of its vertices leaves a hamiltonian (traceable) digraph. A 1-hypohamiltonian (1-traceable) digraph is simply called hypohamiltonian (hypotraceable). Although hypohamiltonian and hypotraceable digraphs are well-known and well-studied concepts, we have found no mention of r-hypohamiltonian or r-hypotraceable digraphs in the literature for any r > 1. In this paper we present infinitely many 2-hypohamiltonian oriented graphs and use these to construct infinitely many 2-hypotraceable oriented graphs. We also discuss an interesting connection between the existence of r-hypotraceable oriented graphs and the Path Partition Conjecture for oriented graphs.     

On the number of noncritical vertices in strongly connected digraphs

By definition, a vertex w of a strongly connected (or, simply, strong) digraph D is noncritical if the subgraph D — w is also strongly connected. We prove that if the minimal out (or in) degree k of D is at least 2, then there are at least k noncritical vertices in D. In contrast to the case of undirected graphs, this bound cannot be sharpened, for a given k, even for digraphs of large order. Moreover, we show that if the valency of any vertex of a strong digraph of order n is at least 3/4n, then it contains at least two noncritical vertices. The proof makes use of the results of the theory of maximal proper strong subgraphs established by Mader and developed by the present author. We also construct a counterpart of this theory for biconnected (undirected) graphs.     

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.     

Double-super-connected digraphs

A strongly connected digraph D is said to be super-connected if every minimum vertex-cut is the out-neighbor or in-neighbor set of a vertex. A strongly connected digraph D is said to be double-super-connected if every minimum vertex-cut is both the out-neighbor set of a vertex and the in-neighbor set of a vertex. In this paper, we characterize the double-super-connected line digraphs, Cartesian product and lexicographic product of two digraphs. Furthermore, we study double-super-connected Abelian Cayley digraphs and illustrate that there exist double-super-connected digraphs for any given order and minimum degree.     

A note on decompositions of transitive tournaments

For any positive integer n, we determine all connected digraphs G of size at most four, such that a transitive tournament of order n is G-decomposable. Among others, these results disprove a generalization of a theorem of Sali and Simonyi [Orientations of self-complementary graphs and the relation of Sperner and Shannon capacities, European J. Combin. 20 (1999), 93–99].     

Polynomial addition sets and polynomial digraphs

Let G be a group of order v, and f(x) be a nonzero integral polynomial. A (v, k, f(x))-polynomial addition set in G is a subset D of G with k distinct elements such that f(Σ_d∈Dd) = λΣ_g∈Gg for some integer λ. We discuss some general properties of polynomial addition sets. The relation between polynomial addition sets and polynomial Cayley digraphs is studied and, in particular, some new results on Cayley xⁿ-digraphs and strongly regular Cayley graphs are obtained. Finally, a complete list of polynomial addition sets with certain restrictions on parameters is given.     

Some sufficient conditions for the existence of kernels in infinite digraphs

A kernel N of a digraph D is an independent set of vertices of D such that for every w∈V(D)−N there exists an arc from w to N. If every induced subdigraph of D has a kernel, D is said to be a kernel perfect digraph. D is called a critical kernel imperfect digraph when D has no kernel but every proper induced subdigraph of D has a kernel. If F is a set of arcs of D, a semikernel modulo F of D is an independent set of vertices S of D such that for every z∈V(D)−S for which there exists an (S,z)-arc of D−F, there also exists an (z,S)-arc in D. In this work we show sufficient conditions for an infinite digraph to be a kernel perfect digraph, in terms of semikernel modulo F. As a consequence it is proved that symmetric infinite digraphs and bipartite infinite digraphs are kernel perfect digraphs. Also we give sufficient conditions for the following classes of infinite digraphs to be kernel perfect digraphs: transitive digraphs, quasi-transitive digraphs, right (or left)-pretransitive digraphs, the union of two right (or left)-pretransitive digraphs, the union of a right-pretransitive digraph with a left-pretransitive digraph, the union of two transitive digraphs, locally semicomplete digraphs and outward locally finite digraphs.     

On a Conjecture on Directed Cycles in a Directed Bipartite Graph

Let D = (V ₁, V ₂; A) be a directed bipartite graph with |V ₁| = |V ₂| = n ≥ 2. Suppose that d _D (x) + d _D (y) ≥ 3n for all x ∈ V ₁ and y ∈ V ₂. Then, with one exception, D contains two vertex-disjoint directed cycles of lengths 2n ₁ and 2n ₂, respectively, for any positive integer partition n = n ₁ + n ₂. This proves a conjecture proposed in [9].     

Ordered and Canonical Ramsey Numbers of Stars

A canonical version of Ramsey’s Theorem proved by Erdös and Rado, implies that given any acyclic digraph D, there exists a least integer ρ _c (D) = n, such that every arc colouring (with an arbitrary number of colours) of the transitive tournament TT _n contains a canonically coloured D (in the sense of Erdös-Rado). It follows that if P _m is a directed path and D is an acyclic digraph, then there exists a least integer ρ_*(P _m , D) = n such that every arc coloring of TT _n , with an arbitrary number of colours, contains either a P _m with no two arcs of the same colour or a monochromatic D. Recently, Lefmann, Rödl and Thomas [4], Lefmann and Rödl [5] have studied the numbers ρ_*(P _n , P _m ) and ρ_*(P _n , TT _m ). In this paper we find ρ_*(P _n , S _m ), where S _m is the out-star and give bounds for ρ _c (S _{m, n} ) where S _{m, n} is the directed star with m in-arcs and n out-arcs at the centre.     

On majorization and Schur products

Suppose A, D₁,…,D_m are n × n matrices where A is self-adjoint, and let $\text{X = Σ}{}^{\mathrm{m}}{}_{\mathrm{k\; =\; 1}}\text{D}{}_{\mathrm{k}}\text{AD}{}^1{}_{\mathrm{k}}$. It is shown that if $\text{ΣD}{}_{\mathrm{k}}\text{D}{}^1{}_{\mathrm{k}}\text{= ΣD}{}^1{}_{\mathrm{k}}\text{D}{}_{\mathrm{k}}\text{= I}$, then the spectrum of X is majorized by the spectrum of A. In general, without assuming any condition on D₁,…,D_m, a result is obtained in terms of weak majorization. If each D_k is a diagonal matrix, then X is equal to the Schur (entrywise) product of A with a positive semidefinite matrix. Thus the results are applicable to spectra of Schur products of positive semidefinite matrices. If A, B are self-adjoint with B positive semidefinite and if b_ii = 1 for each i, it follows that the spectrum of the Schur product of A and B is majorized by that of A. A stronger version of a conjecture due to Marshall and Olkin is also proved.     

Distinguishing labeling of group actions

Suppose Γ is a group acting on a set X. An r-labeling f:X→{1,2,…,r} of X is distinguishing (with respect to Γ) if the only label preserving permutation of X in Γ is the identity. The distinguishing number, D_Γ(X), of the action of Γ on X is the minimum r for which there is an r-labeling which is distinguishing. This paper investigates the relation between the cardinality of a set X and the distinguishing numbers of group actions on X. For a positive integer n, let D(n) be the set of distinguishing numbers of transitive group actions on a set X of cardinality n, i.e., D(n)={D_Γ(X):|X|=n and Γ acts transitively on X}. We prove that . Then we consider the problem of an arbitrary fixed group Γ acting on a large set. We prove that if for any action of Γ on a set Y, for each proper normal subgroup H of Γ, D_H(Y)≤2, then there is an integer n such that for any set X with |X|≥n, for any action of Γ on X with no fixed points, D_Γ(X)≤2.     

On diophantine equations of the form {({\boldsymbol x}-{\boldsymbol a}_{\bf 1})({\boldsymbol x}-{\boldsymbol a}_{\bf 2}) \ldots ({\boldsymbol x}-{\boldsymbol a}_{\boldsymbol k}) + {\boldsymbol r} = {\boldsymbol y}^{ \boldsymbol n}}

Erd?s and Selfridge [3] proved that a product of consecutive integers can never be a perfect power. That is, the equation x(x?+?1)(x?+?2)...(x?+?(m???1))?=?y ⁿ has no solutions in positive integers x,m,n where m, n?>?1 and y?∈?Q. We consider the equation $$ (x-a_1)(x-a_2) \ldots (x-a_k) + r = y^n $$ where 0?≤?a ₁?<?a ₂?<???<?a _k are integers and, with r?∈?Q, n?≥?3 and we prove a finiteness theorem for the number of solutions x in Z, y in Q. Following that, we show that, more interestingly, for every nonzero integer n?>?2 and for any nonzero integer r which is not a perfect n-th power for which the equation admits solutions, k is bounded by an effective bound.     

The extension of the D(?k 2)-pair {k 2,k 2 + 1}

Let n be a nonzero integer. A set of m distinct positive integers is called a D(n)-m-tuple if the product of any two of them increased by n is a perfect square. Let k be a positive integer. In this paper, we show that if {k ², k ²+1, c, d} is a D(?k ²)-quadruple with c < d, then c = 1 and d = 4k ²+1. This extends the work of the first author [20] and that of Dujella [4].     

Augmentation quotients for burnside rings of generalized dihedral groups

Let H be a finite abelian group of odd order, D be its generalized dihedral group, i.e., the semidirect product of C₂ acting on H by inverting elements, where C₂ is the cyclic group of order two. Let Ω (D) be the Burnside ring of D, Δ(D) be the augmentation ideal of Ω (D). Denote by Δⁿ(D) and Q_n(D) the nth power of Δ(D) and the nth consecutive quotient group Δⁿ(D)/Δⁿ⁺¹(D), respectively. This paper provides an explicit Z-basis for Δⁿ(D) and determines the isomorphism class of Q_n(D) for each positive integer n.