Covering the vertices of a graph by cycles of prescribed length

The main theorem of that paper is the following: let G be a graph of order n, of size at least (n² - 3n + 6)/2. For any integers k, n₁, n₂,…,n_k such that n = n₁ + n₂ +. + n_k and n_i ? 3, there exists a covering of the vertices of G by disjoint cycles (C_i) =l…k with |C_i| = ni, except when n = 6, n₁ = 3, n₂ = 3, and G is isomorphic to G₁, the complement of G₁ consisting of a C₃ and a stable set of three vertices, or when n = 9, n₁ = n₂ = n₃ = 3, and G is isomorphic to G₂, the complement of G₂ consisting of a complete graph on four vertices and a stable set of five vertices. We prove an analogous theorem for bipartite graphs: let G be a bipartite balanced graph of order 2n, of size at least n² - n + 2. For any integers s, n₁, n₂,…,n_s with n_i ? 2 and n = n₁ + n₂ + ? + n_s, there exists a covering of the vertices of G by s disjoint cycles C_i, with |C_i| = 2n_i.     

New series of odd non-congruent numbers

We determine all square-free odd positive integers n such that the 2-Selmer groups S _n and Ŝ _n of the elliptic curve E _n : y ² = x(x − n)(x − 2n) and its dual curve ê _n : y ² = x ³ + 6nx ² + n ² x have the smallest size: S _n = {1}, Ŝ _n = {1, 2, n, 2n}. It is well known that for such integer n, the rank of group E _n (ℚ) of the rational points on E _n is zero so that n is a non-congruent number. In this way we obtain many new series of elliptic curves E _n with rank zero and such series of integers n are non-congruent numbers. Dedicated to Professor Sheng GONG on the occasion of his 75th birthday     

The structure of symplectic groups over arbitrary commutative rings

LetR be an arbitrary commutative ring, andn be an integer ≥3. It is proved for any idealJ ofR thatESp _2n(R,J)=[ESp _2n(R),ESp _2n(J)]=[ESp _2n(R),ESp _2n(R,J)] =[ESp _2n(R),GSp _2n(R,J)]=[Sp _2n(R),ESp _2n(R,J)]. Furthermore, the problem of normal subgroups ofSp _2n(R) has an affirmative solution if and only ifaR=a ²R+2aR for eacha inR. This covers the relevant results of [4], [8], [10], [12] and [13]. Project Supported by the Science Fund of the Chinese Academy of Sciences     

Packing graphs with odd and even trees

The Gyárfás-Lehel tree-packing conjecture asserts that any sequence T₁, T₂, …, T_n^?1 of trees with 1, 2, …, n - 1 edges packs into the complete graph K_n on n vertices. The present paper examines two conjectures that jointly imply the Gyárfás-Lehel conjecture: 1. For n even, any T₁, T₃, …, T_n^?1 pack into the half-complete graph Hn on n vertices.2. For n odd, any T₂, T₄, …, T_n^?1 pack into the half-complete graph Hn on n vertices. The H_n are uniquely defined by their degree sequences: H_n and H_n+1 are complements in K_n+1. It is shown that H_n and T_n+1 pack into H_n+2 if T_n+1 is a double star, unimodal triple star, interior-3 caterpillar, or scorpion. Hence Conjectures 1 and 2 are true for these specialized types of trees. The conjectures are also valid for all trees when n ≤ 9, so that the Gyárfás-Lehel conjecture holds for n ≤ 9.     

A transitive closure algorithm

An algorithm is given for computing the transitive closure of a directed graph in a time no greater thana ₁ N ₁ n+a ₂ n ² for largen wherea ₁ anda ₂ are constants depending on the computer used to execute the algorithm,n is the number of nodes in the graph andN ₁ is the number of arcs (not counting those arcs which are part of a cycle and not counting those arcs which can be removed without changing the transitive closure). For graphs where each arc is selected at random with probabilityp, the average time to compute the transitive closure is no greater than min{a ₁ pn ³+a ₂ n ², 1/2a ₁ n ² p ^–2+a ₂ n ²} for largen. The algorithm will compute the transitive closure of an undirected graph in a time no greater thana ₂ n ² for largen. The method uses aboutn ²+n bits and 5n words of storage (where each word can holdn+2 values).     

Appearance of complex components in a random bigraph

This is an investigation into the limiting distribution of the sparse connected components in an n₁ × n₂ bipartite multigraph with approximately ½n edges, where n₁, n₂ ≈? ½n. We will show that the probability of finding no complex components in a random n₁ × n₂ bigraph, with approximately ½n edges, is asymptotically the same as for random graphs with n vertices and approximately ½n edges, namely √2/3. In addition, we will show that, for n₁ × n₂ multi-bigraphs, the probability distribution for finitely many bicyclic components, tricyclic components, etc., with no components having more than a given number of cycles, asymptotically equals the corresponding distribution for random multigraphs with n vertices and approximately half as many edges. As an application of this analysis we present a method for estimating the efficiency of memory access in a distributed, replicated data base.     

A spectral identity between symmetric spaces

Let π be a cuspidal automorphic representation ofGL _2n . We prove an identity between two spectral distributions onSp _2n andGL _2n respectively. The first is the spherical distribution with respect toSp _n×Sp _nof the residual Eisenstein series induced from π. The second is the weighted spherical distribution of π with respect toGL _n×GL _nand a certain degenerate Eisenstein series. A similar identity relates the pair (U _2n ,Sp _n) and (GL _n/E,GL _n/F) whereE/F is the quadratic extension defining the quasi-split unitary groupU _2n . We also have a Whittaker version of these trace identities. First-named author partially supported by NSF grant DMS 0070611. Second-named author partially supported by NSF grant DMS 9970342.     

Induced matching extendable graphs

We say that a simple graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. The main results of this paper are as follows: (1) For every connected IM-extendable graph G with |V(G)| ≥ 4, the girth g(G) ≤ 4. (2) If G is a connected IM-extendable graph, then |E(G)| ≥ ${3\over 2}|V(G)| - 2$; the equality holds if and only if G ≅ T × K₂, where T is a tree. (3) The only 3-regular connected IM-extendable graphs are C_n × K₂, for n ≥ 3, and C_2n(1, n), for n ≥ 2, where C_2n(1, n) is the graph with 2n vertices x₀, x₁, …, x_2n−1, such that x_ix_j is an edge of C_2n(1, n) if either |i − j| ≡ 1 (mod 2n) or |i − j| ≡ n (mod 2n). © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 203–213, 1998     

Chromatic factorizations of a graph

Let n₁ ? n₂ ? …? ? n_k ? 2 be integers. We say that G has an (n₁, n₂, …?, n_k-chromatic factorization if G) can be edge-factored as G₁ ⊕ G₂ ⊕ …? ⊕ G_k with χ(G_i) = nA_i, for i = 1,2,…, k. The following results are proved:

• i If (n₁ ? 1)n₂ …? n_k < χ(G) ? n₁n₂ …? n_k, then G has an (n₁, n₂, …?, n_k)-chromatic factorization.
• ii If n₁ + n₂ + …? + n_k ? (k - 1) ? n ? n₁n₂ …? n_k, then K_n has an (n₁, n₂, …?, n_k)-chromatic factorization.

     

CUSUM control charts based on likelihood ratio for preliminary analysis

To detect and estimate a shift in either the mean and the deviation or both for the preliminary analysis, the statistical process control (SPC) tool, the control chart based on the likelihood ratio test (LRT), is the most popular method. Sullivan and woodall pointed out the test statistic lrt(n1, n2) is approximately distributed as x2(2) as the sample size n,n1 and n2 are very large, and the value of n1 = 2,3,..., n - 2 and that of n2 = n - n1. So it is inevitable that n1 or n2 is not large. In this paper the limit distribution of lrt(n1, n2) for fixed n1 or n2 is figured out, and the exactly analytic formulae for evaluating the expectation and the variance of the limit distribution are also obtained. In addition, the properties of the standardized likelihood ratio statistic slr(n1, n) are discussed in this paper. Although slr(n1, n) contains the most important information, slr(i, n)(i≠n1) also contains lots of information. The cumulative sum (CUSUM) control chart can obtain more information in this condition. So we propose two CUSUM control charts based on the likelihood ratio statistics for the preliminary analysis on the individual observations. One focuses on detecting the shifts in location in the historical data and the other is more general in detecting a shift in either the location and the scale or both. Moreover, the simulated results show that the proposed two control charts are, respectively, superior to their competitors not only in the detection of the sustained shifts but also in the detection of some other out-of-control situations considered in this paper.     

Locating the peaks of solutions via the maximum principle II: A local version of the method of moving planes

Let Ω be a bounded, smooth domain in ?²ⁿ, n ≥ 2. The well‐known Moser‐Trudinger inequality ensures the nonlinear functional J_ρ(u) is bounded from below if and only if ρ ≤ ρ_2n := 2²ⁿn!(n ? 1)!ω_2n, where in , and ω_2n is the area of the unit sphere ??^{2n ? 1} in ?²ⁿ. In this paper, we prove the inf_u∈X J_ρ(u) is always attained for ρ ≤ ρ_2n. The existence of minimizers of J_ρ at the critical value ρ = ρ_2n is a delicate problem. The proof depends on the blowup analysis for a sequence of bubbling solutions. Here we develop a local version of the method of moving planes to exclude the boundary bubbling. The existence of minimizers for J_ρ at the critical value ρ = ρ_2n is in contrast to the case of two dimensions. © 2003 Wiley Periodicals, Inc.     

Super magic strength of a graph

By G(p, q) we denote a graph having p vertices and q edges, by V and E the vertex set and edge set of G respectively. A graph G(p, q) is said to have an edge magic labeling (valuation) with the constant (magic number) c(f) if there exists a one-to-one and onto function f: V ∪ E → {1, 2, …., p + q} such that f(u)+f(v)+f(uv) = c(f) for all uv ∈ E. An edge magic labeling f of G is called a super magic labeling if f(E) ={1, 2, …., q}. In this paper the concepts of the super magic and super magic strength of a graph are introduced. The super magic strength (sms) of a graph G is defined as the minimum of all constants c′(f) where the minimum is taken over all super magic labeling of G and is denoted by sms(G). This minimum is defined only if the graph has at least one such super magic labeling. In this paper, the super magic strength of some well known graphs P _2n , P _2n+1, K _1,n , B _n,n , < K _1,n : 2 >, P _n ² and (2 _{n + 1})P ₂, C _n and W _n are obtained, where P _n is a path on n vertices, K _1,n is a star graph on n+1 vertices, n-bistar B _n,n is the graph obtained from two copies of K _1,n by joining the centres of two copies of K _1,n by an edge e, if e is subdivided then B _n,n becomes < K _1,n : 2 >, (2 _{n + 1}) P ₂ is 2 _{n + 1} disjoint copies of P ₂, P _n ² is a square graph of P _n . C _n is a cycle on n vertices and W _n = C _n + K ₁ is wheel on n + 1 vertices.     

Multicolor bipartite Ramsey number of C4 and large Kn,n

Let br_k(C₄;K_{n, n}) be the smallest N such that if all edges of K_{N, N} are colored by k + 1 colors, then there is a monochromatic C₄ in one of the first k colors or a monochromatic K_{n, n} in the last color. It is shown that br_k(C₄;K_{n, n}) = Θ(n²/log²n) for k?3, and br₂(C₄;K_{n, n})≥c(n n/log²n)² for large n. The main part of the proof is an algorithm to bound the number of large K_{n, n} in quasi‐random graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 47‐54, 2011     

When the cartesian product of directed cycles is Hamiltonian

The cartesian product of two hamiltonian graphs is always hamiltonian. For directed graphs, the analogous statement is false. We show that the cartesian product C_n1 × C_n2 of directed cycles is hamiltonian if and only if the greatest common divisor (g.c.d.) d of n₁ and n₂ is at least two and there exist positive integers d₁, d₂ so that d₁ + d₂ = d and g.c.d. (n₁, d₁) = g.c.d. (n₂, d₂) = 1. We also discuss some number-theoretic problems motivated by this result.     

Balancing the n-Cube: A Census of Colorings

Weights of 1 or 0 are assigned to the vertices of the n-cube in n-dimensional Euclidean space. Such an n-cube is called balanced if its center of mass coincides precisely with its geometric center. The seldom-used n-variable form of Pólya's enumeration theorem is applied to express the number N _{n, 2k} of balanced configurations with 2k vertices of weight 1 in terms of certain partitions of 2k. A system of linear equations of Vandermonde type is obtained, from which recurrence relations are derived which are computationally efficient for fixed k. It is shown how the numbers N _{n, 2k} depend on the numbers A _{n, 2k} of specially restricted configurations. A table of values of N _{n, 2k} and A _{n, 2k} is provided for n = 3, 4, 5, and 6. The case in which arbitrary, nonnegative, integral weights are allowed is also treated. Finally, alternative derivations of the main results are developed from the perspective of superposition.     

Dependence of the wave-front speeds on the propagation direction

The dependence of the characteristic speeds of quasilinear hyperbolic systems on the propagation directionn is investigated. It is proved that any non-vanishing characteristic speedc(n) is the sum of a homogeneous functionc ₁ (n) and a positively homogeneous functionc ₂ (n). As a further result, ifc ₂ (n) is non-vanishing, then bothc ₂ (n)±c ₂ (n) are characteristic speeds.

---

Sommario Nel lavoro si analizza la dipendenza dalla direzione di propagazionen delle velocità caratteristiche associate ad un sistema iperbolico quasi lineare. Si prova che ogni velocità caratteristicac(n) non nulla è somma di una funzione omogeneac ₁ (n) e di una funzione positivamente omegeneac ₂(n). Come ulteriore risultato si ha che, sec ₂(n) è non nulla, allora entrambe le funzionic ₁(n)±c ₂(n) sono velocità caratteristiche.

     

Recovering fourier coefficients of some functions and factorization of integer numbers

It is shown that if a function determined on the segment [−1, 1] has a sufficiently good approximation by partial sums of its expansion over Legendre polynomial, then, given the function’s Fourier coefficients c _n for some subset of n ∈ [n ₁, n ₂], one can approximately recover them for all n ∈ [n ₁, n ₂]. A new approach to factorization of integer numbers is given as an application.     

Hamilton cycle rich two‐factorizations of complete graphs

For all integers n ≥ 5, it is shown that the graph obtained from the n‐cycle by joining vertices at distance 2 has a 2‐factorization is which one 2‐factor is a Hamilton cycle, and the other is isomorphic to any given 2‐regular graph of order n. This result is used to prove several results on 2‐factorizations of the complete graph K_n of order n. For example, it is shown that for all odd n ≥ 11, K_n has a 2‐factorization in which three of the 2‐factors are isomorphic to any three given 2‐regular graphs of order n, and the remaining 2‐factors are Hamilton cycles. For any two given 2‐regular graphs of even order n, the corresponding result is proved for the graph K_n ‐ I obtained from the complete graph by removing the edges of a 1‐factor. © 2004 Wiley Periodicals, Inc.     

Balanced Convex Partitions of Measures in ℝ2

 Let n≥2 be an integer and let μ₁ and μ₂ be measures in ℝ² such that each μ _i is absolutely continuous with respect to the Lebesgue measure and μ₁(ℝ²)=μ₂(ℝ²)=n. Let u≠0 be a vector on the plane. We show that if μ₁(B)=μ₂(B)=n for some bounded domain B, then there exist positive integers n ₁,n ₂ with n ₁+n ₂=n and disjoint open half-planes D ₁,D ₂ such that , μ₁(D ₁)=μ₂(D ₁)=n ₁ and μ₁(D ₂)=μ₂(D ₂)=n ₂; or there exist positive integers n ₁,n ₂,n ₃ with n ₁+n ₂+n ₃=n and disjoint open convex domains D ₁,D ₂,D ₃ such that , μ₁(D ₁)=μ₂(D ₁)=n ₁, μ₁(D ₂)= μ₂(D ₂)=n ₂, μ₁(D ₃)=μ₂(D ₃)=n ₃ and such that the ray is parallel to u. We also show a similar result for partitioning of point sets on the plane. Received: November 24, 1999 Final version received: February 9, 2001     

Dade's Invariant Conjecture for the Symplectic Group Sp4(2 n ) and the Special Unitary Group SU4(22n ) in Defining Characteristic

In this article, we verify Dade's projective invariant conjecture for the symplectic group Sp₄(2 ⁿ ) and the special unitary group SU₄(2²ⁿ ) in the defining characteristic, that is, in characteristic 2. Furthermore, we show that the Isaacs–Malle–Navarro version of the McKay conjecture holds for Sp₄(2 ⁿ ) and SU₄(2²ⁿ ) in the defining characteristic, that is, Sp₄(2 ⁿ ) and SU₄(2²ⁿ ) are good for the prime 2 in the sense of Isaacs, Malle, and Navarro.