Small Directed Strongly Regular Graphs

The goal of the present paper is to provide a gallery of small directed strongly regular graphs.For each graph of order n≤12 and valency k相似文献   

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.     

Regular Graphs,Eigenvalues and Regular Factors

In this article, we obtain a sufficient condition for the existence of regular factors in a regular graph in terms of its third largest eigenvalue. We also determine all values of k such that every r‐regular graph with the third largest eigenvalue at most has a k‐factor.     

Equimatchable Regular Graphs

A graph is called equimatchable if all of its maximal matchings have the same size. Kawarabayashi, Plummer, and Saito showed that the only connected equimatchable 3‐regular graphs are K₄ and K_{3, 3}. We extend this result by showing that for an odd positive integer r, if G is a connected equimatchable r‐regular graph, then . Also it is proved that for an even r, a connected triangle‐free equimatchable r‐regular graph is isomorphic to one of the graphs C₅, C₇, and .     

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.     

The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs

This paper deals with the isomorphism problem of directed path graphs and rooted directed path graphs. Both graph classes belong to the class of chordal graphs, and for both classes the relative complexity of the isomorphism problem is yet unknown. We prove that deciding isomorphism of directed path graphs is isomorphism complete, whereas for rooted directed path graphs we present a polynomial-time isomorphism algorithm.     

Cyclotomy and Strongly Regular Graphs

We consider strongly regular graphs defined on a finite field by taking the union of some cyclotomic classes as difference set. Several new examples are found.     

Strongly Regular Semi-Cayley Graphs

We consider strongly regular graphs = (V, E) on an even number, say 2n, of vertices which admit an automorphism group G of order n which has two orbits on V. Such graphs will be called strongly regular semi-Cayley graphs. For instance, the Petersen graph, the Hoffman–Singleton graph, and the triangular graphs T(q) with q 5 mod 8 provide examples which cannot be obtained as Cayley graphs. We give a representation of strongly regular semi-Cayley graphs in terms of suitable triples of elements in the group ring Z G. By applying characters of G, this approach allows us to obtain interesting nonexistence results if G is Abelian, in particular, if G is cyclic. For instance, if G is cyclic and n is odd, then all examples must have parameters of the form 2n = 4s ² + 4s + 2, k = 2s ² + s, = s ² – 1, and = s ²; examples are known only for s = 1, 2, and 4 (together with a noncyclic example for s = 3). We also apply our results to obtain new conditions for the existence of strongly regular Cayley graphs on an even number of vertices when the underlying group H has an Abelian normal subgroup of index 2. In particular, we show the nonexistence of nontrivial strongly regular Cayley graphs over dihedral and generalized quaternion groups, as well as over two series of non-Abelian 2-groups. Up to now these have been the only general nonexistence results for strongly regular Cayley graphs over non-Abelian groups; only the first of these cases was previously known.     

Generating Random Regular Graphs

Random regular graphs play a central role in combinatorics and theoretical computer science. In this paper, we analyze a simple algorithm introduced by Steger and Wormald [10] and prove that it produces an asymptotically uniform random regular graph in a polynomial time. Precisely, for fixed d and n with d = O(n^1/3−ε), it is shown that the algorithm generates an asymptotically uniform random d-regular graph on n vertices in time O(nd²). This confirms a conjecture of Wormald. The key ingredient in the proof is a recently developed concentration inequality by the second author. The algorithm works for relatively large d in practical (quadratic) time and can be used to derive many properties of uniform random regular graphs. * Research supported in part by grant RB091G-VU from UCSD, by NSF grant DMS-0200357 and by an A. Sloan fellowship.     

Homomorphisms and Polynomial Invariants of Graphs

This paper initiates a study of the connection between graph homomorphisms and the Tutte polynomial. This connection enables us to extend the study to other important polynomial invariants associated with graphs, and closely related to the Tutte polynomial. We then obtain applications of these relationships in several areas, including Abelian Groups and Statistical Physics. A new type of uniqueness of graphs, strongly related to chromatically-unique graphs and Tutte-unique graphs, is introduced in order to provide a new point of view of the conjectures about uniqueness of graphs stated by Bollobas, Peabody and Riordan.     

The Ferry Cover Problem on Regular Graphs and Small-Degree GraphsThe Ferry Cover Problem on Regular Graphs and Small-Degree Graphs

The ferry problem may be viewed as generalizations of the classical wolf-goatcabbage puzzle. The ferry cover problem is to determine the minimum required boat capacity to safely transport n items represented by a conflict graph. The Alcuin number of a conflict graph is the smallest capacity of a boat for which the graph possesses a feasible ferry schedule. In this paper the authors determine the Alcuin number of regular graphs and graphs with maximum degree at most five.     

Polynomial and Regular Maps into Grassmannians

We find a regular deformation retraction _n,r (K): Idem _n,r (K) G _n,r (K) from the manifold Idem _n,r (K) of idempotent n × n matrices with rank r to the Grassmannian manifold G _n,r (K) over K the reals, complex numbers or quaternions. Then we derive an injection from the sets of homotopy classes of complex-valued polynomial to such a set of real-valued regular maps, where denotes the Zariski closure in the affine space ⁿ of a subset ⁿ . Furthermore, we list complex-valued polynomial maps ^{2 2} of any Brouwer degree and deduce that the map ()_2,1: Idem()_2,1 G()_2,1 yields an isomorphism [ ² ] [ ², ²] of cyclic infinite homotopy groups. Finally, we show that every nonzero even Brouwer degree of the spheres ⁿ and ⁿ cannot be realized by a real-valued (resp. complex-valued) homogeneous polynomial map provided that n is even.     

The Ferry Cover Problem on Regular Graphs and Small-Degree Graphs

The ferry problem may be viewed as generalizations of the classical wolf-goat-cabbage puzzle. The ferry cover problem is to determine the minimum required boat capacity to safely transport n items represented by a conflict graph. The Alcuin number of a conflict graph is the smallest capacity of a boat for which the graph possesses a feasible ferry schedule. In this paper the authors determine the Alcuin number of regular graphs and graphs with maximum degree at most five.     

Operator Machines on Directed Graphs

We show that if an infinite-dimensional Banach space X has a symmetric basis then there exists a bounded, linear operator ${R\,:\,X\longrightarrow\, X}We show that if an infinite-dimensional Banach space X has a symmetric basis then there exists a bounded, linear operator R : X? X{R\,:\,X\longrightarrow\, X} such that the set

A = {x ? X : ||Rn x||? ￥}A = \{x \in X\,:\,{\left|\left|{R^n x}\right|\right|}\rightarrow \infty\}      17. Minimum Paths in Directed Graphs      A. Frieze 《The Journal of the Operational Research Society》1977,28(2):339-346 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.      18. Chip-Firing Games on Directed Graphs      Anders Björner  László Lovász 《Journal of Algebraic Combinatorics》1992,1(4):305-328 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.      19. Even Cycles in Directed Graphs      Carsten Thomassen 《European Journal of Combinatorics》1985,6(1):85-89       20. List-Compactness of Infinite Directed Graphs      Bruce L. Bauslaugh 《Graphs and Combinatorics》2001,17(1):17-38 A digraph H is homomorphically compact if the digraphs G which admit homomorphisms to H are exactly the digraphs whose finite subdigraphs all admit homomorphisms to H. In this paper we define a similar notion of compactness for list-homomorphisms. We begin by showing that it is essentially only finite digraphs that are compact with respect to list-homomorphisms. We then explore the effects of restricting the types of list-assignments which are permitted, and obtain some richer characterizations. Received: May 16, 1997 Final version received: January 16, 1998

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 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.     

List-Compactness of Infinite Directed Graphs

A digraph H is homomorphically compact if the digraphs G which admit homomorphisms to H are exactly the digraphs whose finite subdigraphs all admit homomorphisms to H. In this paper we define a similar notion of compactness for list-homomorphisms. We begin by showing that it is essentially only finite digraphs that are compact with respect to list-homomorphisms. We then explore the effects of restricting the types of list-assignments which are permitted, and obtain some richer characterizations. Received: May 16, 1997 Final version received: January 16, 1998