Finding coherent cyclic orders in strong digraphs

A cyclic order in the vertex set of a digraph is said to be coherent if any arc is contained in a directed cycle whose winding number is one. This notion plays a key role in the proof by Bessy and Thomassé (2004) of a conjecture of Gallai (1964) on covering the vertex set by directed cycles. This paper presents an efficient algorithm for finding a coherent cyclic order in a strongly connected digraph, based on a theorem of Knuth (1974). With the aid of ear decomposition, the algorithm runs in O(nm) time, where n is the number of vertices and m is the number of arcs. This is as fast as testing if a given cyclic order is coherent.     

Cycle extendability in graphs and digraphs

In 1990, Hendry conjectured that all chordal Hamiltonian graphs are cycle extendable, that is, the vertices of each non-Hamiltonian cycle are contained in a cycle of length one greater. Let A be a symmetric (0,1)-matrix with zero main diagonal such that A is the adjacency matrix of a chordal Hamiltonian graph. Hendry’s conjecture in this case is that every k×k principle submatrix of A that dominates a full cycle permutation k×k matrix is a principle submatrix of a (k+1)×(k+1) principle submatrix of A that dominates a (k+1)×(k+1) full cycle permutation matrix. This article generalizes the concept of cycle-extendability to S-extendable; that is, with S⊆{1,2,…,n} and G a graph on n vertices, G is S-extendable if the vertices of every non-Hamiltonian cycle are contained in a cycle length i greater, where i∈S. We investigate this concept in directed graphs and in particular tournaments, i.e., anti-symmetric matrices with zero main diagonal.     

The partition dimension of circulant graphs

Let Π = {S₁, S₂, . . . , S_k} be an ordered partition of the vertex set V (G) of a graph G. The partition representation of a vertex v ∈ V (G) with respect to Π is the k-tuple r(v|Π) = (d(v, S₁), d(v, S₂), . . . , d(v, S_k)), where d(v, S) is the distance between v and a set S. If for every pair of distinct vertices u, v ∈ V (G), we have r(u|Π) ≠ r(v|Π), then Π is a resolving partition and the minimum cardinality of a resolving partition of V (G) is called the partition dimension of G. We study the partition dimension of circulant graphs, which are Cayley graphs of cyclic groups. Grigorious et al. [On the partition dimension of circulant graphs] proved that pd(C_n(1, 2, . . . , t)) ≥ t + 1 for n ≥ 3. We disprove this statement by showing that if t ≥ 4 is even, then there exists an infinite set of values of n, such that . We also present exact values of the partition dimension of circulant graphs with 3 generators.     

Vertex coloring acyclic digraphs and their corresponding hypergraphs

We consider vertex coloring of an acyclic digraph in such a way that two vertices which have a common ancestor in receive distinct colors. Such colorings arise in a natural way when bounding space for various genetic data for efficient analysis. We discuss the corresponding down-chromatic number and derive an upper bound as a function of , the maximum number of descendants of a given vertex, and the degeneracy of the corresponding hypergraph. Finally, we determine an asymptotically tight upper bound of the down-chromatic number in terms of the number of vertices of and .     

The asymptotic numbers of regular tournaments,Eulerian digraphs and Eulerian oriented graphs

LetRT(n), ED(n) andEOG(n) be the number of labelled regular tournaments, labelled loop-free simple Eulerian digraphs, and labelled Eulerian oriented simple graphs, respectively, onn vertices. Then, asn,, for any>0. The last two families of graphs are also enumerated by their numbers of edges. The proofs use the saddle point method applied to appropriaten-dimensional integrals.     

赋权图的w密度和w平衡性

The notion of w-density for the graphs with positive weights on vertices and nonnegative weights on edges is introduced. A weighted graph is called w-balanced if its w-density is no less than the w-density of any subgraph of it. In this paper,a good characterization of w-balanced weighted graphs is given. Applying this characterization ,many large w-balanced weighted graphs are formed by combining smaller ones. In the case where a graph is not w-balanced,a polynomial-time algorithm to find a subgraph of maximum w-density is proposed. It is shown that the w-density theory is closely related to the study of SEW(G,w) games.     

The convexity spectra of graphs

Let D be a connected oriented graph. A set S⊆V(D) is convex in D if, for every pair of vertices x,y∈S, the vertex set of every x-y geodesic (x-y shortest dipath) and y-x geodesic in D is contained in S. The convexity numbercon(D) of a nontrivial oriented graph D is the maximum cardinality of a proper convex set of D. Let G be a graph. We define that S_C(G)={con(D):D is an orientation of G} and S_SC(G)={con(D):D is a strongly connected orientation of G}. In the paper, we show that, for any n?4, 1?a?n-2, and a≠2, there exists a 2-connected graph G with n vertices such that S_C(G)=S_SC(G)={a,n-1} and there is no connected graph G of order n?3 with S_SC(G)={n-1}. Then, we determine that S_C(K₃)={1,2}, S_C(K₄)={1,3}, S_SC(K₃)=S_SC(K₄)={1}, S_C(K₅)={1,3,4}, S_C(K₆)={1,3,4,5}, S_SC(K₅)=S_SC(K₆)={1,3}, S_C(K_n)={1,3,5,6,…,n-1}, S_SC(K_n)={1,3,5,6,…,n-2} for n?7. Finally, we prove that, for any integers n, m, and k with , 1?k?n-1, and k≠2,4, there exists a strongly connected oriented graph D with n vertices, m edges, and convexity number k.     

The asymptotic number of acyclic digraphs. I

We obtain an asymptotic formula forA _n,q , the number of digraphs withn labeled vertices,q edges and no cycles. The derivation consists of two separate parts. In the first we analyze the generating function forA _n,q so as to obtain a central limit theorem for an associated probability distribution. In the second part we show combinatorially thatA _n,q is a smooth function ofq. By combining these results, we obtain the desired asymptotic formula. Research supported by NSF under grant MCS-8300414. Research supported by NSERC under grant A4067. Research supported by NSF under grant MCS-8302282. Research supported by the Australian Department of Science and Technology under the Queen Elizabeth II Fellowship Scheme, while this author was at the University of Newcastle, Australia.     

Vertex-weightings for distance moments and thorny graphs

Valence-weightings are considered for shortest-path distance moments, as well as related weightings for the so-called “Wiener” polynomial. In the case of trees the valence-weighted quantities are found to be expressible as a combination of unweighted quantities. Further the weighted quantities for a so-called “thorny” graph are considered and shown to be related to the weighted and unweighted quantities for the underlying parent graph.     

On the connectivity of randomm-orientable graphs and digraphs

We consider graphs and digraphs obtained by randomly generating a prescribed number of arcs incident at each vertex. We analyse their almost certain connectivity and apply these results to the expected value of random minimum length spanning trees and arborescences. We also examine the relationship between our results and certain results of Erdős and Rényi.     

Local-edge-connectivity in digraphs and oriented graphs

A digraph without any cycle of length two is called an oriented graph. The local-edge-connectivityλ(u,v) of two vertices u and v in a digraph or graph D is the maximum number of edge-disjoint u-v paths in D, and the edge-connectivity of D is defined as . Clearly, λ(u,v)?min{d⁺(u),d^-(v)} for all pairs u and v of vertices in D. Let δ(D) be the minimum degree of D. We call a graph or digraph D maximally edge-connected when λ(D)=δ(D) and maximally local-edge-connected when

λ(u,v)=min{d⁺(u),d^-(v)}     

Longest paths in digraphs

In this paper, we give a sufficient condition on the degrees of the vertices of a digraph to insure the existence of a path of given length, and we characterize the extremal graphs.     

Disjoint cycles in digraphs

We show that, for each natural numberk, these exists a (smallest) natural numberf(k) such that any digraph of minimum outdegree at leastf(k) containsk disjoint cycles. We conjecture thatf(k)=2k−1 and verify this fork=2 and we show that, for eachk≧3, the determination off(k) is a finite problem. Dedicated to Paul Erdős on his seventieth birthday     

Degree and local connectivity in digraphs

It is shown that there is a digraphD of minimum outdegree 12m and μ(x, y; D)=11m, but every digraphD of minimum outdegreen contains verticesx ≠y withλ(x, y; D)≧n−1, whereμ(x, y; D) andλ(x, y; D) denote the maximum number of openly disjoint and edge-disjoint paths, respectively.     

Vertex and edge PI indices of Cartesian product graphs

The Padmakar-Ivan (PI) index of a graph G is the sum over all edges uv of G of the number of edges which are not equidistant from u and v. In this paper, the notion of vertex PI index of a graph is introduced. We apply this notion to compute an exact expression for the PI index of Cartesian product of graphs. This extends a result by Klavzar [On the PI index: PI-partitions and Cartesian product graphs, MATCH Commun. Math. Comput. Chem. 57 (2007) 573-586] for bipartite graphs. Some important properties of vertex PI index are also investigated.     

On a property ofn-edge-connected digraphs

It is proved that for every pair of verticesx, y in a finiten-edge-connected digraphD there is such a pathP fromx toy that the digraphD′ arising fromD by deleting the edges ofP is (n−1)-edge-connected.     

Multipartite Moore digraphs

We derive some Moore-like bounds for multipartite digraphs, which extend those of bipartite digraphs, under the assumption that every vertex of a given partite set is adjacent to the same number δ of vertices in each of the other independent sets. We determine when a multipartite Moore digraph is weakly distance-regular. Within this framework, some necessary conditions for the existence of a r-partite Moore digraph with interpartite outdegree δ > 1 and diameter k = 2m are obtained. In the case δ = 1, which corresponds to almost Moore digraphs, a necessary condition in terms of the permutation cycle structure is derived. Additionally, we present some constructions of dense multipartite digraphs of diameter two that are vertex-transitive.     

Packing circuits in eulerian digraphs

LetG be an eulerian digraph; let (G) be the maximum number of pairwise edge-disjoint directed circuits ofG, and (G) the smallest size of a set of edges that meets all directed circuits ofG. Borobia, Nutov and Penn showed that (G) need not be equal to (G). We show that (G)=(G) provided thatG has a linkless embedding in 3-space, or equivalently, if no minor ofG can be converted toK ₆ by –Y andY– operations.