Asymptotic enumeration of strongly connected digraphs by vertices and edges

We derive an asymptotic formula for the number of strongly connected digraphs with n vertices and m arcs (directed edges), valid for m ‐ n →∞ as n →∞ provided m = O(nlog n). This fills the gap between Wright's results which apply to m = n + O (1) , and the long‐known threshold for m, above which a random digraph with n vertices and m arcs is likely to be strongly connected. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Asymptotic enumeration of sparse 2‐connected graphs

We determine an asymptotic formula for the number of labelled 2‐connected (simple) graphs on n vertices and m edges, provided that m ‐ n →∞ and m = O(nlog n) as n →∞. This is the entire range of m not covered by previous results. The proof involves determining properties of the core and kernel of random graphs with minimum degree at least 2. The case of 2‐edge‐connectedness is treated similarly. We also obtain formulae for the number of 2‐connected graphs with given degree sequence for most (“typical”) sequences. Our main result solves a problem of Wright from 1983. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

On Hamilton decompositions of infinite circulant graphs

The natural infinite analog of a (finite) Hamilton cycle is a two‐way‐infinite Hamilton path (connected spanning 2‐valent subgraph). Although it is known that every connected 2k‐valent infinite circulant graph has a two‐way‐infinite Hamilton path, there exist many such graphs that do not have a decomposition into k edge‐disjoint two‐way‐infinite Hamilton paths. This contrasts with the finite case where it is conjectured that every 2k‐valent connected circulant graph has a decomposition into k edge‐disjoint Hamilton cycles. We settle the problem of decomposing 2k‐valent infinite circulant graphs into k edge‐disjoint two‐way‐infinite Hamilton paths for , in many cases when , and in many other cases including where the connection set is or .     

Non‐Cayley‐isomorphic self‐complementary circulant graphs

Non‐CI self‐complementary circulant graphs of prime‐squared order are constructed and enumerated. It is shown that for prime p, there exists a self‐complementary circulant graph of order p² not Cayley isomorphic to its complement if and only if p ≡ 1 (mod 8). Such graphs are also enumerated. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 128–141, 2000     

On isomorphic factorizations of circulant graphs

We investigate the conjecture that every circulant graph X admits a k‐isofactorization for every k dividing |E(X)|. We obtain partial results with an emphasis on small values of k. © 2006 Wiley Periodicals, Inc. J Combin Designs 14: 406–414, 2006     

Asymptotic enumeration of 2-covers and line graphs

A 2-cover is a multiset of subsets of [n]?{1,2,…,n} such that each element of [n] lies in exactly two of the subsets. A 2-cover is called proper if all of the subsets are distinct, and is called restricted if any two of them intersect in at most one element.In this paper we find asymptotic enumerations for the number of line graphs on n labelled vertices and for 2-covers.We find that the number s_n of 2-covers and the number t_n of proper 2-covers both have asymptotic growth

     

Decomposition of bipartite graphs into closed trails

Let Lct(G) denote the set of all lengths of closed trails that exist in an even graph G. A sequence (t ₁,..., t _p ) of elements of Lct(G) adding up to |E(G)| is G-realisable provided there is a sequence (T ₁,..., t _p ) of pairwise edge-disjoint closed trails in G such that T _i is of length T _i for i = 1,..., p. The graph G is arbitrarily decomposable into closed trails if all possible sequences are G-realisable. In the paper it is proved that if a ⩾ 1 is an odd integer and M _a,a is a perfect matching in K _a,a , then the graph K _a,a -M _a,a is arbitrarily decomposable into closed trails.      

The asymptotic number of spanning trees in circulant graphs

Let T(G) be the number of spanning trees in graph G. In this note, we explore the asymptotics of T(G) when G is a circulant graph with given jumps.The circulant graph is the 2k-regular graph with n vertices labeled 0,1,2,…,n−1, where node i has the 2k neighbors i±s₁,i±s₂,…,i±s_k where all the operations are . We give a closed formula for the asymptotic limit as a function of s₁,s₂,…,s_k. We then extend this by permitting some of the jumps to be linear functions of n, i.e., letting s_i, d_i and e_i be arbitrary integers, and examining

     

Embedding of circulant graphs and generalized Petersen graphs on projective plane

Both the circulant graph and the generalized Petersen graph are important types of graphs in graph theory. In this paper, the structures of embeddings of circulant graph C(2n + 1; {1, n}) on the projective plane are described, the number of embeddings of C(2n + 1; {1, n}) on the projective plane follows, then the number of embeddings of the generalized Petersen graph P(2n +1, n) on the projective plane is deduced from that of C(2n +1; {1, n}), because C(2n + 1;{1, n}) is a minor of P(2n + 1, n), their structures of embeddings have relations. In the same way, the number of embeddings of the generalized Petersen graph P(2n, 2) on the projective plane is also obtained.     

Compatible Eulerian circuits in Eulerian (di)graphs with generalized transition systems

A transition in a graph is defined as a pair of adjacent edges. A transition system of an Eulerian graph refers to a set of partitions such that for each vertex of the graph, there corresponds to a partition of the set of edges incident to the vertex into transitions. A generalized transition system $F\left(G\right)$ over a graph $G$ defines a set of transitions over $G$. A compatible Eulerian circuit of an Eulerian graph $G$ with a generalized transition system $F\left(G\right)$ is defined as an Eulerian circuit in which no two consecutive edges form a transition defined by $F\left(G\right)$. In this paper, we further introduce the concept of weakly generalized transition system which is an extension of the generalized transition system and prove some Ore-type sufficient conditions for the existence of compatible Eulerian circuits in Eulerian graphs with (weakly) generalized transition systems and obtain corresponding results for Eulerian digraphs. Our conditions improve some previous results due to Jackson and Isaak, respectively.     

Asymptotic Eulerian expansions for binomial and negative binomial reciprocals

Asymptotic expansions of any order for expectations of inverses of random variables with positive binomial and negative binomial distributions are obtained in terms of the Eulerian polynomials. The paper extends and improves upon an expansion due to David and Johnson (1956-7).

     

Further analysis of the number of spanning trees in circulant graphs

Let 1?s₁<s₂<?<s_k?⌊n/2⌋ be given integers. An undirected even-valent circulant graph, has n vertices 0,1,2,…, n-1, and for each and j(0?j?n-1) there is an edge between j and . Let stand for the number of spanning trees of . For this special class of graphs, a general and most recent result, which is obtained in [Y.P. Zhang, X. Yong, M. Golin, [The number of spanning trees in circulant graphs, Discrete Math. 223 (2000) 337-350]], is that where a_n satisfies a linear recurrence relation of order 2^s_k-1. And, most recently, for odd-valent circulant graphs, a nice investigation on the number a_n is [X. Chen, Q. Lin, F. Zhang, The number of spanning trees in odd-valent circulant graphs, Discrete Math. 282 (2004) 69-79].In this paper, we explore further properties of the numbers a_n from their combinatorial structures. Comparing with the previous work, the differences are that (1) in finding the coefficients of recurrence formulas for a_n, we avoid solving a system of linear equations with exponential size, but instead, we give explicit formulas; (2) we find the asymptotic functions and therefore we ‘answer’ the open problem posed in the conclusion of [Y.P. Zhang, X. Yong, M. Golin, The number of spanning trees in circulant graphs, Discrete Math. 223 (2000) 337-350]. As examples, we describe our technique and the asymptotics of the numbers.     

Two‐connected orientations of Eulerian graphs

A graph G = (V, E) is said to be weakly four‐connected if G is 4‐edge‐connected and G – x is 2‐edge‐connected for every x ∈ V. We prove that every weakly four‐connected Eulerian graph has a 2‐connected Eulerian orientation. This verifies a special case of a conjecture of A. Frank . © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 230–242, 2006     

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.     

Decomposing complete multipartite graphs into closed trails of arbitrary even lengths

We prove that any complete multipartite graph with parts of even size can be decomposed into closed trails with prescribed even lengths. Copyright © 2011 Wiley Periodicals, Inc. J Combin Designs 19:455‐462, 2011     

Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs

A locally connected spanning tree of a graph G is a spanning tree T of G such that the set of all neighbors of v in T induces a connected subgraph of G for every v∈V(G). The purpose of this paper is to give linear-time algorithms for finding locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs, respectively.