The Convexity Number of a Graph

 For two vertices u and v of a connected graph G, the set I[u,v] consists of all those vertices lying on a u−v shortest path in G, while for a set S of vertices of G, the set I[S] is the union of all sets I[u,v] for u,v∈S. A set S is convex if I[S]=S. The convexity number con(G) of G is the maximum cardinality of a proper convex set of G. The clique number ω(G) is the maximum cardinality of a clique in G. If G is a connected graph of order n that is not complete, then n≥3 and 2≤ω(G)≤con(G)≤n−1. It is shown that for every triple l,k,n of integers with n≥3 and 2≤l≤k≤n−1, there exists a noncomplete connected graph G of order n with ω(G)=l and con(G)=k. Other results on convex numbers are also presented. Received: August 19, 1998 Final version received: May 17, 2000     

Asymptotic representations of solutions of nonautonomous ordinary differential equations with regularly varying nonlinearities

We obtain asymptotic representations as t ↑ ω, ω ≤ + ∞, for all possible types of P _ω(Y ₀, λ ₀)-solutions (where Y ₀ is zero or ±∞ and −∞ ≤ λ₀ ≤ +∞) of nonlinear differential equations y ⁽ⁿ⁾ = α ₀ p(t)φ(y), where α ₀ ∈ {−1, 1}, p: [a, ω[→]0,+∞[ is a continuous function, and φ is a continuous regularly varying function in a one-sided neighborhood of Y ₀.     

CLASSIFICATION OF COMPLETE 5-PARTITE GRAPHS AND CHROMATICITY OF 5-PARTITE GRAPHSWITH 5n VERTICES

For a graph G,P(G,λ)denotes the chromatic polynomial of G. Two graphs G and H are said to be chromatically equivalent,denoted by G-H,if P(G,λ)=p(H,λ). Let[G]= {H|H-G}. If [G]={G},then G is said to be chromatically unique. For a complete 5-partite graph G with 5n vertices, define θ(G)=(a(G,6)-2^n 1-2^n-1 5)/2n-2,where a(G,6) denotes the number of 6-independent partitions of G. In this paper, the authors show that θ(G)≥0 and determine all graphs with θ(G)= 0, 1, 2, 5/2, 7/2, 4, 17/4. By using these results the chromaticity of 5-partite graphs of the form G-S with θ(G)=0,1,2,5/2,7/2,4,17/4 is investigated,where S is a set of edges of G. Many new chromatically unique 5-partite graphs are obtained.     

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     

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.     

The Clique Numbers of Regular Graphs

 Let ω(G) be the clique number of a graph G. We prove that if G runs over the set of graphs with a fixed degree sequence d, then the values ω(G) completely cover a line segment [a,b] of positive integers. For an arbitrary graphic degree sequence d, we define min(ω,d) and max(ω,d) as follows:

Discrete spectrum in the gaps of a perturbed pseudorelativistic hamiltonian

The pseudorelativistic Hamiltonian is considered under wide conditions on potentials A(x), W(x). It is assumed that a real point λ is regular for G_1/2. Let G_1/2(α)=G_1/2−αV, where α>0, V(x)≥0, and V ∈L _d(ℝ^d). Denote by N(λ, α) the number of eigenvalues of G_1/2(t) that cross the point λ as t increases from 0 to α. A Weyl-type asymptotics is obtained for N(λ, α) as α→∞. Bibliography: 5 titles. To O. A. Ladyzhenskaya Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 249, 1997. pp. 102–117. Translated by A. B. Pushnitskii.     

Instances of the Conjecture of Chang

We consider various forms of the Conjecture of Chang. Part A constitutes an introduction. Donder and Koepke have shown that if ρ is a cardinal such that ρ ≧ ω₁, and (ρ⁺⁺,ρ⁺↠(ρ⁺, ρ), then 0⁺ exists. We obtain the same conclusion in Part B starting from some other forms of the transfer hypothesis. As typical corollaries, we get: Theorem A.Assume that there exists cardinals λ, κ, such that λ ≧ K ⁺ ≧ω₂ and (λ⁺, λ)↠(K ⁺,K. Then 0⁺ exists. Theorem B.Assume that there exists a singularcardinal κ such that(K ⁺,K↠(ω₁, ω₀. Then 0⁺ exists. Theorem C.Assume that (λ ⁺⁺, λ). Then 0⁺ exists (also ifK=ω ₀. Remark. Here, as in the paper of Donder and Koepke, “O⁺ exists” is a matter of saying that the hypothesis is strictly stronger than “L(μ) exists”. Of course, the same proof could give a few more sharps overL(μ), but the interest is in expecting more cardinals, coming from a larger core model. Theorem D.Assume that (λ ⁺⁺, λ)↠(K ⁺, K) and thatK≧ω ₁. Then 0⁺ exists. Remark 2. Theorem B is, as is well-known, false if the hypothesis “κ is singular” is removed, even if we assume thatK≧ω ₂, or that κ is inaccessible. We shall recall this in due place. Comments. Theorem B and Remark 2 suggest we seek the consistency of the hypothesis of the form:K ⁺, K↠(ω_n +1, ω_n), for κ singular andn≧0. 0266 0152 V 3 The consistency of several statements of this sort—a prototype of which is (N _ω+1,N _ω)↠(ω₁, ω₀) —have been established, starting with an hypothesis slightly stronger than: “there exists a huge cardinal”, but much weaker than: “there exists a 2-huge cardinal”. These results will be published in a joint paper by M. Magidor, S. Shelah, and the author of the present paper.     

On Lp-convergence of Grunwald interpolation

In this paper, the L_p-convergence of Grünwald interpolation G_n(f,x) based on the zeros of Jacobi polynomials J _n ^(α,β) (x)(−1<α,β<1) is considered. L_p-convergence (0<p<2) of Grünwald interpolation G_n(f,x) is proved for p·Max(α,β)<1. Moreover, L_p-convergence (p>0) of G_n(f,x) is obtained for −1<α,β≤0. Therefore, the results of [1] and [3–5] are improved.     

On the Upper Bounds of the Numbers of Perfect Matchings in Graphs with Given Parameters

Let φ(G),κ(G),α(G),χ(G),cl(G),diam(G)denote the number of perfect matchings,connectivity,independence number,chromatic number,clique number and diameter of a graph G,respectively.In this note,by constructing some extremal graphs,the following extremal problems are solved:1.max{φ(G):|V(G)|=2n,κ(G)≤k}=k[(2n-3)!!],2.max{φ(G):|V(G)|=2n,α(G)≥k}=[multiply from i=0 to k-1(2n-k-i)[(2n-2k-1)!!],3.max{φ(G):|V(G)|=2n,χ(G)≤k}=φ(T_(k,2n))T_(k,2n)is the Turán graph,that is a complete k-partite graphon 2n vertices in which all parts are as equal in size as possible,4.max{φ(G):|V(G)|=2n,cl(G)=2}=n1,5.max{φ(G):|V(G)|=2n,diam(G)≥2}=(2n-2)(2n-3)[(2n-5)!!],max{φ(G):|V(G)|=2n,diam(G)≥3}=(n-1)~2[(2n-5)!!].     

An extension of Hawkes theorem on the Hausdorff dimension of a Galton–Watson tree

Let ? be the genealogical tree of a supercritical multitype Galton–Watson process, and let Λ be the limit set of ?, i.e., the set of all infinite self-avoiding paths (called ends) through ? that begin at a vertex of the first generation. The limit set Λ is endowed with the metric d(ζ, ξ) = 2 ⁻ⁿ where n = n(ζ, ξ) is the index of the first generation where ζ and ξ differ. To each end ζ is associated the infinite sequence Φ(ζ) of types of the vertices of ζ. Let Ω be the space of all such sequences. For any ergodic, shift-invariant probability measure μ on Ω, define Ω_μ to be the set of all μ-generic sequences, i.e., the set of all sequences ω such that each finite sequence v occurs in ω with limiting frequency μ(Ω(v)), where Ω(v) is the set of all ω′?Ω that begin with the word v. Then the Hausdorff dimension of Λ∩Φ⁻¹ (Ω_μ) in the metric d is

Structures and Chromaticity of Extremal 3-Colourable Sparse Graphs

 Assume that G is a 3-colourable connected graph with e(G) = 2v(G) −k, where k≥ 4. It has been shown that s ₃(G) ≥ 2 ^{k −3}, where s _r (G) = P(G,r)/r! for any positive integer r and P(G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s ₃(G) < 2 ^{k −2}, then G contains at most v(G) −k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle C _k by a 2-tree. By using this result, we settle the problem of determining if W(n, s) is χ-unique, where W(n, s) is the graph obtained from the wheel W _n by deleting all but s consecutive spokes. Received: January 29, 1999 Final version received: April 8, 2000     

Large Monotone Paths in Graphs with Bounded Degree

 We prove that for every ε>0 and positive integer r, there exists Δ₀=Δ₀(ε) such that if Δ>Δ₀ and n>n(Δ,ε,r) then there exists a packing of K _n with ⌊(n−1)/Δ⌋ graphs, each having maximum degree at most Δ and girth at least r, where at most εn ² edges are unpacked. This result is used to prove the following: Let f be an assignment of real numbers to the edges of a graph G. Let α(G,f) denote the maximum length of a monotone simple path of G with respect to f. Let α(G) be the minimum of α(G,f), ranging over all possible assignments. Now let α_Δ be the maximum of α(G) ranging over all graphs with maximum degree at most Δ. We prove that Δ+1≥α_Δ≥Δ(1−o(1)). This extends some results of Graham and Kleitman [6] and of Calderbank et al. [4] who considered α(K _n ). Received: March 15, 1999?Final version received: October 22, 1999     

On the exponent of tensor categories coming from finite groups

We describe the exponent of a group-theoretical fusion category C = C(G, ω, F, α) associated to a finite group G in terms of group cohomology. We show that the exponent of C divides both e(ω)expG and (expG)², where e(ω) is the cohomological order of the 3-cocycle ω. In particular, expC divides (dim C)². This work was partially supported by CONICET, Fundación Antorchas, Agencia Córdoba Ciencia, ANPCyT and Secyt (UNC).     

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.     

On the total domination subdivision numbers in graphs

A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ _t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sd_γt (G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. Karami, Khoeilar, Sheikholeslami and Khodkar, (Graphs and Combinatorics, 2009, 25, 727–733) proved that for any connected graph G of order n ≥ 3, sd_{γ t} (G) ≤ 2γ _t (G) − 1 and posed the following problem: Characterize the graphs that achieve the aforementioned upper bound. In this paper we first prove that sd_{γ t} (G) ≤ 2α′(G) for every connected graph G of order n ≥ 3 and δ(G) ≥ 2 where α′(G) is the maximum number of edges in a matching in G and then we characterize all connected graphs G with sd_{γ t} (G)=2γ _t (G)−1.     

The weighted Herz-type Hardy spaces hK q α,p (ω1,ω2)

Let 1<q<∞, n(1−1/q)≤α<∞, 0<p<∞ and ω₁,ω₂ ɛA ₁(R ⁿ ) (the Muckenhoupt class). In this paper, the author introduce the weighted Herz-type Hardy spaces hk _q ^α,p (gw₁,ω₂) and present their atomic decomposition. Using the atomic decomposition, the author find out their dual spaces, establish the boundedness on these spaces of the pseudo-differential operators of order zero and show thatD(R ⁿ ), the class of C^∞(Rⁿ)-functions with compactly support, is dense inhK _q ^α,p (ω₁,ω₂) and there is a subsequence, which converges in distrbutional sense to some distribution ofhK _q ^α,p (ω₁,ω₂), of any bounded sequence inhK _q ^α,p (ω₁,ω₂). In addition, the author also set up the boundedness of some non-linear quantities in compensated compactness. Supported by the NECF and the NECF and the NNSF of China.     

A poisson formula for solvable Lie groups

Given a probability measure μ on a locally compact second countable groupG the space of bounded μ-harmonic functions can be identified withL ^∞(η, α) where (η, α) is a BorelG-space with a σ-finite quasiinvariant measure α. Our goal is to show that when μ is an arbitrary spread out probability measure on a connected solvable Lie groupG then the μ-boundary (η, α) is a contractive homogeneous space ofG. Our approach is based on a study of a class of strongly approximately transitive (SAT) actions ofG. A BorelG-space η with a σ-finite quasiinvariant measure α is called SAT if it admits a probability measurev≪α, such that for every Borel set A with α(A)≠0 and every ε>0 there existsg∈G with ν(gA)>1−ε. Every μ-boundary is a standard SATG-space. We show that for a connected solvable Lie group every standard SATG-space is transitive, characterize subgroupsH⊆G such that the homogeneous spaceG/H is SAT, and establish that the following conditions are equivalent forG/H: (a)G/H is SAT; (b)G/H is contractive; (c)G/H is an equivariant image of a μ-boundary.     

Bounds on the Total Restrained Domination Number of a Graph

Let G = (V, E) be a graph. A set S í V{S \subseteq V} is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex of V − S is adjacent to a vertex in V − S. The total restrained domination number of G, denoted by γ _tr (G), is the smallest cardinality of a total restrained dominating set of G. We show that if δ ≥ 3, then γ _tr (G) ≤ n − δ − 2 provided G is not one of several forbidden graphs. Furthermore, we show that if G is r − regular, where 4 ≤ r ≤ n − 3, then γ _tr (G) ≤ n − diam(G) − r + 1.     

Precise asymptotic formulas for variational eigencurves of semilinear two-parameter elliptic eigenvalue problems

We consider the two-parameter nonlinear eigenvalue problem?−Δu = μu − λ(u + u ^p + f(u)), u > 0 in Ω, u = 0 on ∂Ω,?where p>1 is a constant and μ,λ>0 are parameters. We establish the asymptotic formulas for the variational eigencurves λ=λ(μ,α) as μ→∞, where α>0 is a normalizing parameter. We emphasize that the critical case from a viewpoint of the two-term asymptotics of the eigencurve is p=3. Moreover, it is shown that p=5/3 is also a critical exponent from a view point of the three-term asymptotics when Ω is a ball or an annulus. This sort of criticality for two-parameter problems seems to be new. Received: February 9, 2002; in final form: April 3, 2002?Published online: April 14, 2003