On Models of Directed Path Graphs Non Rooted Directed Path Graphs

A directed path graph is the intersection graph of a family of directed subpaths of a directed tree. A rooted directed path graph is the intersection graph of a family of directed subpaths of a rooted tree. Clearly, rooted directed path graphs are directed path graphs. Several characterizations are known for directed path graphs: one by forbidden induced subgraphs and one by forbidden asteroids. It is an open problem to find such characterizations for rooted directed path graphs. With the purpose of proving knowledge in this direction, we show in this paper properties of directed path models that can not be rooted for chordal graphs with any leafage and with leafage four. Therefore, we prove that for leafage four directed path graphs minimally non rooted directed path graphs have a unique asteroidal quadruple, and can be characterized by the presence of certain type of asteroidal quadruples.     

Some Families of Directed Strongly Regular Graphs Obtained from Certain Finite Incidence Structures

We present many new directed strongly regular graphs by direct construction. We construct these graphs on the collections of antiflags of certain finite incidence structures. In this way, we confirm the feasibility of infinitely many parameter sets that was previously undetermined. We describe some examples of graphs together with their isomorphism classes to demonstrate the fact that our construction method is capable of producing many graphs with same parameters.     

Explicit Construction and Uniqueness for Universal Operator Algebras of Directed Graphs

Given a directed graph, there exist a universal operator algebraand universal C*-algebra associated to the directed graph. Inthis paper we give intrinsic constructions for these objects.We also provide an explicit construction for the maximal C*-algebraof an operator algebra. We discuss uniqueness of the universalalgebras for finite graphs, showing that for finite graphs thegraph is an isomorphism invariant for the universal operatoralgebra of a directed graph. We show that the underlying undirectedgraph is a Banach algebra isomorphism invariant for the universalC*-algebra of a directed graph.     

Cohn Path Algebras of Higher-Rank Graphs

In this article, we introduce Cohn path algebras of higher-rank graphs. We prove that for a higher-rank graph Λ, there exists a higher-rank graph T Λ such that the Cohn path algebra of Λ is isomorphic to the Kumjian-Pask algebra of T Λ. We then use this isomorphism and properties of Kumjian-Pask algebras to study Cohn path algebras. This includes proving a uniqueness theorem for Cohn path algebras.     

无向路图和块图上的混合控制

图G=(V,E)的一个混合控制集是一个满足如下条件的集合DV∪E:不在D中的每个点或每条边都相邻或关联于D中的至少一个点或一条边.确定图的最小基数的混合控制集的问题称为混合控制问题.本文研究混合控制问题的算法复杂性,证明了混合控制问题在无向路图上是NP-完全的,但在块图上有线性时间算法.无向路图和块图都是弦图的子类,又是树的母类.     

可能行无限图C~*-代数

本文研究可能行无限有向图的C~*-代数。对于一个可能行无限的有向图E,通过引进集合S(μ,v),将行无限点上的算子拓扑强收敛关系代数化表示出来,并由此构造了一个结构丰富的非零*-代数H_E;进而利用H_E证明了一个由Cuntz-Krieger E-族{s_e,p_v}生成的泛C~*-代数 C~*(E)的存在性,并且证明了H_E和 C~*(E)在图同构意义下不依赖于E的选择,从而是可能行无限有向图的同构不变量。     

Intersection graphs of paths in a tree

The intersection graph for a family of sets is obtained by associating each set with a vertex of the graph and joining two vertices by an edge exactly when their corresponding sets have a nonempty intersection. Intersection graphs arise naturally in many contexts, such as scheduling conflicting events, and have been widely studied.We present a unified framework for studying several classes of intersection graphs arising from families of paths in a tree. Four distinct classes of graphs arise by considering paths to be the sets of vertices or the edges making up the path, and by allowing the underlying tree to be undirected or directed; in the latter case only directed paths are allowed. Two further classes are obtained by requiring the directed tree to be rooted. We introduce other classes of graphs as well. The rooted directed vertex path graphs have been studied by Gavril; the vertex path graphs have been studied by Gavril and Renz; the edge path graphs have been studied by Golumbic and Jamison, Lobb, Syslo, and Tarjan.The main results are a characterization of these graphs in terms of their “clique tree” representations and a unified recognition algorithm. The algorithm repeatedly separates an arbitrary graph by a (maximal) clique separator, checks the form of the resultant nondecomposable “atoms,” and finally checks that each separation step is valid. In all cases, the first two steps can be performed in polynomial time. In all but one case, the final step is based on a certain two-coloring condition and so can be done efficiently; in the other case the recognition problem can be shown to be NP-complete since a certain three-coloring condition is needed.The strength of this unified approach is that it clarifies and unifies virtually all of the important known results for these graphs and provides substantial new results as well. For example, the exact intersecting relationships among these graphs, and between these graphs and chordal and perfect graphs fall out easily as corollaries. A number of other results, such as bounds on the number of (maximal) cliques, related optimization problems on these graphs, etc., are presented along with open problems.     

Graphs with two isomorphism classes of spanning unicyclic subgraphs

The graphs whose spanning unicyclic subgraphs partition into exactly two isomorphism classes are characterized.This work is a continuation of [6] where graphs with one isomorphism class of spanning unicyclic graphs are characterized. The analogous question for spanning trees was posed in [10] and graphs with one isomorphism class of spanning trees were characterized in [2], [3], [4], [7], [11] while graphs with two isomorphism classes of spanning trees were characterized in [4], [5]. Related topics are treated in [1], [8], [9].     

Chip-Firing Games on Directed Graphs

We consider the following (solitary) game: each node of a directed graph contains a pile of chips. A move consists of selecting a node with at least as many chips as its outdegree, and sending one chip along each outgoing edge to its neighbors. We extend to directed graphs several results on the undirected version obtained earlier by the authors, P. Shor, and G. Tardos, and we discuss some new topics such as periodicity, reachability, and probabilistic aspects.Among the new results specifically concerning digraphs, we relate the length of the shortest period of an infinite game to the length of the longest terminating game, and also to the access time of random walks on the same graph. These questions involve a study of the Laplace operator for directed graphs. We show that for many graphs, in particular for undirected graphs, the problem whether a given position of the chips can be reached from the initial position is polynomial time solvable.Finally, we show how the basic properties of the probabilistic abacus can be derived from our results.     

有向P2-路图的结构性质

一个有向图D的有向Pk-路图Pk(D)是通过把D中的所有有向k长路作为点集;两点u= x1x2…xk+1,v=y1y2…yk+1之间有弧uv当xi=yi-1,i=2,3,…,k+1.明显地,当k=1时Pk(D)就是通常的有向线图L(D).在[1,2]中,P2-路图得到完整刻画.在[3]中,Broersma等人研究了有向...     

Random Walks on Directed Covers of Graphs

Directed covers of finite graphs are also known as periodic trees or trees with finitely many cone types. We expand the existing theory of directed covers of finite graphs to those of infinite graphs. While the lower growth rate still equals the branching number, upper and lower growth rates no longer coincide in general. Furthermore, the behavior of random walks on directed covers of infinite graphs is more subtle. We provide a classification in terms of recurrence and transience and point out that the critical random walk may be recurrent or transient. Our proof is based on the observation that recurrence of the random walk is equivalent to the almost sure extinction of an appropriate branching process. Two examples in random environment are provided: homesick random walk on infinite percolation clusters and random walk in random environment on directed covers. Furthermore, we calculate, under reasonable assumptions, the rate of escape with respect to suitable length functions and prove the existence of the asymptotic entropy providing an explicit formula which is also a new result for directed covers of finite graphs. In particular, the asymptotic entropy of random walks on directed covers of finite graphs is positive if and only if the random walk is transient.     

Minimum Paths in Directed Graphs

This paper considers the problem of finding paths from a fixed node to all other nodes of a directed graph which minimise a function defined on the paths. Under certain assumptions a characterisation of optimal paths is derived. Two algorithms which are generalisations of standard shortest path methods are then given.     

Chip-Firing and Riemann-Roch Theory for Directed Graphs

Baker and Norine developed a graph theoretic analogue of the classical Riemann-Roch theorem. Amini and Manjunath extended their criteria to all full-dimensional lattices orthogonal to the all ones vector. We show that Amini and Manjunath?s criteria holds for all full-dimensional lattices orthogonal to some positive vector and study some combinatorial examples of such lattices. Two distinct generalizations of the chip-firing game of Baker and Norine to directed graphs are provided. We describe how the “row” chip-firing game is related to the sandpile model and the “column” chip-firing game is related to directed G-parking functions. We finish with a discussion of arithmetical graphs, introduced by Lorenzini, viewing them as a class of vertex weighted graphs whose Laplacian is orthogonal to a positive vector and describe how they may be viewed as a special class of unweighted strongly connected directed graphs.     

Path Decomposition of Graphs with Given Path Length

A path decomposition of a graph G is a list of paths such that each edge appears in exactly onepath in the list.G is said to admit a {P_l}-decomposition if G can be decomposed into some copies of P_l,whereP_l is a path of length l-1.Similarly,G is said to admit a {P_l,P_k}=decomposition if G can be decomposed intosome copies of P_l or P_k.An k-cycle,denoted by C_k,is a cycle with k vertices.An odd tree is a tree of which allvertices have odd degree.In this paper,it is shown that a connected graph G admits a {P_3,P_4}-decompositionif and only if G is neither a 3-cycle nor an odd tree.This result includes the related result of Yan,Xu andMutu.Moreover,two polynomial algorithms are given to find {P_3}-decomposition and {P_3,P_4}-decompositionof graphs,respectively.Hence,{P_3}-decomposition problem and {P_3,P_4}-decomposition problem of graphs aresolved completely.     

Asteroids in rooted and directed path graphs

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 contains no 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 strong path. Two non-adjacent vertices are linked by a strong path if either they have a common neighbor or they are the endpoints of two vertex-disjoint chordless paths satisfying certain conditions. A strong asteroidal triple is an asteroidal triple such that each pair is linked by a strong path. We prove that a chordal graph is a directed path graph if and only if it contains no strong asteroidal triple. We also introduce a related notion of asteroidal quadruple, and conjecture a characterization of rooted path graphs which are the intersection graphs of directed paths in a rooted tree.     

Operator Algebraic Quotient Structures Induced by Directed Graphs

Our result is about inclusions for (finite or infinite) countable directed graphs. In the proof, we use Free Probability Theory, groupoids, and algebras of operators (von Neumann algebras). We show that inclusions of directed graphs induce quotients for associated groupoid actions. With the use of operator thechniques, we then establish a duality between inclusions of graphs on the one hand and quotients of algebras on the other. Our main result is that each connected graph induces a quotient generated by a free group. This is a generalization of the notion of induced representations in the context of unitary representations of groups, i.e., the induction from the representations of a subgroup of an ambient group. The analogue is to systems of imprimitivity based on the homogeneous space. The parallel of this is the more general context of graphs (extending from groups to groupoids): We first prove that inclusions for connected graphs correspond to free group quotients, and we then build up the general case via connected components of given graphs.     

Parallelism, Preprocessing, and Reachability: A Hybrid Algorithm for Directed Graphs

The problem of reachability in a directed graph has resisted attempts at efficient parallelization. Only for fairly dense graphs can we efficiently achieve significant parallel speedups, using known methods. We describe a technique allowing significant parallel speedup even for moderately sparse graphs, following a sequential preprocessing step in which a representation of the graph is created.     

Colour Number, Capacity, and Perfectness of Directed Graphs

We introduce a new concept of chromatic number for directed graphs, called the colour number and use it to upper bound the transitive clique number and the Sperner capacity of arbitrary directed graphs. Our results represent a common generalization of previous bounds of Alon and the second author and lead to a concept of perfectness for directed graphs. Revised: June 3, 1998     

Laplacians and the Cheeger Inequality for Directed Graphs

We consider Laplacians for directed graphs and examine their eigenvalues. We introduce a notion of a circulation in a directed graph and its connection with the Rayleigh quotient. We then define a Cheeger constant and establish the Cheeger inequality for directed graphs. These relations can be used to deal with various problems that often arise in the study of non-reversible Markov chains including bounding the rate of convergence and deriving comparison theorems.Received September 8, 2004     

Definability in the Substructure Ordering of Simple Graphs

For simple graphs, we investigate and seek to characterize the properties first-order definable by the induced subgraph relation. Let \({\mathcal{P}\mathcal{G}}\) denote the set of finite isomorphism types of simple graphs ordered by the induced subgraph relation. We prove this poset has only one non-identity automorphism co, and for each finite isomorphism type G, the set {G, G ^co } is definable. Furthermore, we show first-order definability in \({\mathcal{P}\mathcal{G}}\) captures, up to isomorphism, full second-order satisfiability among finite simple graphs. These results can be utilized to explore first-order definability in the closely associated lattice of universal classes. We show that for simple graphs, the lattice of universal classes has only one non-trivial automorphism, the set of finitely generated and finitely axiomatizable universal classes are separately definable, and each such universal subclass is definable up to the unique non-trivial automorphism.