Circulant Double Coverings of a Circulant Graph of Valency Five

Enumerating the isomorphism classes of several types of graph covering projections is one of the central research topics in enumerative topological graph theory. A covering of G is called circulant if its covering graph is circulant. Recently, the authors [Discrete Math., 277, 73-85 （2004）1 enumerated the isomorphism classes of circulant double coverings of a certain type, called a typical covering, and showed that no double covering of a circulant graph of valency three is circulant. Also, in [Graphs and Combinatorics, 21,386 400 （2005）], the isomorphism classes of circulant double coverings of a circulant graph of valency four are enumerated. In this paper, the isomorphism classes of circulant double coverings of a circulant graph of valency five are enumerated.     

On the Existence of Completely Saturated Packings and Completely Reduced Coverings

We prove the following conjecture of G. Fejes Toth, G. Kuperberg, and W.Kuperberg: every body K in either n-dimensional Euclidean or n-dimensional hyperbolic space admits a completely saturated packing and a completely reduced covering. Also we prove the following counterintuitive result: for every >0, there is a body K in hyperbolic n-space which admits a completely saturated packing with density less than but which also admits a tiling.     

Group Divisible Packings and Coverings with Any Minimum Leave and Minimum Excess

We examine all possible minimum leaves and minimum excesses for maximum group divisible packings and minimum group divisible coverings with triangles or kites, respectively. Necessary and sufficient conditions are established for their existences.     

Petersen图的点传递正则覆盖图

运用基图自同构能被提升的线性准则 ,对满足 :1覆叠变换群 K =Znp,2覆盖图的保簇变换群是点传递的 Petersen图的连通正则覆盖图进行了完全分类 .这种图共有 1 2种类型 .     

Graph Designs for all Graphs with Six Vertices and Eight Edges

Graph designs for all graphs with six vertices and eight edges are discussed. The existence of these graph designs are completely solved except in two possible cases of order 32.     

The Spectrum and Convergence Rates of Exclusion and Interchange Processes on the Complete Graph

We give a short and completely elementary method to find the full spectrum of the exclusion process and a nicely limited superset of the spectrum of the interchange process (a.k.a. random transpositions) on the complete graph. In the case of the exclusion process, this gives a simple closed-form expression for all the eigenvalues and their multiplicities. This result is then used to give an exact expression for the distance in \( L^2 \) from stationarity at any time and upper and lower bounds on the convergence rate for the exclusion process. In the case of the interchange process, upper and lower bounds are similarly found. Our results strengthen or reprove many known results about the mixing time for the two processes in a very simple way.     

Coverings of the Vertices of a Graph by Small Cycles

Given a graph G with n vertices, we call c_k(G) the minimum number of elementary cycles of length at most k necessary to cover the vertices of G. We bound c_k(G) from the minimum degree and the order of the graph.     

Almost Resolvable Maximum Packings of Complete Graphs with 4-Cycles

If the complete graph K _n has vertex set X, a maximum packing of K _n with 4-cycles, (X, C, L), is an edge-disjoint decomposition of K _n into a collection C of 4-cycles so that the unused edges (the set L) is as small a set as possible. Maximum packings of K _n with 4-cycles were shown to exist by Sch?nheim and Bialostocki (Can. Math. Bull. 18:703–708, 1975). An almost parallel class of a maximum packing (X, C, L) of K _n with 4-cycles is a largest possible collection of vertex disjoint 4-cycles (so with ?/4?{\lfloor/4\rfloor} 4-cycles in it). In this paper, for all orders n, except 9, which does not exist, and possibly 23, 41 and 57, we exhibit a maximum packing of K _n with 4-cycles so that the 4-cycles in the packing are resolvable into almost parallel classes, with any remaining 4-cycles being vertex disjoint. [Note: The three missing orders have now been found, and appear in Billington et al. (to appear).]     

最大边数的Cordial图的构造

对于n阶Cordial图G，本给出G的边数的上确界e^*，并给出边数达到e^*的Cordial图的构造。     

关于扇和完全等二部图联图的边染色

得到了扇和完全等二部图联图的边色数.     

Integer Functions on the Cycle Space and Edges of a Graph

A directed graph has a natural \mathbb Z{\mathbb {Z}} -module homomorphism from the underlying graph’s cycle space to \mathbb Z{\mathbb {Z}} where the image of an oriented cycle is the number of forward edges minus the number of backward edges. Such a homomorphism preserves the parity of the length of a cycle and the image of a cycle is bounded by the length of that cycle. Pretzel and Youngs (SIAM J. Discrete Math. 3(4):544–553, 1990) showed that any \mathbb Z{\mathbb {Z}} -module homomorphism of a graph’s cycle space to \mathbb Z{\mathbb {Z}} that satisfies these two properties for all cycles must be such a map induced from an edge direction on the graph. In this paper we will prove a generalization of this theorem and an analogue as well.     

星和完全等二部图联图的点可区别均匀边染色

研究了星与完全等二部图的联图Sm∨Kn,n的点可区别均匀边染色。     

关于扇和完全等二部图联图的点可区别边染色

通过结构分析的方法,考虑各种不同情况,给出了一类联图的点可区别的边染色方法,并得到了它的点可区别的边色数.     

Forbidden Triples Containing a Complete Graph and a Complete Bipartite Graph of Small Order

For a graph G and a set \({\mathcal{F}}\) of connected graphs, G is said be \({\mathcal{F}}\) -free if G does not contain any member of \({\mathcal{F}}\) as an induced subgraph. We let \({\mathcal{G} _{3}(\mathcal{F})}\) denote the set of all 3-connected \({\mathcal{F}}\) -free graphs. This paper is concerned with sets \({\mathcal{F}}\) of connected graphs such that \({\mathcal{F}}\) contains no star, \({|\mathcal{F}|=3}\) and \({\mathcal{G}_{3}(\mathcal{F})}\) is finite. Among other results, we show that for a connected graph T( ≠ K ₁) which is not a star, \({\mathcal{G}_{3}(\{K_{4},K_{2,2},T\})}\) is finite if and only if T is a path of order at most 6.     

Decomposition of Complete Graphs into Cycles and Stars

Let C _k denote a cycle of length k and let S _k denote a star with k edges. As usual K _n denotes the complete graph on n vertices. In this paper we investigate decomposition of K _n into C _l ’s and S _k ’s, and give some necessary or sufficient conditions for such a decomposition to exist. In particular, we give a complete solution to the problem in the case l = k = 4 as follows: For any nonnegative integers p and q and any positive integer n, there exists a decomposition of K _n into p copies of C ₄ and q copies of S ₄ if and only if ${4(p + q)={n \choose 2}, q\ne 1}$ if n is odd, and ${q\geq max\{3, \lceil{\frac{n}{4}\rceil}\}}$ if n is even.     

Strongly Regular Decompositions of the Complete Graph

We study several questions about amorphic association schemes and other strongly regular decompositions of the complete graph. We investigate how two commuting edge-disjoint strongly regular graphs interact. We show that any decomposition of the complete graph into three strongly regular graphs must be an amorphic association scheme. Likewise we show that any decomposition of the complete graph into strongly regular graphs of (negative) Latin square type is an amorphic association scheme. We study strongly regular decompositions of the complete graph consisting of four graphs, and find a primitive counterexample to A.V. Ivanov's conjecture which states that any association scheme consisting of strongly regular graphs only must be amorphic.     

Estimate of the Number of Edges in Subgraphs of a Johnson Graph

Doklady Mathematics - New estimates for the minimum number of edges in subgraphs of a Johnson graph are obtained.