Travel groupoids

In this paper, by a travel groupoid is meant an ordered pair (V, *) such that V is a nonempty set and * is a binary operation on V satisfying the following two conditions for all u, v ∈ V:

Characterizing directed path graphs by forbidden asteroids

An asteroidal triple is a stable set of three vertices such that each pair is connected by a path avoiding the neighborhood of the third vertex. Asteroidal triples play a central role in a classical characterization of interval graphs by Lekkerkerker and Boland. Their result says that a chordal graph is an interval graph if and only if it does not contain an asteroidal triple. In this paper, we prove an analogous theorem for directed path graphs which are the intersection graphs of directed paths in a directed tree. For this purpose, we introduce the notion of a special connection. Two non‐adjacent vertices are linked by a special connection if either they have a common neighbor or they are the endpoints of two vertex‐disjoint chordless paths satisfying certain conditions. A special asteroidal triple is an asteroidal triple such that each pair is linked by a special connection. We prove that a chordal graph is a directed path graph if and only if it does not contain a special asteroidal triple. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:103‐112, 2011     

Groupoid cohomology and extensions

We show that Haefliger's cohomology for étale groupoids, Moore's cohomology for locally compact groups and the Brauer group of a locally compact groupoid are all particular cases of sheaf (or Cech) cohomology for topological simplicial spaces.

     

On expansions and extensions of powerful digraphs

We study the problem of expanding and extending the structure of a stable powerful digraph to the structure of a stable Ehrenfeucht theory. We define the concepts of type unstability and type strict order property. We establish the presence of the type strict order property for every acyclic graph structure with an infinite chain. The simplest form of expansion of a powerful digraph to the structure of an Ehrenfeucht theory is the expansion with a 1-inessential ordered coloring and locally graph ?-definable many-placed relations, which enable us to mutually realize nonprincipal types; we prove that this expansion is incapable of keeping the structure in the class of stable structures, and moreover, by the type strict order property it generates the first-order definable strict order property. We define the concept of a locally countably categorical theory (LCC theory) and prove that given the list p ₁(x), ..., p _n (x) of all nonprincipal 1-types in an LCC theory, if all types r(x ₁, ..., x _m ) containing \(p_{i_1 } \) (x ₁) ∪ ... ∪ \(p_{i_m } \)(x _m ) are dominated by some type q then q is a powerful type.     

Discrepancy properties for random regular digraphs

For the uniform random regular directed graph we prove concentration inequalities for (1) codegrees and (2) the number of edges passing from one set of vertices to another. As a consequence, we can deduce discrepancy properties for the distribution of edges essentially matching results for Erd?s–Rényi digraphs obtained from Chernoff‐type bounds. The proofs make use of the method of exchangeable pairs, developed for concentration of measure by Chatterjee in (Chatterjee, Probab Theory and Relat Fields 138 (2007), 305–321). Exchangeable pairs are constructed using two involutions on the set of regular digraphs: a well‐known “simple switching” operation, as well as a novel “reflection” operation. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 23–58, 2017     

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     

Characterization of digraphs with equal domination graphs and underlying graphs

A domination graph of a digraph D, dom(D), is created using the vertex set of D and edge {u,v}∈E[dom(D)] whenever (u,z)∈A(D) or (v,z)∈A(D) for every other vertex z∈V(D). The underlying graph of a digraph D, UG(D), is the graph for which D is a biorientation. We completely characterize digraphs whose underlying graphs are identical to their domination graphs, UG(D)=dom(D). The maximum and minimum number of single arcs in these digraphs, and their characteristics, is given.     

Hamiltonian cycles in -circulant digraphs

Let D be the circulant digraph with n vertices and connection set {2,3,c}. (Assume D is loopless and has outdegree 3.) Work of S. C. Locke and D. Witte implies that if n is a multiple of 6, c{(n/2)+2,(n/2)+3}, and c is even, then D does not have a hamiltonian cycle. For all other cases, we construct a hamiltonian cycle in D.     

有向图(→C)n×(→P)2的优美性

研究了有向图(→C)n×(→P)2的优美性,利用搜索图的标号的算法与数学证明相结合的方法,证实了有向图(→C)n×(→P)2为优美图,其中n为任意正整数.     

Hamiltonicity and reversing arcs in digraphs

In this paper we introduce a new hamiltonian-like property of graphs. A graph G is said to be cyclable if for each orientation D of G there is a set S of vertices such that reversing all the arcs of D with one end in S results in a hamiltonian digraph. We characterize cyclable complete multipartite graphs and prove that the fourth power of any connected graph G with at least five vertices is cyclable. If, moreover, G is two-connected then its cube is cyclable. These results are shown to be best possible in a sense. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 13–30, 1998     

Cayley color graphs of inverse semigroups and groupoids

The notion of Cayley color graphs of groups is generalized to inverse semigroups and groupoids. The set of partial automorphisms of the Cayley color graph of an inverse semigroup or a groupoid is isomorphic to the original inverse semigroup or groupoid. The groupoid of color permuting partial automorphisms of the Cayley color graph of a transitive groupoid is isomorphic to the original groupoid.     

Cayley digraphs and lexicographic product

In this paper, we prove that a Cayley digraph Γ = Cay(G, S) is a nontrivial lexicographical product if and only if there is a nontrivial subgroup H of G such that S∖H is a union of some double cosets of H in G.      

Large butterfly Cayley graphs and digraphs

We present families of large undirected and directed Cayley graphs whose construction is related to butterfly networks. One approach yields, for every large $k$ and for values of $d$ taken from a large interval, the largest known Cayley graphs and digraphs of diameter $k$ and degree $d$. Another method yields, for sufficiently large $k$ and infinitely many values of $d$, Cayley graphs and digraphs of diameter $k$ and degree $d$ whose order is exponentially larger in $k$ than any previously constructed. In the directed case, these are within a linear factor in $k$ of the Moore bound.     

Asymptotic enumeration of strongly connected digraphs by vertices and edges

We derive an asymptotic formula for the number of strongly connected digraphs with n vertices and m arcs (directed edges), valid for m ‐ n →∞ as n →∞ provided m = O(nlog n). This fills the gap between Wright's results which apply to m = n + O (1) , and the long‐known threshold for m, above which a random digraph with n vertices and m arcs is likely to be strongly connected. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Uniqueness of form extensions and domination of semigroups

In this article, we study uniqueness of form extensions in a rather general setting. The method is based on the theory of ordered Hilbert spaces and the concept of domination of semigroups. Our main abstract result transfers uniqueness of form extension of a dominating form to that of a dominated form. This result can be applied to a multitude of examples including various magnetic Schrödinger forms on graphs and on manifolds.     

Highly edge‐connected detachments of graphs and digraphs

Let G = (V,E) be a graph or digraph and r : V → Z₊. An r‐detachment of G is a graph H obtained by ‘splitting’ each vertex ν ∈ V into r(ν) vertices. The vertices ν₁,…,ν_r(ν) obtained by splitting ν are called the pieces of ν in H. Every edge uν ∈ E corresponds to an edge of H connecting some piece of u to some piece of ν. Crispin Nash‐Williams 9 gave necessary and sufficient conditions for a graph to have a k‐edge‐connected r‐detachment. He also solved the version where the degrees of all the pieces are specified. In this paper, we solve the same problems for directed graphs. We also give a simple and self‐contained new proof for the undirected result. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 67–77, 2003     

正圆有向图中的弧不相交的Hamilton路和圈

2012年,Bang-Jensen和Huang(J.Combin.Theory Ser.B.2012,102:701-714)证明了2-弧强的局部半完全有向图可以分解为两个弧不相交的强连通生成子图当且仅当D不是偶圈的二次幂,并提出了任意3-强的局部竞赛图中包含两个弧不相交的Hamilton圈的猜想.主要研究正圆有向图中的弧不相交的Hamilton路和Hamilton圈,并证明了任意3-弧强的正圆有向图中包含两个弧不相交的Hamilton圈和任意4-弧强的正圆有向图中包含一个Hamilton圈和两个Hamilton路,使得它们两两弧不相交.由于任意圆有向图一定是正圆有向图,所得结论可以推广到圆有向图中.又由于圆有向图是局部竞赛图的子图类,因此所得结论说明对局部竞赛图的子图类――圆有向图,Bang-Jensen和Huang的猜想成立.     

Degree sequence conditions for maximally edge-connected graphs and digraphs

In this paper we give simple degree sequence conditions for the equality of edge-connectivity and minimum degree of a (di-)graph. One of the conditions implies results by Bollobás, Goldsmith and White, and Xu. Moreover, we give analogue conditions for bipartite (di-)graphs. © 1997 John Wiley & Sons, Inc. J Graph Theory 26:27–34, 1997