Maximum path digraphs

In this paper we solve the following problem: Given an integer m, construct a digraph with exactly one source s, exactly one sink t and exactly m arcs such that the number of paths from s to t is maximized.     

Linear arboricity of regular digraphs

A linear directed forest is a directed graph in which every component is a directed path.The linear arboricity la(D) of a digraph D is the minimum number of linear directed forests in D whose union covers all arcs of D. For every d-regular digraph D, Nakayama and P′eroche conjecture that la(D) = d + 1. In this paper, we consider the linear arboricity for complete symmetric digraphs,regular digraphs with high directed girth and random regular digraphs and we improve some wellknown results. Moreover, we propose a more precise conjecture about the linear arboricity for regular digraphs.     

MAXIMUM CYCLE-MEANS OF WEIGHTED DIGRAPHS

Abstract. Computing the maximum cycle-mean of a weighted digraph is relevant to a number of applications, and combinatorial algorlthnls of complexity 0(n) are known.We present a new algorithm, with computational evidence to suggest an expected run-time growth rate below O(n^3）     

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     

Finite digraphs with given regular automorphism groups

With five exceptions, every finite regular permutation group occurs as the automorphism group of a digraph.One of the corollaries: given a finite groupG of ordern, there is a commutative semigroupS of order 2n+2 such that AutSG. The problem whether a latticeL of order Cn with AutLG exists (for some constantC), remains open.     

ON CIRCULANT DIGRAPHS WITH REGULAR AUTOMORPHISM GROUPS

Abstract. We prove that the cyclic group Zn(n≥3) has a k-regular digraph regular     

On spectra of doubly regular asymmetric digraphs ofRH-type

Spectra of doubly regular asymmetric digraph of regular Hadamard type are determined.     

Enumeration and generation of a class of regular digraphs

We study the class of directed graphs that have indegree = outdegree = 2 at every vertex. These digraphs can be decomposed uniquely into “alternating cycles”, we use this decomposition to present efficient techniques for counting and generating them. The number (up to isomorphism) of these digraphs and the number of connected ones on up to 20 vertices have been computed and are presented.     

Maximum genus of regular graphs

This paper provides tight lower bounds on the maximum genus of a regular graph in terms of its cycle rank. The main tool is a relatively simple theorem that relates lower bounds with the existence (or non-existence) of induced subgraphs with odd cycle rank that are separated from the rest of the graph by cuts of size at most three. Lower bounds on the maximum genus are obtained by bounding from below the size of these odd subgraphs. As a special case, upper-embeddability of a class of graphs is caused by an absence of such subgraphs. A well-known theorem stating that every 4-edge-connected graph is upper-embeddable is a straightforward corollary of the employed method.     

Minimum orders of eulerian oriented digraphs with given diameter

A digraph D is oriented if it does not contain 2-cycles.If an oriented digraph D has a directed eulerian path,it is an oriented eulerian digraph.In this paper,when an oriented eulerian digraph D has minimum out-degree 2 and a diameter d,we find the minimum order of D.In addition,when D is 2-regular with diameter 4m(m ≥ 2),we classify the extremal cases.     

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     

Openly disjoint circuits through a vertex in regular digraphs

In 1985, Thomassen [14] constructed for every positive integer r, finite digraphs D of minimum degree δ(D)=r which do not contain a vertex x lying on three openly disjoint circuits, i.e. circuits which have pairwise exactly x in common. In 2005, Seymour [11] posed the question, whether an r-regular digraph contains a vertex x such that there are r openly disjoint circuits through x. This is true for r≤3, but does not hold for r≥8. But perhaps, in contrast to the minimum degree, a high regularity degree suffices for the existence of a vertex lying on r openly disjoint circuits also for r≥4. After a survey of these problems, we will show that every r-regular digraph with r≥7 has a vertex which lies on 4 openly disjoint circuits.     

The diameter of randomly perturbed digraphs and some applications

The central observation of this paper is that if εn random arcs are added to any n‐node strongly connected digraph with bounded degree then the resulting graph has diameter 𝒪(lnn) with high probability. We apply this to smoothed analysis of algorithms and property testing. Smoothed Analysis: Recognizing strongly connected digraphs is a basic computational task in graph theory. Even for digraphs with bounded degree, it is NL‐complete. By XORing an arbitrary bounded degree digraph with a sparse random digraph R ∼ 𝔻_n,ε/n we obtain a “smoothed” instance. We show that, with high probability, a log‐space algorithm will correctly determine if a smoothed instance is strongly connected. We also show that if NL ⫅̸ almost‐L then no heuristic can recognize similarly perturbed instances of (s,t)‐connectivity. Property Testing: A digraph is called k‐linked if, for every choice of 2k distinct vertices s₁,…,s_k,t₁,…,t_k, the graph contains k vertex disjoint paths joining s_r to t_r for r = 1,…,k. Recognizing k‐linked digraphs is NP‐complete for k ≥ 2. We describe a polynomial time algorithm for bounded degree digraphs, which accepts k‐linked graphs with high probability, and rejects all graphs that are at least εn arcs away from being k‐linked. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Maximum matchings in regular graphs

It was conjectured by Mkrtchyan, Petrosyan and Vardanyan that every graph $G$ with $\Delta \left(G\right)?\delta \left(G\right)\le 1$ has a maximum matching $M$ such that any two $M$-unsaturated vertices do not share a neighbor. The results obtained in Mkrtchyan et al. (2010), Petrosyan (2014) and Picouleau (2010) leave the conjecture unknown only for $k$-regular graphs with $4\le k\le 6$. All counterexamples for $k$-regular graphs $(k\ge 7)$ given in Petrosyan (2014) have multiple edges. In this paper, we confirm the conjecture for all $k$-regular simple graphs and also $k$-regular multigraphs with $k\le 4$.     

The diameter of random regular graphs

We give asymptotic upper and lower bounds for the diameter of almost everyr-regular graph onn vertices (n → ∞).     

Superconnectivity of regular graphs with small diameter

A graph is superconnected, for short super-κ, if all minimum vertex-cuts consist of the vertices adjacent with one vertex. In this paper we prove for any r-regular graph of diameter D and odd girth g that if D≤g−2, then the graph is super-κ when g≥5 and a complete graph otherwise.