On 3-restricted edge connectivity of undirected binary Kautz graphs

An edge cut of a connected graph is m-restricted if its removal leaves every component having order at least m. The size of minimum m-restricted edge cuts of a graph G is called its m-restricted edge connectivity. It is known that when m≤4, networks with maximal m-restricted edge connectivity are most locally reliable. The undirected binary Kautz graph UK(2,n) is proved to be maximal 2- and 3-restricted edge connected when n≥3 in this work. Furthermore, every minimum 2-restricted edge cut disconnects this graph into two components, one of which being an isolated edge.     

Short proofs of classical theorems

We give proofs of Ore's theorem on Hamilton circuits, Brooks' theorem on vertex coloring, and Vizing's theorem on edge coloring, as well as the Chvátal-Lovász theorem on semi-kernels, a theorem of Lu on spanning arborescences of tournaments, and a theorem of Gutin on diameters of orientations of graphs. These proofs, while not radically different from existing ones, are perhaps simpler and more natural. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 159–165, 2003     

A Brauerian representation of split preorders

Split preorders are preordering relations on a domain whose composition is defined in a particular way by splitting the domain into two disjoint subsets. These relations and the associated composition arise in categorial proof theory in connection with coherence theorems. Here split preorders are represented isomorphically in the category whose arrows are binary relations and whose composition is defined in the usual way. This representation is related to a classical result of representation theory due to Richard Brauer. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Supereulerian Digraphs with Large Arc‐Strong Connectivity

Let D be a digraph and let be the arc‐strong connectivity of D, and be the size of a maximum matching of D. We proved that if , then D has a spanning eulerian subdigraph.     

Rainbow Arborescence in Random Digraphs

We consider the Erd?s–Rényi random directed graph process, which is a stochastic process that starts with n vertices and no edges, and at each step adds one new directed edge chosen uniformly at random from the set of missing edges. Let be a graph with m edges obtained after m steps of this process. Each edge () of independently chooses a color, taken uniformly at random from a given set of colors. We stop the process prematurely at time M when the following two events hold: has at most one vertex that has in‐degree zero and there are at least distinct colors introduced ( if at the time when all edges are present there are still less than colors introduced; however, this does not happen asymptotically almost surely). The question addressed in this article is whether has a rainbow arborescence (i.e. a directed, rooted tree on n vertices in which all edges point away from the root and all the edges are different colors). Clearly, both properties are necessary for the desired tree to exist and we show that, asymptotically almost surely, the answer to this question is “yes.”     

Acyclic systems of representatives and acyclic colorings of digraphs

A natural digraph analog of the graph theoretic concept of “an independent set” is that of “an acyclic set of vertices,” namely a set not spanning a directed cycle. By this token, an analog of the notion of coloring of a graph is that of decomposition of a digraph into acyclic sets. We extend some known results on independent sets and colorings in graphs to acyclic sets and acyclic colorings of digraphs. In particular, we prove bounds on the topological connectivity of the complex of acyclic sets, and using them we prove sufficient conditions for the existence of acyclic systems of representatives of a system of sets of vertices. These bounds generalize a result of Tardos and Szabó. We prove a fractional version of a strong‐acyclic‐coloring conjecture for digraphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 177–189, 2008     

Nonseparating trees in 2-connected graphs and oriented trees in strongly connected digraphs

Mader (2010) conjectured that for every positive integer $k$ and every finite tree $T$ with order $m$, every $k$-connected, finite graph $G$ with $\delta \left(G\right)\ge \lfloor \frac{3}{2}k\rfloor +m-1$ contains a subtree $T^{\prime }$ isomorphic to $T$ such that $G-V\left(T^{\prime }\right)$ is $k$-connected. The conjecture has been verified for paths, trees when $k=1$, and stars or double-stars when $k=2$. In this paper we verify the conjecture for two classes of trees when $k=2$.For digraphs, Mader (2012) conjectured that every $k$-connected digraph $D$ with minimum semi-degree $\delta \left(D\right)=min\{{\delta }^{+}\left(D\right),{\delta }^{-}\left(D\right)\}\ge 2k+m-1$ for a positive integer $m$ has a dipath $P$ of order $m$ with $\kappa (D-V\left(P\right))\ge k$. The conjecture has only been verified for the dipath with $m=1$, and the dipath with $m=2$ and $k=1$. In this paper, we prove that every strongly connected digraph with minimum semi-degree $\delta \left(D\right)=min\{{\delta }^{+}\left(D\right),{\delta }^{-}\left(D\right)\}\ge m+1$ contains an oriented tree $T$ isomorphic to some given oriented stars or double-stars with order $m$ such that $D-V\left(T\right)$ is still strongly connected.     

Locally-finite connected-homogeneous digraphs

A digraph is connected-homogeneous if any isomorphism between finite connected induced subdigraphs extends to an automorphism of the digraph. We consider locally-finite connected-homogeneous digraphs with more than one end. In the case that the digraph embeds a triangle we give a complete classification, obtaining a family of tree-like graphs constructed by gluing together directed triangles. In the triangle-free case we show that these digraphs are highly arc-transitive. We give a classification in the two-ended case, showing that all examples arise from a simple construction given by gluing along a directed line copies of some fixed finite directed complete bipartite graph. When the digraph has infinitely many ends we show that the descendants of a vertex form a tree, and the reachability graph (which is one of the basic building blocks of the digraph) is one of: an even cycle, a complete bipartite graph, the complement of a perfect matching, or an infinite semiregular tree. We give examples showing that each of these possibilities is realised as the reachability graph of some connected-homogeneous digraph, and in the process we obtain a new family of highly arc-transitive digraphs without property Z.     

Properties of digraphs connected with some congruence relations

The paper extends the results given by M. Křížek and L. Somer, On a connection of number theory with graph theory, Czech. Math. J. 54 (129) (2004), 465–485 (see [5]). For each positive integer n define a digraph Γ(n) whose set of vertices is the set H = {0, 1, ..., n − 1} and for which there is a directed edge from a ∈ H to b ∈ H if a ³ ≡ b (mod n). The properties of such digraphs are considered. The necessary and the sufficient condition for the symmetry of a digraph Γ(n) is proved. The formula for the number of fixed points of Γ(n) is established. Moreover, some connection of the length of cycles with the Carmichael λ-function is presented.      

Connected -tuple twin domination in de Bruijn and Kautz digraphs

For a digraph G, a k-tuple twin dominating set D of G for some fixed k≥1 is a set of vertices such that every vertex is adjacent to at least k vertices in D, and also every vertex is adjacent from at least k vertices in D. If the subgraph of G induced by D is strongly connected, then D is called a connected k-tuple twin dominating set of G. In this paper, we give constructions of minimal connected k-tuple twin dominating sets for de Bruijn digraphs and Kautz digraphs.