Maximum number of edges in a critically k-connected graph

A k-connected graph G is said to be critically k-connected if G−v is not k-connected for any vV(G). We show that if n,k are integers with k4 and nk+2, and G is a critically k-connected graph of order n, then |E(G)|n(n−1)/2−p(n−k)+p²/2, where p=(n/k)+1 if n/k is an odd integer and p=n/k otherwise. We also characterize extremal graphs.     

Convex 4-valent polytopes

Let {p_k}_k≥3 be a sequence of nonnegative integers which satisfies 8 + Σ_k≥3 (k-4) p_k = 0 and p₄ ≥ p₃. Then there is a convex 4-valent polytope P in E³ such that P has exactly p_k k-gons as faces. The inequality p₄ ≥ p₃ is the best possible in the sense that for c < 1 there exist sequences that are not 4-realizable that satisfy both 8 + Σ_{k ≥3} (k - 4) p_k = 0 and p₄ > cp₃. When Σ_{k ≥ 5} p_k ≠ 1, one can make the stronger statement that the sequence {p_k} is 4-reliazable if it satisfies 8 + Σ_{k ≥ 3} (k - 4) p_k = 0 and p₄ ≥ 2Σ_{k ≥ 5} p_k + max{k ¦ p_k ≠ 0}.     

Comparison theorems for the oscillation of higher order difference equations with deviating arguments

The difference equation Δy + δp(k)f (y (g (k))) = 0, where p(k) is positive, is classified into four cases according to is odd or even and δ is 1 or −1. In each case, we shall offer comparison theorems for the oscillation of the difference equation. Examples are also included to illustrate the importance of the results obtained.     

Extremal regular graphs for the achromatic number

The problem of constructing (m, n) cages suggests the following class of problems. For a graph parameter θ, determine the minimum or maximum value of p for which there exists a k-regular graph on p points having a given value of θ. The minimization problem is solved here when θ is the achromatic number, denoted by ψ. This result follows from the following main theorem. Let M(p, k) be the maximum value of ψ(G) over all k-regular graphs G with p points, let {x} be the least integer of size at least x, and let be given by ω(k) = {i(ik+1)+1:1i<∞}. Define the function ƒ(p, k) by

Full-size image

. Then for fixed k2 we have M(p, K=ƒ(p, k) if pω(k) and M(p, k)=ƒ(p,k-1 if pε ω(k) for all p sufficiently large with respect to k.     

ContributionsFinitary bases and formal generating functions

Let k be a nonzero, commutative ring with 1, and let R be a k-algebra with a countably-infinite ordered free k-basis B = [p_n: n 0]. We characterize and analyze those bases from which one can construct a k-algebra of ‘formal B-series’ of the form f=∑c_n p_n, with c_n ε k, showing inter alia that many classical polynomial bases fail to have this property.     

On some integrals arising in mathematical physics

This paper presents in the first section the exact evaluation of three single integrals relating to the dielectric behavior of two-dimensional electron plasmas. In the second section we present a procedure for reducing 3d-dimensional integrals of the form: ∫∫∫dqdpdkD(q)(p+k+q)ƒ(p)[1−ƒ(p+q)]ƒ(k)[1−ƒ(k+q)], where the vectors lie in d-dimensional space and ƒ denotes the Fermi function, to tractable form. The second-order exchange integral for a d-dimensional electron gas is taken as an example and is evaluated in closed form as a function of d.     

Kernel structure of Toeplitz-plus-Hankel matrices

The structure of the kernel of block Toeplitz-plus-Hankel matrices R=[a_j−k+b_j+k], where a_j and b_j are the given p×q blocks with entries from a given field, is investigated. It is shown that R corresponds to two systems of at most p+q vector polynomials from which a basis of the kernel of R and all other Toeplitz-plus-Hankel matrices with the same parameters a_j and b_j can be built. The main result is an analogue of a known kernel structure theorem for block Toeplitz and block Hankel matrices.     

Biased partitions and judicious <Emphasis Type="Italic">k</Emphasis>-partitions of graphs

Let G = (V,E) be a graph with m edges. For reals p ∈ [0, 1] and q = 1- p, let m_p(G) be the minimum of qe(V₁) +pe(V₂) over partitions V = V₁ ∪ V₂, where e(V_i) denotes the number of edges spanned by V_i. We show that if mp(G) = pqm-δ, then there exists a bipartition V₁, V₂ of G such that e(V₁) ≤ p²m - δ + p√m/2 + o(√m) and e(V₂) ≤ q²m - δ + q √m/2 + o(√m) for δ = o(m^2/3). This is sharp for complete graphs up to the error term o(√m). For an integer k ≥ 2, let fk(G) denote the maximum number of edges in a k-partite subgraph of G. We prove that if fk(G) = (1 - 1/k)m + α, then G admits a k-partition such that each vertex class spans at most m/k² - Ω(m/k^7.5) edges for α = Ω(m/k⁶). Both of the above improve the results of Bollobás and Scott.     

On the number of edge-disjoint one factors and the existence of k-factors in complete multipartite graphs

In this paper we use Tutte's f-factor theorem and the method of amalgamations to find necessary and sufficient conditions for the existence of a k-factor in the complete multipartite graph K(p(1), …, p(n)), conditions that are reminiscent of the Erdös-Gallai conditions for the existence of simple graphs with a given degree sequence. We then use this result to investigate the maximum number of edge-disjoint 1-factors in K(p(1), …, p(n)), settling the problem in the case where this number is greater than δ - p(2), where p(1) p(2) … p(n).     

Hamiltonian cycles in n-factor-critical graphs

A graph G is said to be n-factor-critical if G−S has a 1-factor for any SV(G) with |S|=n. In this paper, we prove that if G is a 2-connected n-factor-critical graph of order p with , then G is hamiltonian with some exceptions. To extend this theorem, we define a (k,n)-factor-critical graph to be a graph G such that G−S has a k-factor for any SV(G) with |S|=n. We conjecture that if G is a 2-connected (k,n)-factor-critical graph of order p with , then G is hamiltonian with some exceptions. In this paper, we characterize all such graphs that satisfy the assumption, but are not 1-tough. Using this, we verify the conjecture for k2.     

Subsets of an interval whose product is a power

We form squares from the product of integers in a short interval [n, n + t_n], where we include n in the product. If p is prime, p|n, and (₂^p) > n, we prove that p is the minimum t_n. If no such prime exists, we prove t_n √5n when n> 32. If n = p(2p − 1) and both p and 2p − 1 are primes, then t_n = 3p> 3 √n/2. For n(n + u) a square > n², we conjecture that a and b exist where n < a < b < n + u and nab is a square (except n = 8 and N = 392). Let g₂(n) be minimal such that a square can be formed as the product of distinct integers from [n, g₂(n)] so that no pair of consecutive integers is omitted. We prove that g₂(n) 3n − 3, and list or conjecture the values of g₂(n) for all n. We describe the generalization to kth powers and conjecture the values for large n.     

Holes in random graphs

It is shown that for every >0 with the probability tending to 1 as n→∞ a random graph G(n,p) contains induced cycles of all lengths k, 3 ≤ k ≤ (1 − )n log c/c, provided c(n) = (n − 1)p(n)→∞.     

A generalisation of the diameter of a graph

We prove the following theorem. If G is a connected finite graph of order p, and S is a k-subset of V(G) (where k≥2), then there is a pair of vertices in S which are at a distance ≤2(p−1)/k if k does not divide p, and ≤2(p−1)/k + 1 otherwise.     

Boundedness and asymptotic behavior of the solutions of a fuzzy difference equation

In this paper we study the existence, the uniqueness, the boundedness and the asymptotic behavior of the positive solutions of the fuzzy difference equation x_n+1=∑_i=0^kA_i/x_n−i^p_i, where k{1,2,…,}, A_i, i{0,1,…,k}, are positive fuzzy numbers, p_i, i{0,1,…,k}, are positive constants and x_i, i{−k,−k+1,…,0}, are positive fuzzy numbers.     

On the Equation n_1n_2= n_3n_4 Restricted to Factor Closed Sets

We study the number of solutions N(B,F) of the diophantine equation n_1n_2 = n_3 n_4,where 1 ≤ n_1 ≤ B,1 ≤ n_3 ≤ B,n_2,n_4 ∈ F and F[1,B] is a factor closed set.We study more particularly the case when F={m = p_1~(ε1)···p_k~(εk),ε_j∈{0,1},1 ≤ j ≤ k},p_1,...,p_k being distinct prime numbers.     

A special k-coloring for a connected k-chromatic graph

For each positive integer k we consider the smallest positive integer f(k) (dependent only on k) such that the following holds: Each connected graph G with chromatic number χ(G) = k can be properly vertex colored by k colors so that for each pair of vertices x_o and x_p in any color class there exist vertices x₁, x₂, …, x_p-1 of the same class with dist(x_i, x_i+1) f(k) for each i, 0 i p − 1. Thus, the graph is k-colorable with the vertices of each color class placed throughout the graph so that no subset of the class is at a distance > f(k) from the remainder of the class.

We prove that f(k) < 12k when the order of the graph is k(k − 2) + 1.     

Stability of Periodic Orbits and Return Trajectories of Continuous Multi-valued Maps on Intervals

Let I be a compact interval of real axis R, and(I, H) be the metric space of all nonempty closed subintervals of I with the Hausdorff metric H and f : I → I be a continuous multi-valued map. Assume that Pn =(x_0, x_1,..., xn) is a return tra jectory of f and that p ∈ [min Pn, max Pn] with p ∈ f(p). In this paper, we show that if there exist k(≥ 1) centripetal point pairs of f(relative to p)in {(x_i; x_i+1) : 0 ≤ i ≤ n-1} and n = sk + r(0 ≤ r ≤ k-1), then f has an R-periodic orbit, where R = s + 1 if s is even, and R = s if s is odd and r = 0, and R = s + 2 if s is odd and r 0. Besides,we also study stability of periodic orbits of continuous multi-valued maps from I to I.     

On certain incomplete statistics

The foundations of the incomplete statistics recently proposed by Wang is rediscussed in the context of the canonical statistical ensemble. It is found that the incomplete normalization condition, ∑p^q_i=1 (i=1,…,w), where p_i is the probability of a given microstate, is not compatible with the entropic non-extensive formula proposed by Tsallis. It is proved that the entropic function proposed by Wang must be written as S_q=−k_B∑p_i^2q−1ln_qp_i, whereas the form proposed by Tsallis namely, S_q=−k_B∑p_i^qln_qp_i, is directly associated with the standard normalization condition (∑_ip_i=1).     

Resolutions of Stanley-Reisner rings and Alexander duality

Associated to any simplicial complex Δ on n vertices is a square-free monomial ideal I_Δ in the polynomial ring A = k[x₁, …, x_n], and its quotient k[Δ] = A/I_Δ known as the Stanley-Reisner ring. This note considers a simplicial complex Δ^* which is in a sense a canonical Alexander dual to Δ, previously considered in [1, 5]. Using Alexander duality and a result of Hochster computing the Betti numbers dim_k Tor_i^A (k[Δ],k), it is shown (Proposition 1) that these Betti numbers are computable from the homology of links of faces in Δ^*. As corollaries, we prove that I_Δ has a linear resolution as A-module if and only if Δ^* is Cohen-Macaulay over k, and show how to compute the Betti numbers dim_k Tor_i^A (k[Δ],k) in some cases where Δ^* is wellbehaved (shellable, Cohen-Macaulay, or Buchsbaum). Some other applications of the notion of shellability are also discussed.     

First passage time for some stationary processes

For a 1-dependent stationary sequence {X_n} we first show that if u satisfies p₁=p₁(u)=P(X₁>u)0.025 and n>3 is such that 88np₁³1, then

P{max(X₁,…,X_n)u}=ν·μⁿ+O{p₁³(88n(1+124np₁³)+561)}, n>3,

where

ν=1−p₂+2p₃−3p₄+p₁²+6p₂²−6p₁p₂,μ=(1+p₁−p₂+p₃−p₄+2p₁²+3p₂²−5p₁p₂)⁻¹

with

p_k=p_k(u)=P{min(X₁,…,X_k)>u}, k1

and

|O(x)||x|.

From this result we deduce, for a stationary T-dependent process with a.s. continuous path {Y_s}, a similar, in terms of P{max_0skTY_s<u}, k=1,2 formula for P{max_0stY_su}, t>3T and apply this formula to the process Y_s=W(s+1)−W(s), s0, where {W(s)} is the Wiener process. We then obtain numerical estimations of the above probabilities.