一个六点七边图的填充与覆盖

$lambda{K_v}$为$lambda$重$v$点完全图, $G$ 为有限简单图. $lambda {K_v}$ 的一个 $G$-设计 ( $G$-填充设计, $G$-覆盖设计), 记为 ($v,G,lambda$)-$GD$(($v,G,lambda$)-$PD$, ($v,G,lambda$)-$CD$), 是指一个序偶($X,calB$),其中 $X$ 为 ${K_v}$ 的顶点集, $cal B$ 为 ${K_v}$ 中同构于 $G$的子图的集合, 称为区组集,使得 ${K_v     

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.     

2类6点7边图的$\lambda$-填充与$\lambda$-覆盖

A maximum （v, G, λ）-PD and a minimum （v, G, λ）-CD axe studied for 2 graphs of 6 vertices and 7 edges. By means of ＂difference method＂ and ＂holey graph design＂, we obtain the result： there exists a （v, Gi, λ）-OPD （OCD） for v ≡ 2, 3, 4, 5, 6 （mod 7）, λ ≥ 1, i = 1, 2.     

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.     

完全有向图的奇长圈覆盖

设DK_v表示完全有向对称图,C（v,m）表示覆盖DK_v的m长有向圈的最小圈数（称为覆盖数）.对任意正整数m和v,当m≤v≤m+6时,覆盖数C（v,m） 被确定.     

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图的构造。     

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

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

Treewidth of the Line Graph of a Complete Graph

In recent articles by Grohe and Marx, the treewidth of the line graph of a complete graph is a critical example—in a certain sense, every graph with large treewidth “contains” . However, the treewidth of was not determined exactly. We determine the exact treewidth of the line graph of a complete graph.     

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.