A generalization of Fan’s results: Distribution of cycle lengths in graphs

Fan [G. Fan, Distribution of cycle lengths in graphs, J. Combin. Theory Ser. B 84 (2002) 187-202] proved that if G is a graph with minimum degree δ(G)≥3k for any positive integer k, then G contains k+1 cycles C₀,C₁,…,C_k such that k+1<|E(C₀)|<|E(C₁)|<?<|E(C_k)|, |E(C_i)−E(C_i−1)|=2, 1≤i≤k−1, and 1≤|E(C_k)|−|E(C_k−1)|≤2, and furthermore, if δ(G)≥3k+1, then |E(C_k)|−|E(C_k−1)|=2. In this paper, we generalize Fan’s result, and show that if we let G be a graph with minimum degree δ(G)≥3, for any positive integer k (if k≥2, then δ(G)≥4), if d_G(u)+d_G(v)≥6k−1 for every pair of adjacent vertices u,v∈V(G), then G contains k+1 cycles C₀,C₁,…,C_k such that k+1<|E(C₀)|<|E(C₁)|<?<|E(C_k)|, |E(C_i)−E(C_i−1)|=2, 1≤i≤k−1, and 1≤|E(C_k)|−|E(C_k−1)|≤2, and furthermore, if d_G(u)+d_G(v)≥6k+1, then |E(C_k)|−|E(C_k−1)|=2.     

Self-adjusting stochastic processes

Let A_t(i, j) be the transition matrix at time t of a process with n states. Such a process may be called self-adjusting if the occurrence of the transition from state h to state k at time t results in a change in the hth row such that A_t+1(h, k) ? A_t(h, k). If the self-adjustment (due to transition h → kx) is A_{t + 1}(h, j) = λA_t(h, j) + (1 ? λ)δ_jk (0 < λ < 1), then with probability 1 the process is eventually periodic. If A₀(i, j) < 1 for all i, j and if the self-adjustment satisfies A_{t + 1}(h, k) = ?(A_t(h, k)) with ?(x) twice differentiable and increasing, x < ?(x) < 1 for 0 ? x < 1,?(1) = ?′(1) = 1, then, with probability 1, lim A_t does not exist.     

Eulerian numbers,Newcomb's problem and representations of symmetric groups

Consider a set of n positive integers consisting of μ₁ 1's, μ₂ 2's,…, μ_rr's. If the integer in the ith place in an arrangement σ of this set is σ(i), and a non-rise in σ is defined as σ(i+1)?σ(i), a problem that suggests itself is the determination of the number of arrangements σ with k non-rises. When each μ_i is unity, the problem is that of finding the number A(n, k) of permutations of distinct integers 1, 2,…, n with k descents, a descent being defined as σ(i+1)<σ(i). The number A(n, k) is known as an Eulerian number. The problem of finding the number of arrangements with k non-rises of the more general set, when not all of μ_i are unity, has appeared in the literature as one part of a problem on dealing a pack of cards, this having been proposed by the American astronomer Simon Newcomb (1835–1909).Both the Eulerian numbers and Newcomb's problem have accumulated a substantial literature. The present paper considers these topics from an entirely new stand-point, that of representations of the symmetric group. This approach yields a well-known recurrence for the Eulerian numbers and a known formula for them in terms of Stirling numbers. It also gives the solutions of the Newcomb problem and some recurrences between these solutions, not all of which have been found earlier. A simple connection is found between Stirling numbers and the Kostka numbers of symmetric group representation theory. The Eulerian numbers can also be expressed in terms of the Kostka numbers.The idea which is novel in this treatment and recurs almost as a motif throughout the paper is that of a skew-hook. This occurs in the first place in a very natural way as a picture of the rises and non-rises of σ, with the nodes of the skew-hook labelled successively as σ(1), σ(2),…. As the paper develops, a new form of skew-hook associated with σ emerges. This does not in general depict the rises and non-rises of σ, and it is now the edges, not the nodes, which carry integer labels. A new type of combinatorial number, here called a ψ-function, arises from these edge-labelled skew-hooks. The ψ-functions are intimately related to the Eulerian numbers and the Newcomb solutions and may have further combinatorial applications. The skew-hook treatment casts fresh light on MacMahon's solution of the Newcomb problem and on his “new symmetric functions”, and, if σ(i)?σ(i+1)?s defines an s-descent in σ, on the enumeration of permutations with ks-descents.Also some characters of the symmetric group with interesting properties and recurrences arise in the course of the paper.     

Graphic sequences with a realization containing a generalized friendship graph

Gould, Jacobson and Lehel [R.J. Gould, M.S. Jacobson, J. Lehel, Potentially G-graphical degree sequences, in: Y. Alavi, et al. (Eds.), Combinatorics, Graph Theory and Algorithms, vol. I, New Issues Press, Kalamazoo, MI, 1999, pp. 451-460] considered a variation of the classical Turán-type extremal problems as follows: for any simple graph H, determine the smallest even integer σ(H,n) such that every n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂+?+d_n≥σ(H,n) has a realization G containing H as a subgraph. Let F_t,r,k denote the generalized friendship graph on kt−kr+r vertices, that is, the graph of k copies of K_t meeting in a common r set, where K_t is the complete graph on t vertices and 0≤r≤t. In this paper, we determine σ(F_t,r,k,n) for k≥2, t≥3, 1≤r≤t−2 and n sufficiently large.     

Small cycles and 2-factor passing through any given vertices in graphs

The theory of vertex-disjoint cycles and 2-factor of graphs has important applications in computer science and network communication. For a graph G, let σ ₂(G):=min?{d(u)+d(v)|uv ? E(G),u≠v}. In the paper, the main results of this paper are as follows:

1. Let k≥2 be an integer and G be a graph of order n≥3k, if σ ₂(G)≥n+2k?2, then for any set of k distinct vertices v ₁,…,v _k , G has k vertex-disjoint cycles C ₁,C ₂,…,C _k of length at most four such that v _i ∈V(C _i ) for all 1≤i≤k.
2. Let k≥1 be an integer and G be a graph of order n≥3k, if σ ₂(G)≥n+2k?2, then for any set of k distinct vertices v ₁,…,v _k , G has k vertex-disjoint cycles C ₁,C ₂,…,C _k such that:
   1. v _i ∈V(C _i ) for all 1≤i≤k.
   2. V(C ₁)∪???∪V(C _k )=V(G), and
   3. |C _i |≤4, 1≤i≤k?1.

Moreover, the condition on σ ₂(G)≥n+2k?2 is sharp.     

Uniformly optimal graphs in some classes of graphs with node failures

The uniformly optimal graph problem with node failures consists of finding the most reliable graph in the class Ω(n,m) of all graphs with n nodes and m edges in which nodes fail independently and edges never fail. The graph G is called uniformly optimal in Ω(n,m) if, for all node-failure probabilities q∈(0,1), the graph G is the most reliable graph in the class of graphs Ω(n,m). This paper proves that the multipartite graphs K(b,b+1,…,b+1,b+2) are uniformly optimal in their classes Ω((k+2)(b+1),(k²+3k+2)(b+1)²/2−1), where k is the number of partite sets of size (b+1), while for i>2, the multipartite graphs K(b,b+1,…,b+1,b+i) are not uniformly optimal in their classes Ω((k+2)b+k+i,(k+2)(k+1)b²/2+(k+1)(k+i)b+k(k+2i−1)/2).     

The uniform convergence and precise asymptotics of generalized stochastic order statistics

Let X(i,n,m,k), i=1,…,n, be generalized order statistics based on F. For fixed r∈N, and a suitable counting process N(t), t>0, we mainly discuss the precise asymptotic of the generalized stochastic order statistics X(N(n)−r+1,N(n),m,k). It not only makes the results of Yan, Wang and Cheng [J.G. Yan, Y.B. Wang, F.Y. Cheng, Precise asymptotics for order statistics of a non-random sample and a random sample, J. Systems Sci. Math. Sci. 26 (2) (2006) 237-244] as the special case of our result, and presents many groups of weighted functions and boundary functions, but also permits a unified approach to several models of ordered random variables.     

Bandwidth of the corona of two graphs

The bandwidth B(G) of a graph G is the minimum of the quantity max{|f(u)-f(v)|:uv∈E(G)} taken over all injective integer numberings f of G. The corona of two graphs G and H, written as G°H, is the graph obtained by taking one copy of G and |V(G)| copies of H, and then joining the ith vertex of G to every vertex in the ith copy of H. In this paper, we investigate the bandwidth of the corona of two graphs. For a graph G, we denote the connectivity of G by κ(G). Let G be a graph on n vertices with B(G)=κ(G)=k?2 and let H be a graph of order m. Let c,p and q be three integers satisfying 1?c?k-1 and . We define h_i=(2k-1)m+(k-i)(⌊(2k-1)m/i⌋+1)+1 for i=1,2,…,k and b=max{⌈(n(m+1)-qm-1)/(p+2)⌉,⌈(n(m+1)+k-q-1)/(p+3)⌉}. Then, among other results, we prove that

     

Cliques, minors and apex graphs

In this paper, we proved the following result: Let G be a (k+2)-connected, non-(k−3)-apex graph where k≥2. If G contains three k-cliques, say L₁, L₂, L₃, such that |L_i∩L_j|≤k−2(1≤i<j≤3), then G contains a K_k+2 as a minor. Note that a graph G is t-apex if G−X is planar for some subset X⊆V(G) of order at most t.This theorem generalizes some earlier results by Robertson, Seymour and Thomas [N. Robertson, P.D. Seymour, R. Thomas, Hadwiger conjecture for K₆-free graphs, Combinatorica 13 (1993) 279-361.], Kawarabayashi and Toft [K. Kawarabayashi, B. Toft, Any 7-chromatic graph has K₇ or K_4,4 as a minor, Combinatorica 25 (2005) 327-353] and Kawarabayashi, Luo, Niu and Zhang [K. Kawarabayashi, R. Luo, J. Niu, C.-Q. Zhang, On structure of k-connected graphs without K_k-minor, Europ. J. Combinatorics 26 (2005) 293-308].     

On the chromaticity of complete multipartite graphs with certain edges added

Let P(G,λ) be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P(H,λ)=P(G,λ) implies H is isomorphic to G. For integers k≥0, t≥2, denote by K((t−1)×p,p+k) the complete t-partite graph that has t−1 partite sets of size p and one partite set of size p+k. Let K(s,t,p,k) be the set of graphs obtained from K((t−1)×p,p+k) by adding a set S of s edges to the partite set of size p+k such that 〈S〉 is bipartite. If s=1, denote the only graph in K(s,t,p,k) by K⁺((t−1)×p,p+k). In this paper, we shall prove that for k=0,1 and p+k≥s+2, each graph G∈K(s,t,p,k) is chromatically unique if and only if 〈S〉 is a chromatically unique graph that has no cut-vertex. As a direct consequence, the graph K⁺((t−1)×p,p+k) is chromatically unique for k=0,1 and p+k≥3.     

Majorization and some operator monotone functions

Let h(t) be a non-decreasing function on I and k(t) an increasing function on J. Then h is said to be majorized by k if k(A)≦k(B) implies h(A)≦h(B). f(t) is operator monotone, by definition, if f(t) is majorized by t. By making use of this majorization we will show that is operator monotone on [0,∞) for 0≦a,b<∞ and for 0≦r≦1; the special case of a=b=1 is the theorem due to Petz-Hasegawa.     

Ω-Theorems for the real part of the Riemann zeta function

For s = σ + it, σ > 1, and integer k ? 1$\text{ζ}{}^{\mathrm{k}}\text{(s) = ∑}\text{d}{}_{\mathrm{k}}\text{(n)}\text{n}{}^3$. In a previous paper, Ω results for $\text{ζ(c + it),}\text{1}\text{2}\text{? c ? 1}$, where obtained in an elementary way by choosing N = N(k, c) so that the size of the single term d_k(N) gave Ω results slightly better than existing ones. Here the method will be shown to give the same results for Re ζ(c + it).     

On the Attainable Order of Collocation Methods for Delay Differential Equations with Proportional Delay

To analyze the attainable order of m-stage implicit (collocation-based) Runge-Kutta methods for the delay differential equation (DDE) y′(t) = by(qt), 0 < q ≤ 1 with y(0) = 1, and the delay Volterra integral equation (DVIE) y(t) = 1 + $\tfrac{b}{q}\int {_0^{qt} }$ y(s) ds with proportional delay qt, 0 < q ≤ 1, our particular interest lies in the approximations (and their orders) at the first mesh point t = h for the collocation solution v(t) of the DDE and the iterated collocation solution u _it(t) of the DVIE to the solution y(t). Recently, H. Brunner proposed the following open problem: “For m ≤ 3, do there exist collocation points c _i = c _i(q), i = 1, 2,..., m in [0,1] such that the rational approximant v(h)is the (m, m)-Padé approximant to y(h)? If these exist, then |v(h) ? y(h)| = O(h ^2m+1) but what is the collocation polynomial M _m(t; q) = K Π _i=1 ^m (t ? c _i) of v(th), t ∈ [0, 1]?” In this paper, we solve this question affirmatively, and give the related results between the collocation solution v(t) of the DDE and the iterated collocation solution u _it(t) of the DVIE. We also answer to Brunner's second open question in the case that one collocation point is fixed at the right end point of the interval.     

The class number of cyclotomic function fields

Let k be a rational function field over a finite field. Carlitz and Hayes have described a family of extensions of k which are analogous to the collection of cyclotomic extensions {Q(ζm)| m ≥ 2} of the rational field Q. We investigate arithmetic properties of these “cyclotomic function fields.” We introduce the notion of the maximal real subfield of the cyclotomic function field and develop class number formulas for both the cyclotomic function field and its maximal real subfield. Our principal result is the analogue of a classical theorem of Kummer which for a prime p and positive integer n relates the class number of Q(ζpn + ζpn?1), the maximal real subfield of Q(ζpn), to the index of the group of cyclotomic units in the full unit group of Z[ζpn].     

Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths

In 1982 Thomassen asked whether there exists an integer f(k,t) such that every strongly f(k,t)-connected tournament T admits a partition of its vertex set into t vertex classes V ₁,…V _t such that for all i the subtournament T[V _i] induced on T by V _i is strongly k-connected. Our main result implies an affirmative answer to this question. In particular we show that f(k, t)=O(k ⁷ t ⁴) suffices. As another application of our main result we give an affirmative answer to a question of Song as to whether, for any integer t, there exists aninteger h(t) such that every strongly h(t)-connected tournament has a 1-factor consisting of t vertex-disjoint cycles of prescribed lengths. We show that h(t)=O(t ⁵) suffices.     

On cycles in regular 3-partite tournaments

The vertex set of a digraph D is denoted by V(D). A c-partite tournament is an orientation of a complete c-partite graph. In 1991, Jian-zhong Wang conjectured that every arc of a regular 3-partite tournament D is contained in directed cycles of all lengths 3,6,9,…,|V(D)|. This conjecture is not valid, because for each integer t with 3?t?|V(D)|, there exists an infinite family of regular 3-partite tournaments D such that at least one arc of D is not contained in a directed cycle of length t.In this paper, we prove that every arc of a regular 3-partite tournament with at least nine vertices is contained in a directed cycle of length m, m+1, or m+2 for 3?m?5, and we conjecture that every arc of a regular 3-partite tournament is contained in a directed cycle of length m, (m+1), or (m+2) for each m∈{3,4,…,|V(D)|-2}.It is known that every regular 3-partite tournament D with at least six vertices contains directed cycles of lengths 3, |V(D)|-3, and |V(D)|. We show that every regular 3-partite tournament D with at least six vertices also has a directed cycle of length 6, and we conjecture that each such 3-partite tournament contains cycles of all lengths 3,6,9,…,|V(D)|.     

Continuous approximation of random function

Modifying the methods of Lee [J. Math. Anal. Appl.61 (1977), 1–6], we show that each μ-measurable mapping f on a normal space T into a separable linear metric space E is almost continuous, where μ is a Radon probability measure. It is shown that for every ε > 0 there exists a compact subset K_ε ? T with μ(K_ε) > 1 ? ε and an elementary function g(t) = ∑ⁿ_{i = 1}h_i(t) x_i such that μ(t?K_ε; f(t) ≠ g(t)) < ε, where x_i?E and h_i(t) are real bounded continuous functions with disjoint supports.     

Constructions of new orthogonal arrays and covering arrays of strength three

A covering array of size N, strength t, degree k, and order v, or a CA(N;t,k,v) in short, is a k×N array on v symbols. In every t×N subarray, each t-tuple column vector occurs at least once. When ‘at least’ is replaced by ‘exactly’, this defines an orthogonal array, OA(t,k,v). A difference covering array, or a DCA(k,n;v), over an abelian group G of order v is a k×n array (aij) (1?i?k, 1?j?n) with entries from G, such that, for any two distinct rows l and h of D (1?l<h?k), the difference list Δlh={dh1−dl1,dh2−dl2,…,dhn−dln} contains every element of G at least once.Covering arrays have important applications in statistics and computer science, as well as in drug screening. In this paper, we present two constructive methods to obtain orthogonal arrays and covering arrays of strength 3 by using DCAs. As a consequence, it is proved that there are an OA(3,5,v) for any integer v?4 and v?2 (mod 4), and an OA(3,6,v) for any positive integer v satisfying gcd(v,4)≠2 and gcd(v,18)≠3. It is also proved that the size CAN(3,k,v) of a CA(N;3,k,v) cannot exceed v³+v² when k=5 and v≡2 (mod 4), or k=6, v≡2 (mod 4) and gcd(v,18)≠3.     

Complete monotonicity of some functions involving polygamma functions

In the present paper, we establish necessary and sufficient conditions for the functions x^α|ψ⁽ⁱ⁾(x+β)| and α|ψ⁽ⁱ⁾(x+β)|−x|ψ⁽ⁱ⁺¹⁾(x+β)| respectively to be monotonic and completely monotonic on (0,∞), where i∈N, α>0 and β≥0 are scalars, and ψ⁽ⁱ⁾(x) are polygamma functions.