Turán theorems and convexity invariants for directed graphs

This paper is motivated by the desire to evaluate certain classical convexity invariants (specifically, the Helly and Radon numbers) in the context of transitive closure of arcs in the complete digraph. To do so, it is necessary to establish several new Turán type results for digraphs and characterize the associated extremal digraphs. In the case of the Radon number, we establish the following analogue for transitive closure in digraphs of Radon's classical convexity theorem [J. Radon, Mengen konvexer Körper, die einer gemeinsamen Punkt enthalten, Math. Ann. 83 (1921) 113-115]: in a complete digraph on n?7 vertices with >n²/4 arcs, it is possible to partition the arc set into two subsets whose transitive closures have an arc in common.     

Fast parallel strong orientation of mixed graphs and related augmentation problems

The strong orientation problem is: Given an undirected graph, G, assign orientations to its edges so that the resulting directed graph is strongly connected. Robbins showed when such an orientation exists. A generalization of this problem is when the input graph is mixed (i.e., contains some directed and some undirected edges). Boesch and Tindell gave necessary and sufficient conditions for a strong orientation to exist in a mixed graph. In this paper we give an NC algorithm for constructing a strong orientation for a given mixed graph after determining if it exists. We also give an NC algorithm for adding a minimum set of arcs to a mixed graph to make it strongly orientable. We give simplified NC algorithms for the following special cases: find minimum augmentations to make a digraph strongly connected and to make an undirected graph bridge-connected. All the algorithms presented run within the time and processor bounds required for computing the transitive closure of a digraph.     

The transitive closure of a random digraph

In a random n-vertex digraph, each arc is present with probability p, independently of the presence or absence of other arcs. We investigate the structure of the strong components of a random digraph and present an algorithm for the construction of the transitive closure of a random digraph. We show that, when n is large and np is equal to a constant c greater than 1, it is very likely that all but one of the strong components are very small, and that the unique large strong component contains about Θ₂n vertices, where Θ is the unique root in [0, 1] of the equation 1 ? x ? e^?ex = 0. Nearly all the vertices outside the large strong component line in strong components of size 1. Provided that the expected degree of a vertex is bounded away from 1, our transitive closure algorithm runs in expected time O(n). for all choices of n and p, the expected execution time of the algorithm is O(w(n) (n log n)^4/3), where w(n) is an arbitrary nondecreasing unbounded function. To circumvent the fact that the size of the transitive closure may be Ω(n²) the algorithm presents the transitive closure in the compact form (A × B)U C, where A and B are sets of vertices, and C is a set of arcs.     

利用关系矩阵求传递闭包的一种方法

介绍了一种利用关系矩阵求有限集合上二元关系的传递闭包的方法 ,该方法简便、实用 .还可用此方法计算有向图的可达性矩阵 .     

About some cyclic properties in digraphs

In this article we are concerned with digraphs in which any two vertices are on a common cycle. For example, we prove that, in a strong digraph of order n and half degrees at least 2 with at least n² ? 5n + 15 arcs, any two vertices are on a common cycle. We also consider related properties and give sufficient conditions on half degrees and the number of arcs to insure these properties. In particular, we show that every digraph of order n with half degrees at least r and with at least n² ? rn + r² arcs is 2-linked.     

分支数≤7时S^2NS有向图的禁用子图刻划

实方阵A称为强符号非异阵（S~2NS阵）,若任一与A符号模式相同的矩阵非异且其逆的符号模式也一致。若一个有向图是某一S~2NS阵对应赋号有向图的基础有向图,称为S~2NS有向图。本文用禁用子图形式给出了分支数≤7时有向图成为S~2NS有向图的刻划,同时部分地解决了[2]和[4]中提出的问题。     

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 Vosperian and Superconnected Vertex-Transitive Digraphs

We investigate the structure of a digraph having a transitive automorphism group where every cutset of minimal cardinality consists of all successors or all predecessors of some vertex. We give a complete characterization of vosperian arc-transitive digraphs. It states that an arc-transitive strongly connected digraph is vosperian if and only if it is irreducible. In particular, this is the case if the degree is coprime with the order of the digraph. We give also a complete characterization of vosperian Cayley digraphs and a complete characterization of irreducible superconnected Cayley digraphs. These two last characterizations extend the corresponding ones in Abelian Cayley digraphs and the ones in the undirected case.     

On extremal weighted digraphs with no heavy paths

Bollobás and Scott proved that if the weighted outdegree of every vertex of an edge-weighted digraph is at least 1, then the digraph contains a (directed) path of weight at least 1. In this note we characterize the extremal weighted digraphs with no heavy paths. Our result extends a corresponding theorem of Bondy and Fan on weighted graphs. We also give examples to show that a result of Bondy and Fan on the existence of heavy paths connecting two given vertices in a 2-connected weighted graph does not extend to 2-connected weighted digraphs.     

Cycle-free partial orders and chordal comparability graphs

This paper studies a number of problems on cycle-free partial orders and chordal comparability graphs. The dimension of a cycle-free partial order is shown to be at most 4. A linear time algorithm is presented for determining whether a chordal directed graph is transitive, which yields an O(n ²) algorithm for recognizing chordal comparability graphs. An algorithm is presented for determining whether the transitive closure of a digraph is a cycle-free partial order in O(n+m _t)time, where m _tis the number of edges in the transitive closure.     

Making choices with a binary relation: Relative choice axioms and transitive closures

This article presents an axiomatic analysis of the best choice decision problem from a reflexive crisp binary relation on a finite set (a digraph). With respect to a transitive digraph, optimality and maximality are usually accepted as the best fitted choice axioms to the intuitive notion of best choice. However, beyond transitivity (resp. acyclicity), optimality and maximality can characterise distinct choice sets (resp. empty sets). Accordingly, different and rather unsatisfying concepts have appeared, such as von Neumann–Morgenstern domination, weak transitive closure and kernels. Here, we investigate a new family of eight choice axioms for digraphs: relative choice axioms. Within choice theory, these axioms generalise top-cycle for tournaments, gocha, getcha and rational top-cycle for complete digraphs. We present their main properties such as existence, uniqueness, idempotence, internal structure, and cross comparison. We then show their strong relationship with optimality and maximality when the latter are not empty. Otherwise, these axioms identify a non-empty choice set and underline conflicts between chosen elements in strict preference circuits. Finally, we exploit the close link between this family and transitive closures to compute choice sets in linear time, followed by a relevant practical application.     

Score sequences in oriented graphs

An oriented graph is a digraph with no symmetric pairs of directed arcs and without loops. The score of a vertexv _i in an oriented graph D is $a_{v_i } $ (or simply a_i) $d_{v_i }^ - $ are the outdegree and indegree, respectively, ofv _i and n is the number of vertices in D. In this paper, we give a new proof of Avery’s theorem and obtain some stronger inequalities for scores in oriented graphs. We also characterize strongly transitive oriented graphs.     

Classification of numerical 3-semigroups by means of L-shapes

We recall L-shapes, which are minimal distance diagrams, related to weighted 2-Cayley digraphs, and we give the number and the relation between minimal distance diagrams related to the same digraph. On the other hand, we consider some classes of numerical semigroups useful in the study of curve singularity. Then, we associate L-shapes to each numerical 3-semigroup and we describe some main invariants of numerical 3-semigroups in terms of their associated L-shapes. Finally, we give a characterization of the parameters of the L-shapes associated with a numerical 3-semigroup in terms of its generators, and we use it to classify the numerical 3-semigroups of interest in curve singularity.     

Spanning Forests of Digraphs and Limiting Probabilities of Markov Chains

A maximum out forest of a digraph is its spanning subgraph that consists of disjoint diverging trees and has the maximum possible number of arcs. For an arbitrary weighted digraph, we consider a matrix of specific weights of maximum out forests and demonstrate how this matrix can be used to get a graph-theoretic interpretation for the limiting probabilities of Markov chains. For a special (nonclassical) correspondence between Markov chains and weighted digraphs, the matrix of Cesáro limiting transition probabilities of any finite homogeneous Markov chain coincides with the normalized matrix of maximum out forests of the corresponding digraphs. This provides a finite (combinatorial) method to calculate the limiting probabilities of Markov chains and thus their stationary distributions. On the other hand, the Markov chain technique provides the proofs to some statements about digraphs.     

A graph theoretic approach to the investigation of system‐environment relationships†

For any empirical structure consisting of a system S and its environment E, there is an associated digraph D whose points and arcs (directed lines) correspond to the elements and relationships of the structure. The arcs of D are thus of four types: (1) internal arcs, which join two points of S; (b) external arcs, which join two points of E; (c) out‐liaisons of S, which join a point of S to one of E; and (d) in‐liaisons of S, which join a point of E to one of S. The boundary of S is defined as the subgraph of D induced by the liaisons of S and corresponds to those elements and relationships of the structure directly involved in transactions between the system and its environment. The basic structural properties of boundaries are then identified, and it is shown how the points of S and E can be stratified according to their distances to (or from) the boundary of S. Next, several results are derived concerning system‐environment relationships in structures whose digraphs are symmetric, transitive, or signed. The concept of convexity is then introduced to deal with a certain kind of segregation of a system relative to its environment. And, finally, it is shown how the adjacency matrix of D can be employed to facilitate the analysis of such structures and the calculation of various indexes of system‐environment relationships.     

Applying mod-k-cuts for solving linear ordering problems

The linear ordering problem consists of finding an ordering of the nodes of the weighted complete digraph on n nodes such that the sum of the weights of the arcs compatible with the ordering is maximized. In this paper, we report about the usefulness of mod-k cuts in a branch-and-cut algorithm for solving linear ordering problems to optimality.      

竞赛图弧色数的上界

有向图的弧色数指的是对有向图的弧进行着色, 使得所有连贯弧着不同颜色所需要的最少颜色数. 在介绍了一些相关结果的基础上, 通过确定顶点数较少的竞赛图弧色数的最大值, 说明了已有弧色数的上界虽然对一般有向图是紧的, 对竞赛图却是可以改进的.     

On the Ferrers dimension of a digraph

The Ferrers dimension of a digraph has been shown to be an extension of the order dimension. By proving a property of (finite) transitive Ferrers digraphs, we give an original proof of this above result and derive Ore's alternative definition of the order dimension. Still, the order dimension is proved to be ‘polynomially equivalent’ to the Ferrers dimension.     

The Area Derivative of a Space-Filling Diagram

The motion of a biomolecule greatly depends on the engulfing solution, which is mostly water. Instead of representing individual water molecules, it is desirable to develop implicit solvent models that nevertheless accurately represent the contribution of the solvent interaction to the motion. In such models, hydrophobicity is expressed as a weighted sum of atomic surface areas. The derivatives of these weighted areas contribute to the force that drives the motion. In this paper we give formulas for the weighted and unweighted area derivatives of a molecule modeled as a space-filling diagram made up of balls in motion. Other than the radii and the centers of the balls, the formulas are given in terms of the sizes of circular arcs of the boundary and edges of the power diagram. We also give inclusion–exclusion formulas for these sizes.     

一种求模糊矩阵传递闭包的基于幂序列单增矩阵构造的新算法

引入幂序列单增模糊矩阵的概念并讨论它的性质, 给出一种基于幂序列单增模糊矩阵构造的求模糊关系矩阵传递闭包的新算法; 并通过与现有的两种传递闭包求解算法的比较分析, 借助实例说明了算法的有效性和简洁性.