On Trees of Bounded Degree with Maximal Number of Greatest Independent Sets

Given n and d, we describe the structure of trees with the maximal possible number of greatest independent sets in the class of n-vertex trees of vertex degree at most d.We show that the extremal tree is unique for all even n but uniqueness may fail for odd n; moreover, for d = 3 and every odd n ≥ 7, there are exactly ?(n ? 3)/4? + 1 extremal trees. In the paper, the problem of searching for extremal (n, d)-trees is also considered for the 2-caterpillars; i.e., the trees in which every vertex lies at distance at most 2 from some simple path. Given n and d ∈ {3, 4}, we completely reveal all extremal 2-caterpillars on n vertices each of which has degree at most d.     

A bijection for triangulations, quadrangulations, pentagulations, etc.

A d-angulation is a planar map with faces of degree d. We present for each integer d?3 a bijection between the class of d-angulations of girth d (i.e., with no cycle of length less than d) and a class of decorated plane trees. Each of the bijections is obtained by specializing a “master bijection” which extends an earlier construction of the first author. Our construction unifies known bijections by Fusy, Poulalhon and Schaeffer for triangulations (d=3) and by Schaeffer for quadrangulations (d=4). For d?5, both the bijections and the enumerative results are new.We also extend our bijections so as to enumerate p-gonal d-angulations (d-angulations with a simple boundary of length p) of girth d. We thereby recover bijectively the results of Brown for simple p-gonal triangulations and simple 2p-gonal quadrangulations and establish new results for d?5.A key ingredient in our proofs is a class of orientations characterizing d-angulations of girth d. Earlier results by Schnyder and by De Fraysseix and Ossona de Mendez showed that simple triangulations and simple quadrangulations are characterized by the existence of orientations having respectively indegree 3 and 2 at each inner vertex. We extend this characterization by showing that a d-angulation has girth d if and only if the graph obtained by duplicating each edge d−2 times admits an orientation having indegree d at each inner vertex.     

Irreducibility of Hurwitz spaces of coverings with one special fiber

Let Y be a smooth, projective complex curve of genus g ? 1. Let d be an integer ? 3, let e = {e₁, e₂,..., e_r} be a partition of d and let |e| = Σ_i=1^r(e_i − 1). In this paper we study the Hurwitz spaces which parametrize coverings of degree d of Y branched in n points of which n − 1 are points of simple ramification and one is a special point whose local monodromy has cyclic type e and furthermore the coverings have full monodromy group S_d. We prove the irreducibility of these Hurwitz spaces when n − 1 + |e| ? 2d, thus generalizing a result of Graber, Harris and Starr [A note on Hurwitz schemes of covers of a positive genus curve, Preprint, math. AG/0205056].     

Improved bounds for the Laplacian energy of Bethe trees

For k, d?2, a Bethe tree is a rooted tree with k levels which the root vertex has degree d, the vertices from level 2 to k-1 have degree d+1 and the vertices at the level k are pendent vertices. So et al, using a theorem by Ky Fan have obtained both upper and lower bounds for the Laplacian energy of bipartite graphs. We shall employ the above mentioned theorem to obtain new and improved bounds for the Laplacian energy in the case of Bethe trees.     

Trees with minimal index and diameter at most four

In this paper we consider the trees with fixed order n and diameter d≤4. Among these trees we identify those trees whose index is minimal.     

Some notes on graphs whose index is close to 2

We consider two classes of graphs: (i) trees of order n and diameter d =n − 3 and (ii) unicyclic graphs of order n and girth g = n − 2. Assuming that each graph within these classes has two vertices of degree 3 at distance k, we order by the index (i.e. spectral radius) the graphs from (i) for any fixed k (1 ? k ? d − 2), and the graphs from (ii) independently of k.     

Hypersurfaces in P n with 1-parameter symmetry groups II

We assume V a hypersurface of degree d in ${P^n({\mathbb C})}$ with isolated singularities and not a cone, admitting a group G of linear symmetries. In earlier work we treated the case when G is semi-simple; here we analyse the unipotent case. Our first main result lists the possible groups G. In each case we discuss the geometry of the action, reduce V to a normal form, find the singular points, study their nature, and calculate the Milnor numbers. The Tjurina number τ(V) ≤ (d ? 1) ^n–2(d ² ? 3d + 3): we call V oversymmetric if this value is attained. We calculate τ in many cases, and characterise the oversymmetric situations. In particular, we list all the cases with dim(G) = 2 which are the oversymmetric cases with d = 3.     

Superlocalization of waves and electrons and hopping conductivity on classical and superconductive fractals

We have found an unexpected paradoxical situation in the percolation transition: the superconductive behavior below and above the threshold. We have found also the two different density of states d_s=4/3 and d_v=1.05 and the inverse localization lengths for fractons with the scalar and vector interactions, respectively. In this concept the wave functions of electrons or waves on an incipient percolation cluster and fractal dilute structure exhibit superlocalization behavior of the form ψ(r)∝exp[−r^d_φ] with values of d_φ1=1.73 and d_φ2=2.4 for the former and the latter. Applications of these results for thermally activated hopping conductivity σ(t)∝exp[−(T₀/T)^β] between impurities on a random fractal structure give the values of β=2/5 for the scalar and β=1/2 (Mott's law) for the vector interactions, respectively. Band states are localized in classical and superlocalized in superconductive percolations.     

Metric trees of generalized roundness one

Every finite metric tree has generalized roundness strictly greater than one. On the other hand, some countable metric trees have generalized roundness precisely one. The purpose of this paper is to identify several large classes of countable metric trees that have generalized roundness precisely one. At the outset we consider spherically symmetric trees endowed with the usual path metric (SSTs). Using a simple geometric argument we show how to determine reasonable upper bounds on the generalized roundness of finite SSTs that depend only on the downward degree sequence of the tree in question. By considering limits, it follows that if the downward degree sequence (d ₀, d ₁, d ₂, . . .) of an SST (T, ρ) satisfies ${|\{j \, | \, d_{j} > 1 \}| = \aleph_{0}}${|\{j \, | \, d_{j} > 1 \}| = \aleph_{0}} , then (T, ρ) has generalized roundness one. In particular, all complete n-ary trees of depth ∞ (n ≥ 2), all k-regular trees (k ≥ 3) and all inductive limits of Cantor trees are seen to have generalized roundness one. The remainder of the paper deals with two classes of countable metric trees of generalized roundness one whose members are not, in general, spherically symmetric. The first such class of trees are merely required to spread out at a sufficient rate (with a restriction on the number of leaves) and the second such class of trees resemble infinite combs. It remains an intriguing problem to completely classify countable metric trees of generalized roundness one.     

Class number one quadratic fields and solvability of some Pellian equations

Consider these two types of positive square-free integers d≠ 1 for which the class number h of the quadratic field Q(√d) is odd: (1) d is prime∈ 1(mod 8), or d=2q where q is prime ≡ 3 (mod 4), or d=qr where q and r are primes such that q≡ 3 (mod 8) and r≡ 7 (mod 8); (2) d is prime ≡ 1 (mod 8), or d=qr where q and r are primes such that q≡r≡ 3 or 7 (mod 8). For d of type (2) (resp. (1)), let Π be the set of all primes (resp. odd primes) p∈N satisfying (d/p) = 1. Also, let δ :=0 (resp. δ :=1) if d≡ 2,3 (mod 4) (resp. d≡ 1 (mod 4)). Then the following are equivalent: (a) h=1; (b) For every p∈П at least one of the two Pellian equations Z ²-dY ² = ±4^δ p is solvable in integers. (c) For every p∈П the Pellian equation W ²-dV ² = 4^δ p ² has a solution (w,v) in integers such that gcd (w,v) divides 2^δ.     

Construction of lattice rules with a trigonometric <Emphasis Type="Italic">d</Emphasis>-property on the basis of extreme lattices

Lattice rules with the trigonometric d-property that are optimal with respect to the number of points are constructed for the approximation of integrals over an n-dimensional unit cube. An extreme lattice for a hyperoctahedron at n = 4 is used to construct lattice rules with the trigonometric d-property and the number of points

$0.80822 \ldots \cdot \Delta ^4 (1 + o(1)), \Delta \to \infty $

(d = 2Δ ? 1 ≥ 3 is an arbitrary odd number). With few exceptions, the resulting lattice rules have the highest previously known effectiveness factor.

     

Regular separable graphs of minimum order with given diameter

A (d, c, v)-graph G is one which is regular of degree v and has diameter d and connectivity c. G is said to be minimum if it is of minimum order, i.e. has the minimumnumber of points; G is separable if c=1.In this paper, the minimum order of a (d, 1, v)-graph is determined and the construction of all minimum (d, 1, v)-graphs is described.     

Spanning cycles of nearly cubic graphs

The fact that a cubic hamiltonian graph must have at least three spanning cycles suggests the question of whether every hamiltonian graph in which each point has degree at least 3 must have at least three spanning cycles. We answer this in the negative by exhibiting graphs on n=2m+1, m≥5, points in which one point has degree 4, all others have degree 3, and only two spanning cycles exist.     

The C r-fundamental splines of Clough–Tocher and Powell–Sabin types for Lagrange interpolation on a three direction mesh

Let Δ⁽¹⁾ be the uniform three direction mesh of the plane whose vertices are integer points of .Let (respectively of degree d=3r (respectively d=3r+1 ) for r odd (respectively even) on the triangulation , and of degree d=2r (respectively d=2r+1) for r odd (respectively even) on the triangulation . Using linear combinations of translates of these splines we obtain Lagrange interpolants whose corresponding order of approximation is optimal. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the Number of Galois Points for a Plane Curve in Positive Characteristic

We study Galois points for a plane smooth curve C ? P ² of degree d ≥ 4 in characteristic p > 2. We generalize Yoshihara's result on the number of inner (resp., outer) Galois points to positive characteristic under the assumption that d ? 1 (resp., d ? 0) modulo p. As an application, we also find the number of Galois points in the case that d = p.     

On the existence of graphs of diameter two and defect two

In the context of the degree/diameter problem, the ‘defect’ of a graph represents the difference between the corresponding Moore bound and its order. Thus, a graph with maximum degree d and diameter two has defect two if its order is n=d²−1. Only four extremal graphs of this type, referred to as (d,2,2)-graphs, are known at present: two of degree d=3 and one of degree d=4 and 5, respectively. In this paper we prove, by using algebraic and spectral techniques, that for all values of the degree d within a certain range, (d,2,2)-graphs do not exist.The enumeration of (d,2,2)-graphs is equivalent to the search of binary symmetric matrices A fulfilling that AJ_n=dJ_n and A²+A+(1−d)I_n=J_n+B, where J_n denotes the all-one matrix and B is the adjacency matrix of a union of graph cycles. In order to get the factorization of the characteristic polynomial of A in Q[x], we consider the polynomials F_i,d(x)=f_i(x²+x+1−d), where f_i(x) denotes the minimal polynomial of the Gauss period , being ζ_i a primitive ith root of unity. We formulate a conjecture on the irreducibility of F_i,d(x) in Q[x] and we show that its proof would imply the nonexistence of (d,2,2)-graphs for any degree d>5.     

The k-factor conjecture is true

A sequence 〈d_i〉, 1≤i≤n, is called graphical if there exists a graph whose i^th vertex has degree d_i for all i. It is shown that the sequences 〈d_i〉 and 〈d_i-k〉 are graphical only if there exists a graph G whose degree sequence is 〈d_i〉 and which has a regular subgraph with k lines at each vertex. Similar theorems have been obtained for digraphs. These theorems resolve comjectures given by A.R. Rao and S.B. Rao, and by B. Grünbaum.     

The mapping class group and the Meyer function for plane curves

For each d ≥ 2, the mapping class group for plane curves of degree d will be defined and it is proved that there exists uniquely the Meyer function on this group. In the case of d = 4, using our Meyer function, we can define the local signature for four-dimensional fiber spaces whose general fibers are non-hyperelliptic compact Riemann surfaces of genus 3. Some computations of our local signature will be given.