There are Finitely Many Triangle-Free Distance-Regular Graphs with Degree 8, 9 or 10

In this paper we prove that there are finitely many triangle-free distance-regular graphs with degree 8, 9 or 10.     

On the 7 Total Colorability of Planar Graphs with Maximum Degree 6 and without 4-cycles

Vizing and Behzad independently conjectured that every graph is (Δ + 2)-totally-colorable, where Δ denotes the maximum degree of G. This conjecture has not been settled yet even for planar graphs. The only open case is Δ = 6. It is known that planar graphs with Δ ≥ 9 are (Δ + 1)-totally-colorable. We conjecture that planar graphs with 4 ≤ Δ ≤ 8 are also (Δ + 1)-totally-colorable. In addition to some known results supporting this conjecture, we prove that planar graphs with Δ = 6 and without 4-cycles are 7-totally-colorable. Supported by the Natural Science Foundation of Department of Education of Zhejiang Province, China, Grant No. 20070441.     

There are Infinitely Many Williams Squares with Circular Structure and Order a Multiple of 4

Williams squares, also known as row quasi-complete Latin squares, that have circular structure are used in repeated measurements designs where error terms are correlated. They are known to exist for all orders that are not multiples of 4 and also order 8; there is no such square of order 4. We use a variation of the generating array method to construct a Williams square of order 12 with circular structure. We also give a product theorem that produces Williams squares of orders 8r and 12s, where the smallest prime divisor of r is at least 11 and the smallest prime divisor of s is at least 13, that have circular structure.     

There is no triangulation of the torus with vertex degrees 5, 6, ... , 6, 7 and related results: geometric proofs for combinatorial theorems

There is no 5,7-triangulation of the torus, that is, no triangulation with exactly two exceptional vertices, of degree 5 and 7. Similarly, there is no 3,5-quadrangulation. The vertices of a 2,4-hexangulation of the torus cannot be bicolored. Similar statements hold for 4,8-triangulations and 2,6-quadrangulations. We prove these results, of which the first two are known and the others seem to be new, as corollaries of a theorem on the holonomy group of a euclidean cone metric on the torus with just two cone points. We provide two proofs of this theorem: One argument is metric in nature, the other relies on the induced conformal structure and proceeds by invoking the residue theorem. Similar methods can be used to prove a theorem of Dress on infinite triangulations of the plane with exactly two irregular vertices. The non-existence results for torus decompositions provide infinite families of graphs which cannot be embedded in the torus.     

具有性质cr+1=3,ar+1=3a+1或 4a的(a+1,3)型距离正则图

设г是直径为d且型为(a 1,3)的距离正则图,其中a≥2.用l(c,a,b)表示交叉阵列ι(г)中列(c,a,6)t的个数,记r=r(г)=l(c1,a1,b1),8=8(г)=l(Cr 1,ar 1,br 1)及t=t(г)=l(cr s 1,ar s 1,br s 1).那末,若Cr 1=3,ar 1=4a或3a 1,则d=r t 2.     

Claw‐Free Graphs,Skeletal Graphs,and a Stronger Conjecture on ω, Δ, and χ

The second author's (B.A.R.) ω, Δ, χ conjecture proposes that every graph satisfies . In this article, we prove that the conjecture holds for all claw‐free graphs. Our approach uses the structure theorem of Chudnovsky and Seymour. Along the way, we discuss a stronger local conjecture, and prove that it holds for claw‐free graphs with a three‐colorable complement. To prove our results, we introduce a very useful χ‐preserving reduction on homogeneous pairs of cliques, and thus restrict our view to so‐called skeletal graphs.     

具有性质cr 1=3,ar 1=3a 1或 4a的(a 1,3)型距离正则图

设г是直径为d且型为(a 1,3)的距离正则图,其中a≥2.用l(c,a,b)表示交叉阵列ι(г)中列(c,a,6)t的个数,记r=r(г)=l(c1,a1,b1),8=8(г)=l(Cr 1,ar 1,br 1)及t=t(г)=l(cr s 1,ar s 1,br s 1).那末,若Cr 1=3,ar 1=4a或3a 1,则d=r t 2.     

Simplicial Vertices in Graphs with no Induced Four‐Edge Path or Four‐Edge Antipath,and the H6‐Conjecture

Let be the class of all graphs with no induced four‐edge path or four‐edge antipath. Hayward and Nastos 6 conjectured that every prime graph in not isomorphic to the cycle of length five is either a split graph or contains a certain useful arrangement of simplicial and antisimplicial vertices. In this article, we give a counterexample to their conjecture, and prove a slightly weaker version. Additionally, applying a result of the first author and Seymour 1 we give a short proof of Fouquet's result 3 on the structure of the subclass of bull‐free graphs contained in .     

On the Structure of Graphs with Given Odd Girth and Large Minimum Degree

We study minimum degree conditions for which a graph with given odd girth has a simple structure. For example, the classical work of Andrásfai, Erd?s, and Sós implies that every n‐vertex graph with odd girth and minimum degree bigger than must be bipartite. We consider graphs with a weaker condition on the minimum degree. Generalizing results of Häggkvist and of Häggkvist and Jin for the cases and 3, we show that every n‐vertex graph with odd girth and minimum degree bigger than is homomorphic to the cycle of length . This is best possible in the sense that there are graphs with minimum degree and odd girth that are not homomorphic to the cycle of length . Similar results were obtained by Brandt and Ribe‐Baumann.     

Decomposition of Sparse Graphs into Forests and a Graph with Bounded Degree

For a loopless multigraph G, the fractional arboricity Arb(G) is the maximum of over all subgraphs H with at least two vertices. Generalizing the Nash‐Williams Arboricity Theorem, the Nine Dragon Tree Conjecture asserts that if , then G decomposes into forests with one having maximum degree at most d. The conjecture was previously proved for ; we prove it for and when and . For , we can further restrict one forest to have at most two edges in each component. For general , we prove weaker conclusions. If , then implies that G decomposes into k forests plus a multigraph (not necessarily a forest) with maximum degree at most d. If , then implies that G decomposes into forests, one having maximum degree at most d. Our results generalize earlier results about decomposition of sparse planar graphs.     

The Linear Arboricity of Planar Graphs without 5-, 6-Cycles with Chords

The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. In this paper, it is proved that for a planar graph G, ${la(G)=\lceil\frac{\Delta(G)}{2}\rceil}$ if Δ(G) ≥ 7 and G has no 5-cycles with chords, or Δ(G) ≥ 5 and G has no 5-, 6-cycles with chords.     

On a Conjecture of Erdős,Gallai, and Tuza

Erd?s, Gallai, and Tuza posed the following problem: given an n‐vertex graph G, let denote the smallest size of a set of edges whose deletion makes G triangle‐free, and let denote the largest size of a set of edges containing at most one edge from each triangle of G. Is it always the case that ? We have two main results. We first obtain the upper bound , as a partial result toward the Erd?s–Gallai–Tuza conjecture. We also show that always , where m is the number of edges in G; this bound is sharp in several notable cases.     

Stabilizers of Vertices of Graphs with Primitive Automorphism Groups and a Strong Version of the Sims Conjecture. III

This is the third in a series of papers whose results imply the validity of a strong version of the Sims conjecture on finite primitive permutation groups. In this paper, the case of primitive groups with simple socle of classical nonorthogonal Lie type and nonparabolic point stabilizer is considered.     

On a Class of Finitely Supported Scaling Functions with Properties of Interpolation and Symmetry

In this paper, a class of finitely supported orthogonal filters with interpolation and symmetry is constructed. The work is partially supported by NSFC(69735020).     

一类具有对称性和插值性的紧支撑尺度函数

具有对称性和插值性的多进尺度函数的滤波器也具有相应的对称性和插值 性,本文研究具有具有对称性和插值性的滤波器构造问题.     

直径为5的图的2-导出匹配划分和2-导出匹配覆盖问题的NP-完全性

给定一个简单图G和正整数κ,具有完美匹配的图G的κ-导出匹配划分是对顶点集V(C)的一个κ-划分(V1,V2,...,Vκ),其中对每一个i(1≤i≤κ),由Vi导出的G的子图G[Vi]是1-正则的.κ-导出匹配划分问题是指对给定的图G,判定G是否存在一个κ-导出匹配划分.令M1,M2…,Mκ为图G的κ个导出匹配,如果V(M1)UV(M2)∪...∪V(Mκ)=V(G),则我们称{M1,M2,...,Mκ}是G的κ-导出匹配覆盖.κ-导出匹配覆盖问题是指对给定的图G,判定G是否存在κ-导出匹配覆盖.本文给出了Yang,Yuan和Dong所提出问题的解,证明了直径为5的图的导出匹配2一划分问题和导出匹配2-覆盖问题都是NP-完全的.     

An Application of Logic to Combinatorial Geometry: How Many Tetrahedra are Equidecomposable with a Cube?

It is known (see Rapp [9]) that elementary geometry with the additional quantifier “there exist uncountably many” is decidable. We show that this decidability helps in solving the following problem from combinatorial geometry: does there exist an uncountable family of pairwise non-congruent tetrahedra that are n-equidecomposable with a cube? Mathematics Subject Classification: 03B25, 03C80, 51M04, 52B05, 52B10.     

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.