Degree sequence and supereulerian graphs

A sequence d=(d₁,d₂,…,d_n) is graphic if there is a simple graph G with degree sequence d, and such a graph G is called a realization of d. A graphic sequence d is line-hamiltonian if d has a realization G such that L(G) is hamiltonian, and is supereulerian if d has a realization G with a spanning eulerian subgraph. In this paper, it is proved that a nonincreasing graphic sequence d=(d₁,d₂,…,d_n) has a supereulerian realization if and only if d_n≥2 and that d is line-hamiltonian if and only if either d₁=n−1, or ∑_di=1d_i≤∑_dj≥2(d_j−2).     

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.     

On factorable degree sequences

We call a degree sequence graphic (respectively, k-factorable, connected k-factorable) if there exists a graph (respectively, a graph with a k-factor, a graph with a connected k-factor) with the given degree sequence. In this paper we give a necessary and sufficient condition for a k-factorable sequence to be connected k-factorable when k ? 2. We also prove that every k-factorable sequence is (k − 2) factorable and 2-factorable, and also 1-factorable, when the sequence is of even length. Some conjectures are stated and it is also proved that, if {d_i} and {d_i − k} are graphic, then {d_i − r} is graphic for 0 ≤ r ≤ k provided rn is even.     

Four correspondences between graphs and generalized young tableaux

Read's method of counting the number of undirected labeled graphs with a prescribed valency at each labeled node implies that the number of different graphs with a given degree sequence (d₁, d₂, d₃…d_n) is equal to the number of generalized Young tableaux of a certain shape filled with objects of specification (d₁, d₂, d₃…d_n). There are in fact four such results which are applicable to graphs with or without loops and with or without multiple edges. This paper contains four one-one correspondences between the four types of graph and generalized Young tableaux having four different shapes. The correspondences can be considered as combinatorial proofs of four identities of Littlewood.     

On graphs with equal edge connectivity and minimum degree

The note contains some conditions on a graph implying that the edge connectivity is equal to the minimum degree. One of these conditions is that if d₁?d₂???d_n is the degree sequence then ∑^l_l?1(d₁+d_n?1)>In?1 for $\text{1 ? l? min {}\text{n}\text{2?1}\text{, d}{}_{\mathrm{n}}\text{}}$.     

A characterization for a graphic sequence to be potentially C r -graphic

Let r 3, n r and π = (d1, d2, . . . , dn) be a graphic sequence. If there exists a simple graph G on n vertices having degree sequence π such that G contains Cr (a cycle of length r) as a subgraph, then π is said to be potentially Cr-graphic. Li and Yin (2004) posed the following problem: characterize π = (d1, d2, . . . , dn) such that π is potentially Cr-graphic for r 3 and n r. Rao and Rao (1972) and Kundu (1973) answered this problem for the case of n = r. In this paper, this problem is solved completely.     

Langford sequences: perfect and hooked

A sequence {d, d+1,…, d+m?1} of m consecutive positive integers is said to be perfect if the integers {1, 2,…, 2m} can be arranged in disjoint pairs {(a_i, b_i): 1?i?m} so that {b_i?a_i: 1?i?m}={d,d+1,…,d+m?1}. A sequence is hooked if the set {1, 2,…, 2m?1 2m+1} can be arranged in pairs to satisfy the same condition. Well known necessary conditions for perfect sequences are herein shown to be sufficient. Similar necessary and sufficient conditions for hooked sequences are given.     

Maximizing a lower bound on the computational complexity

We solve a combinatorial problem that arises in determining by a method due to Engeler lower bounds for the computational complexity of algorithmic problems. Denote by G_d the class of permutation groups G of degree d that are iterated wreath products of symmetric groups, i.e. G = S_dh?11?1S_d0 with Π^h?1_i=0d_i = d for some natural number h and some sequence (d₀,…,d_h?1) of natural numbers greater than 1. The problem is to characterize those G = S_dh?11?1S_d0 in G_d on which k(G):=log|G|/max_0≤i≤h?1log(d_i!) assumes its maximum. Our solution consists of two necessary conditions for this, namely that d₀≤d₁≤?≤d_h and that d_h is the largest prime divisor of d. Consequently, if d is a prime power, say d = p^h with p prime, then a necessary and sufficient condition is that d_i = p, 0 ≤ i ≤ h ? 1.     

Searching monotone multi-dimensional arrays

A d-dimensional array of real numbers is called monotone increasing if its entries are increasing along each dimension. Given A_n,d, a monotone increasing d-dimensional array with n entries along each dimension, and a real number x, we want to decide whether x∈A_n,d, by performing a sequence of comparisons between x and some entries of A_n,d. We want to minimize the number of comparisons used. In this paper we investigate this search problem, we generalize Linial and Saks’ search algorithm [N. Linial, M. Saks, Searching ordered structures, J. Algorithms 6 (1985) 86-103] for monotone three-dimensional arrays to d-dimensions for d?4. For d=4, our new algorithm is optimal up to the lower order terms.     

2-Cell Embeddings with Prescribed Face Lengths and Genus

Let n be a positive integer, let d ₁, . . . , d _n be a sequence of positive integers, and let ${{q = \frac{1}{2}\sum^{n}_{i=1} d_{i}\cdot}}$ . It is shown that there exists a connected graph G on n vertices, whose degree sequence is d ₁, . . . , d _n and such that G admits a 2-cell embedding in every closed surface whose Euler characteristic is at least n ? q?+?1, if and only if q is an integer and q ?? n ? 1. Moreover, the graph G can be required to be loopless if and only if d _i ?? q for i = 1, . . . , n. This, in particular, answers a question of Skopenkov.     

A Havel-Hakimi type procedure and a sufficient condition for a sequence to be potentially S r,s -graphic

The split graph K _r + $\overline {{K_s}} $ on r+s vertices is denoted by S _r,s . A non-increasing sequence π = (d ₁, d ₂, …, d _n ) of nonnegative integers is said to be potentially S _r,s -graphic if there exists a realization of π containing S _r,s as a subgraph. In this paper, we obtain a Havel-Hakimi type procedure and a simple sufficient condition for π to be potentially S _r,s -graphic. They are extensions of two theorems due to A.R.Rao (The clique number of a graph with given degree sequence, Graph Theory, Proc. Symp., Calcutta 1976, ISI Lect. Notes Series 4 (1979), 251–267 and An Erd?s-Gallai type result on the clique number of a realization of a degree sequence, unpublished).     

Pancyclic graphs and a conjecture of Bondy and Chvátal

A p-vertex graph is called pancyclic if it contains cycles of every length l, 3 ≤ l ≤ p. In this paper we prove the following conjecture of Bondy and Chvátal: If a graph G has vertex degree sequence d₁ ≤ d₂ ≤ … ≤ d_ν, and if $\text{d}{}_{\mathrm{k}}\text{≤ k <}\text{p}\text{2}$ implies d_ν?k ≥ p ? k, then G is pancyclic or bipartite.     

Simulation de lois conjuguées et application à l'estimation de la transformée de Cramer dans ℝd

Let X, X₁, X₂,… be a sequence of i.i.d. ℝ^d-valued random variables with distribution F. An algorithm for the simulation of random vectors with distribution dF_t (x):= e〈t,x〉dF(x)/(t), where (t):= Ee^ť,X〉 (cf. [2]) is used for the estimation of the Cramer transform H (x):= sup_t (〈t, X〉 − log(t)). This method, which belongs to the class of “acceptance-rejection” techniques, is fast and uses a random sieve on the sequence (X_i)_{i ≥ 1}; it does not assume any prior knowledge on F or . We state the asymptotic properties of this estimator calculated on a n-sample of simulated r.v. 's with distribution F_t. We also present some numerical simulations.     

Unconditional structures of translates for L p (ℝ d )

We prove that a sequence (f _i ) _i=1 ^∞ of translates of a fixed f ∈ L _p (?) cannot be an unconditional basis of L _p (?) for any 1 ≤ p < ∞. In contrast to this, for every 2 < p < ∞, d ∈ ? and unbounded sequence (λ _n ) _n∈? ? ? ^d we establish the existence of a function f ∈ L _p (? ^d ) and sequence (g _n *) _n∈? ? L _p *(? ^d ) such that \({({T_{{\lambda _n}}}f,g_n^*)_{n \in {\Bbb N}}}\) forms an unconditional Schauder frame for L _p (? ^d ). In particular, there exists a Schauder frame of integer translates for L _p (?) if (and only if) 2 < p < ∞.     

On additive representation function of general sequences

Let 0 ≦ a ₁ < a ₂ < ? be an infinite sequence of integers and let r ₁(A, n) = |(i;j): a _i + a _j = n, i ≦ j|. We show that if d > 0 is an integer, then there does not exist n ₀ such that d ≦ r ₁ (A, n) ≦ d + [√2d + ½] for n > n ₀.     

A note on the sequence spacel (p v )

In this paper, the linear isometry of the sequence space l(p_v) into itself is specified as the automorphism of l(p_v) onto itself, when (p_v) satisfies the conditions, (i) 0 < p_v? 1, (ii) 1 +d ? p_v ? p < ∞,q < q_v < 1+d/d,d > o When (p_v) satisfies condition (ii),l (p_v) andl (q_v) are proved to be perfect spaces in the sense of Kothe and Toeplitz. A similar result connecting linear isometry and automorphism has been noted in the case of a non-normable complete linear metric space whose conjugate space is also determined.     

On the distribution of values of certain divisor functions

Let {?_d} be a sequence of nonnegative numbers and f(n) = Σ?_d, the sum being over divisors d of n. We say that f has the distribution function F if for all c ≥ 0, the number of integers n ≤ x for which f(n) > c is asymptotic to xF(c), and we investigate when F exists and when it is continuous.     

On the gonality sequence of an algebraic curve

For any smooth irreducible projective curve X, the gonality sequence ${\{d_r \;| \; r \in \mathbb N\}}$ is a strictly increasing sequence of positive integer invariants of X. In most known cases d _r+1 is not much bigger than d _r . In our terminology this means the numbers d _r satisfy the slope inequality. It is the aim of this paper to study cases when this is not true. We give examples for this of extremal curves in ${{\mathbb P}^r}$ , for curves on a general K3-surface in ${{\mathbb P}^r}$ and for complete intersections in ${{\mathbb P}^3}$ .     

Deviation of elements of a Banach space from a system of subspaces

We prove that if X is a real Banach space, Y ₁ ? Y ₂ ? ... is a sequence of strictly embedded closed linear subspaces of X, and d ₁ ≥ d ₂ ≥ ... is a nonincreasing sequence converging to zero, then there exists an element x ∈ X such that the distance ρ(x, Y _n ) from x to Y _n satisfies the inequalities d _n ≤ ρ(x, Y _n ) ≤ 8d _n for n = 1, 2, ....