On super-edge-connected digraphs and bipartite digraphs

A maximally edge-connected digraph is called super-λ if every minimum edge disconnecting set is trivial, i.e., it consists of the edges adjacent to or from a given vertex. In this paper sufficient conditions for a digraph to be super-λ are presented in terms of parameters such as diameter and minimum degree. Similar results are also given for bipartite digraphs. As a corollary, some characterizations of super-λ graphs and bipartite graphs are obtained. © 1929 John Wiley & Sons, Inc.     

Degree sequence conditions for maximally edge-connected and super-edge-connected digraphs depending on the clique number

Let $D$ be a finite and simple digraph with vertex set $V\left(D\right)$. For a vertex $v\in V\left(D\right)$, the degree $d\left(v\right)$ of $v$ is defined as the minimum value of its out-degree $d^{+}\left(v\right)$ and its in-degree $d^{?}\left(v\right)$. If $D$ is a graph or a digraph with minimum degree $\delta$ and edge-connectivity $\lambda$, then $\lambda \le \delta$. A graph or a digraph is maximally edge-connected if $\lambda =\delta$. A graph or a digraph is called super-edge-connected if every minimum edge-cut consists of edges adjacent to or from a vertex of minimum degree.In this note we present degree sequence conditions for maximally edge-connected and super-edge-connected digraphs depending on the clique number of the underlying graph.     

New sufficient conditions for bipancyclicity of balanced bipartite digraphs

The main results provide sufficient conditions for balanced bipartite digraphs to be bipancyclic. These are analogues to well-known results on pancyclic digraphs.     

Supereulerian bipartite digraphs

A digraph D is supereulerian if D has a spanning closed ditrail. Bang‐Jensen and Thomassé conjectured that if the arc‐strong connectivity of a digraph D is not less than the independence number , then D is supereulerian. A digraph is bipartite if its underlying graph is bipartite. Let be the size of a maximum matching of D. We prove that if D is a bipartite digraph satisfying , then D is supereulerian. Consequently, every bipartite digraph D satisfying is supereulerian. The bound of our main result is best possible.     

On Moore bipartite digraphs

In the context of the degree/diameter problem for directed graphs, it is known that the number of vertices of a strongly connected bipartite digraph satisfies a Moore‐like bound in terms of its diameter k and the maximum out‐degrees (d₁, d₂) of its partite sets of vertices. It has been proved that, when d₁d₂ > 1, the digraphs attaining such a bound, called Moore bipartite digraphs, only exist when 2 ≤ k ≤ 4. This paper deals with the problem of their enumeration. In this context, using the theory of circulant matrices and the so‐called De Bruijn near‐factorizations of cyclic groups, we present some new constructions of Moore bipartite digraphs of diameter three and composite out‐degrees. By applying the iterated line digraph technique, such constructions also provide new families of dense bipartite digraphs with arbitrary diameter. Moreover, we show that the line digraph structure is inherent in any Moore bipartite digraph G of diameter k = 4, which means that G = L G′, where G′ is a Moore bipartite digraph of diameter k = 3. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 171–187, 2003     

Path number of bipartite digraphs

In this paper it is proved that the path number of the complete symmetric bipartite digraph on n and n vertices is n + 1, thereby establishing a conjecture of Chein.     

Longest paths in bipartite digraphs

In this paper we give a sufficient condition on the degrees of the vertices of a digraph to insure the existence of a path of length greater than or equal to a given value, when the digraph is bipartite and when the digraph is dipartite and oriented. These conditions are shown to be best possible.     

Neighborhood hypergraphs of bipartite graphs

Matrix symmetrization and several related problems have an extensive literature, with a recurring ambiguity regarding their complexity and relation to graph isomorphism. We present a short survey of these problems to clarify their status. In particular, we recall results from the literature showing that matrix symmetrization is in fact NP‐hard; furthermore, it is equivalent with the problem of recognizing whether a hypergraph can be realized as the neighborhood hypergraph of a graph. There are several variants of the latter problem corresponding to the concepts of open, closed, or mixed neighborhoods. While all these variants are NP‐hard in general, one of them restricted to the bipartite graphs is known to be equivalent with graph isomorphism. Extending this result, we consider several other variants of the bipartite neighborhood recognition problem and show that they all are either polynomial‐time solvable, or equivalent with graph isomorphism. Also, we study uniqueness of neighborhood realizations of hypergraphs and show that, in general, for all variants of the problem, a realization may be not unique. However, we prove uniqueness in two special cases: for the open and closed neighborhood hypergraphs of the bipartite graphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 69–95, 2008     

Orientations of Hamiltonian cycles in bipartite digraphs

The main result of the paper is the following Theorem. Let D=(X,Y,A) be a bipartite, balanced digraph of order 2n and size at least 2n²–2n+3. Then D contains an almost symmetric Hamiltonian cycle (i.e. a Hamiltonian cycle in which at least 2n–1 arcs are symmetric edges), unless D has a vertex which is not incident to any symmetric edge of D.This theorem implies a number of results on cycles in bipartite, balanced digraphs, including some recent results of N. Chakroun, M. Manoussakis and Y. Manoussakis.     

Acyclically pushable bipartite permutation digraphs: An algorithm

Given a digraph D=(V,A) and an X⊆V, D^X denotes the digraph obtained from D by reversing those arcs with exactly one end in X. A digraph D is called acyclically pushable when there exists an X⊆V such that D^X is acyclic. Huang, MacGillivray and Yeo have recently characterized, in terms of two excluded induced subgraphs on 7 and 8 nodes, those bipartite permutation digraphs which are acyclically pushable. We give an algorithmic proof of their result. Our proof delivers an O(m²) time algorithm to decide whether a bipartite permutation digraph is acyclically pushable and, if yes, to find a set X such that D^X is acyclic. (Huang, MacGillivray and Yeo's result clearly implies an O(n⁸) time algorithm to decide but the polynomiality of constructing X was still open.)We define a strongly acyclic digraph as a digraph D such that D^X is acyclic for every X. We show how a result of Conforti et al [Balanced cycles and holes in bipartite graphs, Discrete Math. 199 (1-3) (1999) 27-33] can be essentially regarded as a characterization of strongly acyclic digraphs and also provides linear time algorithms to find a strongly acyclic orientation of an undirected graph, if one exists. Besides revealing this connection, we add simplicity to the structural and algorithmic results first given in Conforti et al [Balanced cycles and holes in bipartite graphs, Discrete Math. 199 (1-3) (1999) 27-33]. In particular, we avoid decomposing the graph into triconnected components.We give an alternate proof of a theorem of Huang, MacGillivray and Wood characterizing acyclically pushable bipartite tournaments. Our proof leads to a linear time algorithm which, given a bipartite tournament as input, either returns a set X such that D^X is acyclic or a proof that D is not acyclically pushable.     

Configurational conditions and digraphs

Configurational conditions (Schließungsaussagen) of a noncommutative space will be developped from pairs (, ) of digraphs where is a partial digraph of . In this way we obtain an extensive generalization of Pfalzgraf 's q-simplex-conditions Sim_q.In Memoriam Hans Zassenhaus     

Minimum degree thresholds for bipartite graph tiling

Given a bipartite graph H and a positive integer n such that v(H) divides 2n, we define the minimum degree threshold for bipartite H‐tiling, δ₂(n, H), as the smallest integer k such that every bipartite graph G with n vertices in each partition and minimum degree δ(G)≥k contains a spanning subgraph consisting of vertex‐disjoint copies of H. Zhao, Hladký‐Schacht, Czygrinow‐DeBiasio determined δ₂(n, K_{s, t}) exactly for all s?t and suffi‐ciently large n. In this article we determine δ₂(n, H), up to an additive constant, for all bipartite H and sufficiently large n. Additionally, we give a corresponding minimum degree threshold to guarantee that G has an H‐tiling missing only a constant number of vertices. Our δ₂(n, H) depends on either the chromatic number χ(H) or the critical chromatic number χ_cr(H), while the threshold for the almost perfect tiling only depends on χ_cr(H). These results can be viewed as bipartite analogs to the results of Kuhn and Osthus [Combinatorica 29 (2009), 65–107] and of Shokoufandeh and Zhao [Rand Struc Alg 23 (2003), 180–205]. © 2011 Wiley Periodicals, Inc. J Graph Theory     

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.     

Planar bipartite biregular degree sequences

A pair of sequences of natural numbers is called planar if there exists a simple, bipartite, planar graph for which the given sequences are the degree sequences of its parts. For a pair to be planar, the sums of the sequences have to be equal and Euler’s inequality must be satisfied. Pairs that verify these two necessary conditions are called admissible. We prove that a pair of constant sequences is planar if and only if it is admissible (such pairs can be easily listed) and is different from $\left(3^5\right|3^5)$ and $\left(3^{25}\right|5^{15})$.     

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.     

Neighborhood degree lists of graphs

The neighborhood degree list (NDL) is a graph invariant that refines information given by the degree sequence and joint degree matrix of a graph and is useful in distinguishing graphs having the same degree sequence. We show that the space of realizations of an NDL is connected via a switching operation. We then determine the NDLs that have a unique realization by a labeled graph; the characterization ties these NDLs and their realizations to the threshold graphs and difference graphs.