Narrow Results

In this paper, we introduce the notions of the directed, undirected, compressed directed, and compressed undirected irreducible divisor graphs $\mathrm{\Gamma }(x)$, $G(x)$, ${\mathrm{\Gamma }}_c(x),$ and $G_c(x)$ of a nonzero nonunit $x$ in a noncommutative atomic domain $D$, respectively. In light of these notions, we identify the corresponding characterizations of the normal unique factorization domain (n-UFD). Moreover, we study the connection between the kinds of directed and undirected irreducible divisor graphs and an n-FFD. Consequently, these characterizations generalize the results of Coykendall and Maney [Irreducible divisor graphs, Comm. Algebra35(3) (2007) 885895] and Axtell et al. [Irreducible divisor graphs and factorization properties of domains, Comm. Algebra39(11) (2011) 41484162] to the noncommutative setting.

We show that if p:F→E is a covering of directed graphs, then the Cuntz–Krieger algebra C*(F) of F can be viewed as a crossed product of C*(E) by a coaction of a homogeneous space for the fundamental group π₁(E). Combining this result with information about Cuntz–Krieger algebras gives some interesting corollaries which suggest conjectures about crossed products by coactions of homogeneous spaces of discrete groups. We then prove these conjectures.

The problem of sorting an intransitive total ordered set, a generalization of regular sorting, is considered. This generalized sorting is based on the fact that there exists a special linear ordering (also called a generalized sorted sequence) for any intransitive total ordered set, or equivalently, the existence of a Hamiltonian path in a tournament. A new data structure called semi-heap is proposed to construct an optimal Θ(n log n) sorting algorithm. We also provide a cost-optimal parallel algorithm using semi-heap. The run time of this algorithm is Θ(n) with Θ(log n) processors under the EREW PRAM model. The use of a Hamiltonian path (generalized sorting sequence) as an approximation of a ranking system in a tournament is also discussed.

A dynamic memory is a storage medium constituted by an array of cells and an interconnection network between them. It is characterized by the constant circulation of the stored data. The objective is to design the interconnection network in order to have small access times and a simple memory control. Several interconnection schemes have been proposed in the literature. This paper presents a quite general model for such structures that greatly facilitates both the design and the control of the memory. Most previous proposals of dynamic memory interconnection networks are particular instances of our model. Moreover, our approach is used to obtain new proposals of interconnection topologies for dynamic memories and fast cyclic shift registers. Namely, a model that optimizes both the access time and the size of the memory and two memory organizations for sequential access are presented.

A coupled cell network is a schematic diagram employed to define a class of differential equations, and can be thought of as a directed graph whose nodes (cells) represent dynamical systems and whose edges (arrows) represent couplings. Often the nodes and edges are labeled to distinguish different types of system and coupling. The associated differential equations reflect this structure in a natural manner. The network is homogeneous if there is one type of cell and one type of arrow, and moreover, every cell lies at the head end of the same number r of arrows. This number is the valency of the network. We use a group-theoretic formula usually but incorrectly attributed to William Burnside to enumerate homogeneous coupled cell networks with N cells and valency r, in both the disconnected and connected cases. We compute these numbers explicitly when N, r ≤ 6.

A coupled cell network is a finite directed graph in which nodes and edges are classified into equivalence classes. Such networks arise in a formal theory of coupled systems of differential equations, as a schematic indication of the topology of the coupling, but they can be studied independently as combinatorial objects. The edges of a coupled cell network are "identical" if they are all equivalent, and the network is "homogeneous" if all nodes have isomorphic sets of input edges. Golubitsky et al. [2005] proved that every homogeneous identical-edge coupled cell network is a quotient of a network that has no multiple edges and no self-connections. We generalize this theorem to any coupled cell network by removing the conditions of homogeneity and identical edges. The problem is a purely combinatorial assertion about labeled directed graphs, and we give two combinatorial proofs. Both proofs eliminate self-connections inductively. The first proof also eliminates multiple edges inductively, the main feature being the specification of the inductive step in terms of a complexity measure. The second proof obtains a more efficient result by eliminating all multiple edges in a single construction.

A directed network such as the WWW can be represented by a transition matrix. Comparing this matrix to a Frobenius–Perron matrix of a chaotic piecewise-linear one-dimensional map whose domain can be divided into Markov subintervals, we are able to relate the network structure itself to chaotic dynamics. Just like various large deviation properties of local expansion rates (finite-time Lyapunov exponents) related to chaotic dynamics, we can also discuss those properties of network structure.

In this paper, an effective method for identifying and realizing linearly separable Boolean functions (LSBF) of six variables via Cellular Neural Networks (CNN) is presented. We characterized the basic relations between CNN genes and the truth table of Boolean functions. In order to implement LSBF independently, a directed graph is employed to sort the offset levels according to the truth table. Because any linearly separable Boolean gene (LSBG) can be derived separately, our method will be more practical than former schemes [Chen & Chen, 2005a, 2005b; Chen & He, 2006].

We study damage propagation in networks, with an emphasis on production-chain models. The models are formulated as systems of Boolean delay equations. This formalism helps take into account the complexity of the interactions between firms; it turns out to be well adapted to investigating propagation of an initial damage due to a climatic or other natural disaster.

We consider in detail the effects of distinct delays and forcing, which represent external intervention to prevent economic collapse. We also account for the possible presence of randomness in the links and the delays. The paper concentrates on two different network structures, periodic and random, respectively; their study allows one to understand the effects of multiple, concurrent production paths, and the role played by the network topology in damage propagation. Applications to the recent network modeling of climate variability are discussed.

The role of polymorphisms in determining the complexity of constraint satisfaction problems is well established. In this context, we study the stability of CSP complexity and polymorphism properties under some basic graph theoretic constructions. As applications we observe a collapse in the applicability of algorithms for CSPs over directed graphs with both a total source and a total sink: the corresponding CSP is solvable by the “few subpowers algorithm” if and only if it is solvable by a local consistency check algorithm. Moreover, we find that the property of “strict width” and solvability by few subpowers are unstable under first-order reductions. The analysis also yields a complete characterization of the main polymorphism properties for digraphs whose symmetric closure is a complete graph.

From any directed graph E one can construct the graph inverse semigroup $G(E)$, whose elements, roughly speaking, correspond to paths in E. Wang and Luo showed that the congruence lattice $L(G(E))$ of $G(E)$ is upper-semimodular for every graph E, but can fail to be lower-semimodular for some E. We provide a simple characterization of the graphs E for which $L(G(E))$ is lower-semimodular. We also describe those E such that $L(G(E))$ is atomistic, and characterize the minimal generating sets for $L(G(E))$ when E is finite and simple.

We consider intrinsic linking and knotting in the context of directed graphs. We construct an example of a directed graph that contains a consistently oriented knotted cycle in every embedding. We also construct examples of intrinsically 3-linked and 4-linked directed graphs. We introduce two operations, consistent edge contraction and H-cyclic subcontraction, as special cases of minors for digraphs, and show that the property of having a linkless embedding is closed under these operations. We analyze the relationship between the number of distinct knots and links in an undirected graph $G$ and its corresponding symmetric digraph $\overline{DG}$. Finally, we note that the maximum number of edges for a graph that is not intrinsically linked is $O(n)$ in the undirected case, but $O(n^2)$ for directed graphs.

A directed graph $G$ is intrinsically linked if every embedding of that graph contains a nonsplit link $L$, where each component of $L$ is a consistently oriented cycle in $G$. A tournament is a directed graph where each pair of vertices is connected by exactly one directed edge.

We consider intrinsic linking and knotting in tournaments, and study the minimum number of vertices required for a tournament to have various intrinsic linking or knotting properties. We produce the following bounds: intrinsically linked ($n=8$), intrinsically knotted ($9\le n\le 12$), intrinsically 3-linked ($10\le n\le 23$), intrinsically 4-linked ($12\le n\le 66$), intrinsically 5-linked ($15\le n\le 154$), intrinsically $m$-linked ($3m\le n\le 8{(2m-3)}^2$), intrinsically linked with knotted components ($9\le n\le 107$), and the disjoint linking property ($12\le n\le 14$).

We also introduce the consistency gap, which measures the difference in the order of a graph required for intrinsic $n$-linking in tournaments versus undirected graphs. We conjecture the consistency gap to be nondecreasing in $n$, and provide an upper bound at each $n$.

We give a characterization of the convex hull of self-similar sets in ℝ³ which extends the results of Panzone¹ in ℝ². As an application, we show a convex set which cannot correspond to the convex hull of a self-similar set.

The decision problem of satisfiability of Boolean expression in k-conjunctive normal form (kSAT) is a typical NP-complete problem. In this paper, by mapping the whole Boolean expressions in k-conjunctive normal form onto a unit hypercube, we visualize the problem space of kSAT. The pattern of kSAT is shown to have self-similarity which can be deciphered in terms of graph directed iterated function system. We provide that the Hausdorff dimension of the pattern of kSAT is equal to the box-counting dimension and increases with k. This suggests that the time complexity of kSAT increases with k.

Using the covering theory in fractal geometry, we obtain the fractality of self-similar substitution networks introduced by Li et al. [Scale-free effect of substitution networks, Physica A 492 (2018) 1449–1455].

Przytycki has established a connection between the Hochschild homology of an algebra A and the chromatic graph homology of a polygon graph with coefficients in A. In general the chromatic graph homology is not defined in the case where the coefficient ring is a non-commutative algebra. In this paper we define a new homology theory for directed graphs which takes coefficients in an arbitrary A–A bimodule, for A possibly non-commutative, which on polygons agrees with Hochschild homology through a range of dimensions.

In this paper, we define directed enhanced power graphs for finite groups and study some graph-theoretic properties. Moreover, we investigate several algebraic properties of Leavitt path algebras of the directed enhanced power graphs and also of the directed punctured enhanced power graphs. We also compute Grothendieck groups of the Leavitt path algebras of directed punctured enhanced power graphs for cyclic groups and give partial answers to “the algebraic Kirchberg–Phillips question”.

The issue of network community detection has been extensively studied across many fields. Most community detection methods assume that nodes belong to only one community. However, in many cases, nodes can belong to multiple communities simultaneously. This paper presents two overlapping network community detection algorithms that build on the two-step approach, using the extended modularity and cosine function. The applicability of our algorithms extends to both undirected and directed graph structures. To demonstrate the feasibility and effectiveness of these algorithms, we conducted experiments using real data.

We introduce the mutation game on a directed multigraph, which is dual to Mozes’ numbers game. This new game allows us to create geometric and combinatorial structure that allows generalization of root systems to more general graphs. We interpret Coxeter–Dynkin diagrams in this multigraph context and exhibit new geometric forms for the associated root systems.