Connected (g,f)‐factors

The vertex set of the reduced Kneser graph KG₂(m,2) consists of all pairs {a,b} such that a, bε{1,2,…,m} and 2≤|a?b|≤m?2. Two vertices are defined to be adjacent if they are disjoint. We prove that, if m≥4 and m≠5, then the circular chromatic number of KG₂(m,2) is equal to m?2, its ordinary chromatic number. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 62–68, 2002     

Contraction–Deletion Invariants for Graphs

We consider generalizations of the Tutte polynomial on multigraphs obtained by keeping the main recurrence relation T(G)=T(G/e)+T(G−e) for eE(G) neither a bridge nor a loop and dropping the relations for bridges and loops. Our first aim is to find the universal invariant satisfying these conditions, from which all others may be obtained. Surprisingly, this turns out to be the universal V-function Z of Tutte (1947, Proc. Cambridge Philos. Soc.43, 26–40) defined to obey the same relation for bridges as well. We also obtain a corresponding result for graphs with colours on the edges and describe the universal coloured V-function, which is more complicated than Z. Extending results of Tutte (1974, J. Combin. Theory Ser. B16, 168–174) and Brylawski (1981, J. Combin. Theory Ser. B30, 233–246), we give a simple proof that there are non-isomorphic graphs of arbitrarily high connectivity with the same Tutte polynomial and the same value of Z. We conjecture that almost all graphs are determined by their chromatic or Tutte polynomials and provide mild evidence to support this.     

A Characterization of the Tutte Polynomial via Combinatorial Embeddings

We give a new characterization of the Tutte polynomial of graphs. Our characterization is formally close (but inequivalent) to the original definition given by Tutte as the generating function of spanning trees counted according to activities. Tutte’s notion of activity requires a choice of a linear order on the edge set (though the generating function of the activities is, in fact, independent of this order). We define a new notion of activity, the embedding-activity, which requires a choice of a combinatorial embedding of the graph, that is, a cyclic order of the edges around each vertex. We prove that the Tutte polynomial equals the generating function of spanning trees counted according to embedding-activities. This generating function is, in fact, independent of the embedding. Received March 15, 2006     

The Diophantine equation (x − 1)(y − 1) = (z − 1)

We sharpen work of Bugeaud to show that the equation of the title has, for t = 1 or 2, no solutions in positive integers x, y, z and k with z > 1 and k > 3. The proof utilizes a variety of techniques, including the hypergeometric method of Thue and Siegel, as well as an assortment of gap principles.     

On the evaluation at (<Emphasis Type="Italic">j</Emphasis>, <Emphasis Type="Italic">j</Emphasis><Superscript>2</Superscript>) of the Tutte polynomial of a ternary matroid

F. Jaeger has shown that up to a ± sign the evaluation at (j, j ²) of the Tutte polynomial of a ternary matroid can be expressed in terms of the dimension of the bicycle space of a representation over GF(3). We give a short algebraic proof of this result, which moreover yields the exact value of ±, a problem left open in Jaeger's paper. It follows that the computation of t(j, j ²) is of polynomial complexity for a ternary matroid.E. Gioan: C.N.R.S., MontpellierM. Las Vergnas: C.N.R.S., Paris     

Behaviour of (−Δ−k2−i0+)−1 outside fading obstacles,independant scattering hypothesis and applications

This paper deals with the behaviour of k‐outgoing solutions of ?Δu?k²u=f outside a fading soft obstacle. We extend an approach using the so‐called Lax–Phillips construction and the well‐known properties of the capacity of smooth obstacles. So, classical results are recovered in a straightforward manner. The previous approach enables us to consider the case of obstacles composed of many tiny spheres. Roughly speaking, we prove that the scattering amplitude is approximately the sum of the scattering amplitudes scattered by each isolated sphere, which is an alternative form of the first Born approximation. As a consequence, two inverse problems are solved. Copyright © 2003 John Wiley & Sons, Ltd.     

Two constructions of (v, (v − 1)/2, (v − 3)/2) difference families

In this article, two constructions of (v, (v ? 1)/2, (v ? 3)/2) difference families are presented. The first construction produces both cyclic and noncyclic difference families, while the second one gives only cyclic difference families. The parameters of the second construction are new. The difference families presented in this article can be used to construct Hadamard matrices. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 164–171, 2008     

一个在置换图中寻找DFS树的最优算法

本是通过在连通置换图中构造辅助树的方法,给出了一个在具有n个顶点的置换图G中寻找深度优先支撑树（简称,DFS树）的最优算法,并证明了该算法的时间复杂性为O(n)。     

A Class of 2‐(3n7, 3n−17, (3n−17−1)/2) Designs

Generalized Hadamard matrices are used for the construction of a class of quasi‐residual nonresolvable BIBD's with parameters . The designs are not embeddable as residual designs into symmetric designs if n is even. The construction yields many nonisomorphic designs for every given n ≥ 2, including more than 10¹⁷ nonisomorphic 2‐(63,21,10) designs. © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 460–464, 2007     

Zero-free regions for multivariate Tutte polynomials (alias Potts-model partition functions) of graphs and matroids

The chromatic polynomial P_G(q) of a loopless graph G is known to be non-zero (with explicitly known sign) on the intervals (−∞,0), (0,1) and (1,32/27]. Analogous theorems hold for the flow polynomial of bridgeless graphs and for the characteristic polynomial of loopless matroids. Here we exhibit all these results as special cases of more general theorems on real zero-free regions of the multivariate Tutte polynomial Z_G(q,v). The proofs are quite simple, and employ deletion–contraction together with parallel and series reduction. In particular, they shed light on the origin of the curious number 32/27.     

Tridiagonal pairs of shape (1, 2, 1)

Let denote a field and let V denote a vector space over with finite positive dimension. We consider a pair of linear transformations A:V→V and A^*:V→V that satisfies the following conditions: (i) each of A,A^* is diagonalizable; (ii) there exists an ordering of the eigenspaces of A such that A^*V_iV_i-1+V_i+V_i+1 for 0id, where V_-1=0 and V_d+1=0; (iii) there exists an ordering of the eigenspaces of A^* such that for 0iδ, where and ; (iv) there is no subspace W of V such that AWW, A^*WW, W≠0,W≠V. We call such a pair a tridiagonal pair on V. It is known that d=δ and that for 0id the dimensions of coincide; we denote this common value by ρ_i. The sequence is called the shape of the pair. In this paper we assume the shape is (1,2,1) and obtain the following results. We describe six bases for V; one diagonalizes A, another diagonalizes A^*, and the other four underlie the split decompositions for A,A^*. We give the action of A and A^* on each basis. For each ordered pair of bases among the six, we give the transition matrix. At the end we classify the tridiagonal pairs of shape (1,2,1) in terms of a sequence of scalars called the parameter array.     

A Regularization Procedure for Σn−i=1fi(zj)xi = g(zj), ( j = 1, 2, …, n)

A regularization procedure for linear systems of the type fi(z_j)x_i = g(zj), (j = 1, 2, …, n) is presented, which is particularly useful in the case when z₁, z₂, …, z_n are close to each other. The associated numerical algorithm was tested on several examples for which analytic solutions do exist and was found to yield highly accurate results.     

Existence of multiple positive solutions for −Δu−μ(u/∣x∣2)=u2*−1+σf(x)

In this paper, we consider the semilinear elliptic problem where Ω??^N (N?3) is a bounded smooth domain such that 0∈Ω, σ>0 is a real parameter, and f(x) is some given function in L^∞(Ω) such that f(x)?0, f(x)?0 in Ω. Some existence results of multiple solutions have been obtained by implicit function theorem, monotone iteration method and Mountain Pass Lemma. Copyright © 2002 John Wiley & Sons, Ltd.     

Every DFS Tree of a 3‐Connected Graph Contains a Contractible Edge

Tutte proved that every 3‐connected graph G on more than 4 vertices contains a contractible edge. We strengthen this result by showing that every depth‐first‐search tree of G contains a contractible edge. Moreover, we show that every spanning tree of G contains a contractible edge if G is 3‐regular or if G does not contain two disjoint pairs of adjacent degree‐3 vertices.     

Property (quasi‐α) and the denseness of norm attaining mappings

We introduce property (quasi ‐α), which implies property (A) defined by Lindenstrauss [10] and whose dual property is property (quasi‐β) [2]. We consider relations between this property and other sufficient conditions for property (A), and study the denseness of norm attaining mappings under the conditions of these properties. In particular, if each of the Banach spaces X_k , 1 ≤ k ≤ n – 1, has property (quasi‐α) and X_n has property (A), then the projective tensor product X₁ ··· X_n has property (A). (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Classification of 9-dimensional trilinear alternating forms over GF(2)

Let V be a finite-dimensional vector space over a finite field and let f be a trilinear alternating form over V. For such forms, we introduce two new invariants. Together with a generalized radical polynomial used for classification of forms in dimension 8 over GF(2), they are sufficient to distinguish between all trilinear alternating forms in dimension 9 over GF(2). To prove the completeness of the list of forms, we computed their groups of automorphisms. There are 31 degenerate and 317 nondegenerate forms. We point out some forms with either small or large automorphism group.     

Classification of 8-Dimensional Trilinear Alternating Forms over GF(2)

Let V be an n-dimensional vector space over a finite field and let f be a trilinear alternating form over V. For such forms we introduce a new invariant called radical polynomial and investigate its behaviour, in particular in the case of the 2-element field. We show that it is compatible with direct products of forms and how it is related to its values on dimension n ? 1. Moreover, it turns out that it is full up to dimension 7. On the other hand, on higher dimensions it is no more full and it is necessary to generalize it to obtain (using computer) a classification of forms on dimension 8 over the 2-element field. This classification is provided, together with the sizes of stabilizers of the corresponding forms.     

Periodic solutions of u'(t) = −f(u(t − 1)): Multiplicity results and small period solutions

In this paper we are concerned with the differential delay equation For odd and continuous nonlinearities f: R → R . We want to prove existence and multiplicity criteria for so called “slowly oscillating” periodic solutions of (A). The oddness condition is of course a rather restrictive one, but due to results of Nussbaum [9], [10] and Peters [13],[14] and numerical studies of Jürgens, Peitgen and Saupe [7] and Hadeler [6] we know that even for odd nonlinearities f (A) may display a complicated dynamical behaviour. On the other hand the oddness condition allows a classification of symmetry properties of periodic solutions of (A).     

Solving the equation −uxx − ϵuyy = f(x,y, u) by an O(h4) finite difference method

The semi‐linear equation −u_xx − ϵu_yy = f(x, y, u) with Dirichlet boundary conditions is solved by an O(h⁴) finite difference method, which has local truncation error O(h²) at the mesh points neighboring the boundary and O(h⁴) at most interior mesh points. It is proved that the finite difference method is O(h⁴) uniformly convergent as h → 0. The method is considered in the form of a system of algebraic equations with a nine diagonal sparse matrix. The system of algebraic equations is solved by an implicit iterative method combined with Gauss elimination. A Mathematica module is designed for the purpose of testing and using the method. To illustrate the method, the equation of twisting a springy rod is solved. © 2000 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 16: 395–407, 2000