The distribution of the domination number of class cover catch digraphs for non-uniform one-dimensional data

For two or more classes of points in R^d with d≥1, the class cover catch digraphs (CCCDs) can be constructed using the relative positions of the points from one class with respect to the points from one or all of the other classes. The CCCDs were introduced by Priebe et al. [C.E. Priebe, J.G. DeVinney, D.J. Marchette, On the distribution of the domination number of random class catch cover digraphs. Statistics and Probability Letters 55 (2001) 239-246] who investigated the case of two classes, X and Y. They calculated the exact (i.e., finite sample) distribution of the domination number of the CCCDs based on X points relative to Y points both of which were uniformly distributed on a bounded interval. We investigate the distribution of the domination number of the CCCDs based on data from non-uniform X points on an interval with end points from Y. Then we extend these calculations for multiple Y points on bounded intervals.     

Extension of one-dimensional proximity regions to higher dimensions

Proximity regions (and maps) are defined based on the relative allocation of points from two or more classes in an area of interest and are used to construct random graphs called proximity catch digraphs (PCDs) which have applications in various fields. The simplest of such maps is the spherical proximity map which gave rise to class cover catch digraph (CCCD) and was applied to pattern classification. In this article, we note some appealing properties of the spherical proximity map in compact intervals on the real line, thereby introduce the mechanism and guidelines for defining new proximity maps in higher dimensions. For non-spherical PCDs, Delaunay tessellation (triangulation in the real plane) is used to partition the region of interest in higher dimensions. We also introduce the auxiliary tools used for the construction of the new proximity maps, as well as some related concepts that will be used in the investigation and comparison of these maps and the resulting PCDs. We provide the distribution of graph invariants, namely, domination number and relative density, of the PCDs and characterize the geometry invariance of the distribution of these graph invariants for uniform data and provide some newly defined proximity maps in higher dimensions as illustrative examples.     

Cliques that are tolerance digraphs

In this paper, we study directed graph versions of tolerance graphs, in particular, the class of totally bounded bitolerance digraphs and several subclasses. When the underlying graph is complete, we prove that the classes of totally bounded bitolerance digraphs and interval catch digraphs are equal, and this implies a polynomial-time recognition algorithm for the former class. In addition, we give examples (whose underlying graphs are complete) to separate every other pair of subclasses, and one of these provides a counterexample to a conjecture of Maehara (1984).     

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.     

Locally semicomplete digraphs: A generalization of tournaments

In this paper we introduce a new class of directed graphs called locally semicomplete digraphs. These are defined to be those digraphs for which the following holds: for every vertex x the vertices dominated by x induce a semicomplete digraph and the vertices that dominate x induce a semicomplete digraph. (A digraph is semicomplete if for any two distinct vertices u and ν, there is at least one arc between them.) This class contains the class of semicomplete digraphs, but is much more general. In fact, the class of underlying graphs of the locally semi-complete digraphs is precisely the class of proper circular-arc graphs (see [13], Theorem 3). We show that many of the classic theorems for tournaments have natural analogues for locally semicomplete digraphs. For example, every locally semicomplete digraph has a directed Hamiltonian path and every strong locally semicomplete digraph has a Hamiltonian cycle. We also consider connectivity properties, domination orientability, and algorithmic aspects of locally semicomplete digraphs. Some of the results on connectivity are new, even when restricted to semicomplete digraphs.     

Biomarker discovery: classification using pooled samples

RNA-sample pooling is sometimes inevitable, but should be avoided in classification tasks like biomarker studies. Our simulation framework investigates a two-class classification study based on gene expression profiles to point out how strong the outcomes of single sample designs differ to those of pooling designs. The results show how the effects of pooling depend on pool size, discriminating pattern, number of informative features and the statistical learning method used (support vector machines with linear and radial kernel, random forest (RF), linear discriminant analysis, powered partial least squares discriminant analysis (PPLS-DA) and partial least squares discriminant analysis (PLS-DA)). As a measure for the pooling effect, we consider prediction error (PE) and the coincidence of important feature sets for classification based on PLS-DA, PPLS-DA and RF. In general, PPLS-DA and PLS-DA show constant PE with increasing pool size and low PE for patterns for which the convex hull of one class is not a cover of the other class. The coincidence of important feature sets is larger for PLS-DA and PPLS-DA as it is for RF. RF shows the best results for patterns in which the convex hull of one class is a cover of the other class, but these depend strongly on the pool size. We complete the PE results with experimental data which we pool artificially. The PE of PPLS-DA and PLS-DA are again least influenced by pooling and are low. Additionally, we show under which assumption the PLS-DA loading weights, as a measure for importance of features regarding classification, are equal for the different designs.     

Different capacities of a digraph

Sperner product is the natural generalization of co-normal product to digraphs. For every class of digraphs closed under Sperner product, the cardinality of the largest subgraph from the given class, contained as an induced subgraph in the co-normal powers of a graphG, has an exponential growth. The corresponding asymptotic exponent is the capacity ofG with respect to said class of digraphs. We derive upper and lower bounds for these capacities for various classes of digraphs, and analyze the conditions under which they are tight.     

The kth lower bases of primitive non-powerful signed digraphs

In [J. Shao, L. You, H. Shan, Bound on the bases of irreducible generalized sign pattern matrices, Linear Algebra Appl. 427 (2007) 285-300], the authors extended the concept of the base from powerful sign pattern matrices to non-powerful irreducible sign pattern matrices. Recently, the kth local bases and the kth upper bases, which are generalizations of the bases, of primitive non-powerful signed digraphs were introduced. In this paper, we introduce a new parameter called the kth lower bases of primitive non-powerful signed digraphs and obtain some bounds for it. For some cases, the bounds we obtain are best possible and the extremal signed digraphs are characterized, respectively. Moreover, we show that there exist “gaps” in the kth lower bases set of primitive non-powerful signed digraphs.     

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.     

Two algorithms for generating and ranking the family of solutions of a finite irreflexive relation

The family of solutions, also known as 1-bases or kernels, of a finite irreflexive relation has a variety of many interesting applications. Furthermore, the decision as towhether the associated digraph posesses a solution belongs to the class of computationally intractable problems known as NP-complete. In this paper we present (a) a tree search algorithm to generate the family of solutions of a digraph and (b) a dynamic programming algorithm to generate the family of solutions ranked in increasing order of their cardinality. Extensive computational experience with the tree search algorithm on more than 1000 randomly generated digraphs ranging from 50 to 150 vertices and from 15% to 60% densities has shown that the proposed algorithm is effective.