Some results on distance two labelling of outerplanar graphs

Let G be an outerplanar graph with maximum degree △. Let χ（G^2） and A（G） denote the chromatic number of the square and the L（2, 1）-labelling number of G, respectively. In this paper we prove the following results： （1） χ（G^2） = 7 if △= 6; （2） λ（G） ≤ △ ＋5 if △ ≥ 4, and ）,（G）≤ 7 if △ = 3; and （3） there is an outerplanar graph G with △ = 4 such that ）λ（G） = 7. These improve some known results on the distance two labelling of outerplanar graphs.     

Super Connectivity of Line Graphs and Digraphs

The h-super connectivity κh and the h-super edge-connectivity λh are more refined network reliability indices than the conneetivity and the edge-connectivity. This paper shows that for a connected balanced digraph D and its line digraph L, if D is optimally super edge-connected, then κ1（L） = 2λ1 （D）, and that for a connected graph G and its line graph L, if one of κ1 （L） and λ（G） exists, then κ1（L） = λ2（G）. This paper determines that κ1（B（d, n） is equal to 4d- 8 for n = 2 and d ≥ 4, and to 4d-4 for n ≥ 3 and d ≥ 3, and that κ1（K（d, n）） is equal to 4d- 4 for d 〉 2 and n ≥ 2 except K（2, 2）. It then follows that B（d,n） and K（d, n） are both super connected for any d ≥ 2 and n ≥ 1.     

On K 1,k -factorization of bipartite multigraphs

A K1,k-factorization of λKm,n is a set of edge-disjoint K1,k-factors of λKm,n, which partition the set of edges of λKm,n. In this paper, it is proved that a sufficient condition for the existence of K1,k-factorization of λKm,n, whenever k is any positive integer, is that （1） m ≤ kn, （2） n ≤ km, （3） km-n = kn-m ≡ 0 （mod （k^2- 1）） and （4） λ（km-n）（kn-m） ≡ 0 （mod k（k- 1）（k^2 - 1）（m ＋ n））.     

Bound on <Emphasis Type="Italic">m</Emphasis>-restricted Edge Connectivity

An m-restricted edge cut is an edge cut that separates a connected graph into a disconnected one with no components having order less than m. m-restrict edge connectivity λm is the cardinality of a minimum m-restricted edge cut. Let G be a connected k-regular graph of order at least 2m that contains m-restricted edge cuts and X be a subgraph of G. Let θ(X) denote the number of edges with one end in X and the other not in X and ξm=min{θ(X) ;X is a connected vertex-induced subgraph of order m}.It is proved in this paper that if G has girth at least m/2 2,then λm≤ξm.The upper bound of λm is sharp.     

Some results on R 2-edge-connectivity of even regular graphs

Let G be a connected k(≥3)-regular graph with girth g. A set S of the edges in G is called an Rredge-cut if G-S is disconnected and comains neither an isolated vertex nor a one-degree vertex. The R2-edge-connectivity of G, denoted by λ^n(G), is the minimum cardinality over all R2-edge-cuts, which is an important measure for fault-tolerance of computer interconnection networks. In this paper, λ^n(G)=g(2k-2) for any 2k-regular connected graph G (≠K5) that is either edge-transitive or vertex-transitive and g≥5 is given.     

Optimization problems of the third edge-connectivity of graphs

The third edge-connectivity λ3(G) of a graph G is defined as the minimum cardinality over all sets of edges, if any, whose deletion disconnects G and each component of the resulting graph has at least 3 vertices. An upper bound has been established for λ3(G) whenever λ3(G) is well-defined. This paper first introduces two combinatorial optimization concepts, that is, maximality and superiority, of λ3(G), and then proves the Ore type sufficient conditions for G to be maximally and super third edge-connected. These concepts and results are useful in network reliability analysis.     

The total reducibility order of a polynomial in two variables

LetK be an algebraically closed field of characteristic zero. ForA ∈K[x, y] let σ(A) = {λ ∈K:A − λ is reducible}. For λ ∈ σ(A) letA − λ = ∏ _i=1 ^n(λ) A _iλ ^k _μ whereA _iλ are distinct primes. Let ϱ_λ(A) =n(λ) − 1 and let ρ(A) = Σ_λɛσ(A)ϱ_λ(A). The main result is the following: Theorem.If A ∈ K[x, y] is not a composite polynomial, then ρ(A) < degA.     

On projectively normal embeddings of generalk-gonal curves

Fix integersg, k andt witht>0,k≥3 andtk<g/2−1. LetX be a generalk-gonal curve of genusg andR∈Pic ^k (X) the uniqueg _k ¹ onX. SetL:=K _X⊗(R ^*)^⊗t.L is very ample. Leth _L:X→P(H ⁰(X, L)^*) be the associated embedding. Here we prove thath _L(X) is projectively normal. Ifk≥4 andtk<g/2−2 the curveh _L(X) is scheme-theoretically cut out by quadrics. The author was partially supported by MURST and GNSAGA of CNR (Italy).     

Cusp forms

LetG andH ⊂G be two real semisimple groups defined overQ. Assume thatH is the group of points fixed by an involution ofG. Letπ ⊂L ²(H\G) be an irreducible representation ofG and letf επ be aK-finite function. Let Γ be an arithmetic subgroup ofG. The Poincaré seriesP _f(g)=Σ_H∩ΓΓ f(γ{}itg) is an automorphic form on Γ\G. We show thatP _f is cuspidal in some cases, whenH ∩Γ\H is compact. Partially supported by NSF Grant # DMS 9103608.     

Homogenous projective factors for actions of semi-simple Lie groups

We analyze the structure of a continuous (or Borel) action of a connected semi-simple Lie group G with finite center and real rank at least 2 on a compact metric (or Borel) space X, using the existence of a stationary measure as the basic tool. The main result has the following corollary: Let P be a minimal parabolic subgroup of G, and K a maximal compact subgroup. Let λ be a P-invariant probability measure on X, and assume the P-action on (X,λ) is mixing. Then either λ is invariant under G, or there exists a proper parabolic subgroup Q⊂G, and a measurable G-equivariant factor map ϕ:(X,ν)→(G/Q,m), where ν=∫ _K kλdk and m is the K-invariant measure on G/Q. Furthermore, The extension has relatively G-invariant measure, namely (X,ν) is induced from a (mixing) probability measure preserving action of Q. Oblatum 14-X-1997 & 18-XI-1998 / Published online: 20 August 1999     

Counting models in universal Horn classes

Definen _K (λ) to be either ω, or the number of non-isomorphic models inK having cardinality α, whichever cardinal is larger. This paper contains a proof that for a congruence modular variety ⋎ of algebras of countable similarity type, there are only six possible functionsn _⋎. It is also proved that ifn _K (λ)≠2^λ for some λ, andK is a universal Horn class of models for a countable language, thenK must satisfy two conditions, one of which is quite restrictive and requires that the members ofK are all in a certain sense Abelian. Presented by B. Jonsson.     

A Shy Invariant of Graphs

 Moving from a well known result of Hammer, Hansen, and Simeone, we introduce a new graph invariant, say λ(G) referring to any graph G. It is a non-negative integer which is non-zero whenever G contains particular induced odd cycles or, equivalently, admits a particular minimum clique-partition. We show that λ(G) can be efficiently evaluated and that its determination allows one to reduce the hard problem of computing a minimum clique-cover of a graph to an identical problem of smaller size and special structure. Furthermore, one has α(G)≤θ(G)−λ(G), where α(G) and θ(G) respectively denote the cardinality of a maximum stable set of G and of a minimum clique-partition of G. Received: April 12, 1999 Final version received: September 15, 2000     

On the general additive divisor problem

We obtain a new upper bound for the sum Σ _h≤H Δ _k (N, h) when 1 ≤ H ≤ N, k ∈ ℕ, k ≥ 3, where Δ _k (N, h) is the (expected) error term in the asymptotic formula for Σ _N<n≤2N d _k (n)d _k (n + h), and d _k (n) is the divisor function generated by ζ(s) ^k . When k = 3, the result improves, for H ≥ N ^1/2, the bound given in a recent work of Baier, Browning, Marasingha and Zhao, who dealt with the case k = 3.     

Chromatic uniqueness of certain complete tripartite graphs

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. Liu et al. [Liu, R. Y., Zhao, H. X., Ye, C. F.: A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs. Discrete Math., 289, 175–179 (2004)], and Lau and Peng [Lau, G. C., Peng, Y. H.: Chromatic uniqueness of certain complete t-partite graphs. Ars Comb., 92, 353–376 (2009)] show that K(p − k, p − i, p) for i = 0, 1 are chromatically unique if p ≥ k + 2 ≥ 4. In this paper, we show that if 2 ≤ i ≤ 4, the complete tripartite graph K(p − k, p − i, p) is chromatically unique for integers k ≥ i and p ≥ k ²/4 + i + 1.     

A bound for Wilson's general theorem

Given any set K of positive integers and positive integer λ, let c(K,λ) denote the smallest integer such that v∈B(K,λ) for every integer v≥c(K,λ) that satisfies the congruences λv(v-1)≡0 (mod β(K) and λ(v-1)≡0 (mod α(K)). Let K0 be an equivalent set of K, k and k* be the smallest and the largest integers in K0. We prove that c(K,λ)≤exp exp{Q0}Qo=max{2(2p(ko)2-k2kk)p(ko)4,(Kk242y-k-2)(y2)}, whereand y=k*+k(k-1)+1.     

Extremal probabilities for Gaussian quadratic forms

 Denote by Q an arbitrary positive semidefinite quadratic form in centered Gaussian random variables such that E(Q)=1. We prove that for an arbitrary x>0, inf _Q P(Q≤x)=P(χ² _n /n≤x), where χ _n ² is a chi-square distributed rv with n=n(x) degrees of freedom, n(x) is a non-increasing function of x, n=1 iff x>x(1)=1.5364…, n=2 iff x[x(2),x(1)], where x(2)=1.2989…, etc., n(x)≤rank(Q). A similar statement is not true for the supremum: if 1<x<2 and Z ₁ ,Z ₂ are independent standard Gaussian rv's, then sup_0≤λ≤1/2 P{λZ ₁ ² +(1−λ)Z ₂ ² ≤x} is taken not at λ=0 or at λ=1/2 but at 0<λ=λ(x)<1/2, where λ(x) is a continuous, increasing function from λ(1)=0 to λ(2)=1/2, e.g. λ(1.5)=.15…. Applications of our theorems include asymptotic quantiles of U and V-statistics, signal detection, and stochastic orderings of integrals of squared Gaussian processes. Received: 24 June 2002 / Revised version: 26 January 2003 Published online: 15 April 2003 Research supported by NSA Grant MDA904-02-1-0091 Mathematics Subject Classification (2000): Primary 60E15, 60G15; Secondary 62G10     

Asymptotic Upper Bounds for Ramsey Functions

 We show that for any graph G with N vertices and average degree d, if the average degree of any neighborhood induced subgraph is at most a, then the independence number of G is at least Nf _{a +1}(d), where f _{a +1}(d)=∫₀ ¹(((1−t)^{1/( a +1)})/(a+1+(d−a−1)t))dt. Based on this result, we prove that for any fixed k and l, there holds r(K _k + _l ,K _n )≤ (l+o(1))n ^k /(logn) ^{k −1}. In particular, r(K _k , K _n )≤(1+o(1))n ^{k −1}/(log n) ^{k −2}. Received: May 11, 1998 Final version received: March 24, 1999     

On subgroups of the general linear group that contain a maximal nonsplit torus

The paper deals with the structure of intermediate subgroups of the general linear group GL(n, k) of degree n over a field k of odd characteristic that contain a nonsplit maximal torus related to a radical extension of degree n of the ground field k. The structure of ideal nets over a ring that determine the structure of intermediate subgroups containinga transvection is given. Let K = k( ⁿ?{d} ) K = k\left( {\sqrt[n]{d}} \right) be a radical degree-n extension of a field k of odd characteristic, and let T =(d) be a nonsplit maximal torus, which is the image of the multiplicative group of the field K under the regular embedding in G =GL(n, k). In the paper, the structure of intermediate subgroups H, T ≤ H ≤ G, that contain a transvection is studied. The elements of the matrices in the torus T = T (d) generate a subring R(d) in the field k.Let R be an intermediate subring, R(d) ⊆ R ⊆ k, d ∈ R. Let σ_R denote the net in which the ideal dR stands on the principal diagonal and above it and all entries of which beneath the principal diagonal are equal to R. Let σ^R denote the net in which all positions on the principal diagonal and beneath it are occupied by R and all entries above the principal diagonal are equal to dR. Let E(σ_R) be the subgroup generated by all transvections from the net group G(σ_R). In the paper it is proved that the product TE(σ_R) is a group (and thus an intermediate subgroup). If the net σ associated with an intermediate subgroup H coincides with σ_R,then TE(σ_R) ≤ H ≤ N(σ_R),where N(σ_R) is the normalizer of the elementary net group E(σ_R) in G. For the normalizer N(σ_R),the formula N(σ_R)= TG(σ^R) holds. In particular, this result enables one to describe the maximal intermediate subgroups. Bibliography: 13 titles.     

On Some Three-Color Ramsey Numbers

 In this paper we study three-color Ramsey numbers. Let K _i,j denote a complete i by j bipartite graph. We shall show that (i) for any connected graphs G ₁, G ₂ and G ₃, if r(G ₁, G ₂)≥s(G ₃), then r(G ₁, G ₂, G ₃)≥(r(G ₁, G ₂)−1)(χ(G ₃)−1)+s(G ₃), where s(G ₃) is the chromatic surplus of G ₃; (ii) (k+m−2)(n−1)+1≤r(K _1,k , K _1,m , K _n )≤ (k+m−1)(n−1)+1, and if k or m is odd, the second inequality becomes an equality; (iii) for any fixed m≥k≥2, there is a constant c such that r(K _k,m , K _k,m , K _n )≤c(n/logn), and r(C _2m , C _2m , K _n )≤c(n/logn) ^m/(m−1) for sufficiently large n. Received: July 25, 2000 Final version received: July 30, 2002 RID="*" ID="*" Partially supported by RGC, Hong Kong; FRG, Hong Kong Baptist University; and by NSFC, the scientific foundations of education ministry of China, and the foundations of Jiangsu Province Acknowledgments. The authors are grateful to the referee for his valuable comments. AMS 2000 MSC: 05C55     

Relatively hyperbolic extensions of groups and Cannon-Thurston maps

Let 1 → (K, K ₁) → (G, N _G (K ₁)) → (Q, Q ₁) → 1 be a short exact sequence of pairs of finitely generated groups with K ₁ a proper non-trivial subgroup of K and K strongly hyperbolic relative to K ₁. Assuming that, for all g ∈ G, there exists k _g ∈ K such that gK ₁ g ⁻¹ = k _g K ₁ k _g⁻¹, we will prove that there exists a quasi-isometric section s: Q → G. Further, we will prove that if G is strongly hyperbolic relative to the normalizer subgroup N _G (K ₁) and weakly hyperbolic relative to K ₁, then there exists a Cannon-Thurston map for the inclusion i: Γ _K → Γ _G .