The Fractional Chromatic Number Of The Categorical Product Of Graphs

We prove that the identity

Total Domination in Partitioned Graphs

We present results on total domination in a partitioned graph G = (V, E). Let γ _t (G) denote the total dominating number of G. For a partition , k ≥ 2, of V, let γ _t (G; V _i ) be the cardinality of a smallest subset of V such that every vertex of V _i has a neighbour in it and define the following

Upper Embeddability,Girth and the Degree-Sum of Nonadjacent Vertices

Let G be a 2-edge-connected simple graph with girth g, independence number α(G), and if one of the following two conditions holds

Undecidability of the centers of groups and group algebras

Let k ≧ 3 be an integer or k = ∞ and let K be a field. There is a recursive family of finitely presented groups G_n over a fixed finite alphabet with solvable word problem such that

Dirac’s Type Sufficient Conditions for Hamiltonicity and Pancyclicity

Let G = (V, E) be a any simple, undirected graph on n ≥ 3 vertices with the degree sequence . We consider the class of graphs satisfying the condition where , is a positive integer. It is known that is hamiltonian if θ ≤ δ. In this paper,

Pan-connectedness of graphs with large neighborhood unions

Let G be a simple graph with n vertices. For any , let , and , and and u and v has distance 2 in E(G)}. Let l ≥ 1 be an integer. A graph G on n ≥ l vertices is [l, n]-pan-connected if for any , and any integer m with l ≤ m ≤ n, G has a (u, v)-path of length m. In 1998, Wei and Zhu (Graphs Combinatorics 14:263–274, 1998) proved that for a three-connected graph on n ≥ 7 vertices, if NC(G) ≥ n − δ(G) + 1, then G is [6, n]-pan-connected. They conjectured that such graphs should be [5, n]-pan-connected. In this paper, we prove that for a three-connected graph on n ≥ 7 vertices, if NC ₂(G) ≥ n − δ(G) + 1, then G is [5, n]-pan-connected. Consequently, the conjecture of Wei and Zhu is proved as NC ₂(G) ≥ NC(G). Furthermore, we show that the lower bound is best possible and characterize all 2-connected graphs with NC ₂(G) ≥ n − δ(G) + 1 which are not [4, n]-pan-connected.      

On the central value of symmetric square L-functions

Let S _k (N, χ) be the space of cusp forms of weight k, level N and character χ. For let L(s, sym² f) be the symmetric square L-function and be the Rankin–Selberg square attached to f. For fixed k ≥ 2, N prime, and real primitive χ, asymptotic formulas for the first and second moment of the central value of L(s, sym² f) and over a basis of S _k (N, χ) are given as N → ∞. As an application it is shown that a positive proportion of the central values L(1/2, sym² f) does not vanish. The author was supported by NSERC grant 311664-05.     

The minimum degree threshold for perfect graph packings

Let H be any graph. We determine up to an additive constant the minimum degree of a graph G which ensures that G has a perfect H-packing (also called an H-factor). More precisely, let δ(H,n) denote the smallest integer k such that every graph G whose order n is divisible by |H| and with δ(G)≥k contains a perfect H-packing. We show that

Gauss-Bonnet Formula, Finiteness Condition, and Characterizations of Graphs Embedded in Surfaces

Let G be an infinite graph embedded in a closed 2-manifold, such that each open face of the embedding is homeomorphic to an open disk and is bounded by finite number of edges. For each vertex x of G, define the combinatorial curvature

Embedding graphs with bounded degree in sparse pseudorandom graphs

In this paper, we show the equivalence of somequasi-random properties for sparse graphs, that is, graphsG with edge densityp=|E(G)|/( ₂ ⁿ )=o(1), whereo(1)→0 asn=|V(G)|→∞. Our main result (Theorem 16) is the following embedding result. For a graphJ, writeN _J(x) for the neighborhood of the vertexx inJ, and letδ(J) andΔ(J) be the minimum and the maximum degree inJ. LetH be atriangle-free graph and setd _H=max{δ(J):J⊆H}. Moreover, putD _H=min{2d _H,Δ(H)}. LetC>1 be a fixed constant and supposep=p(n)≫n ⁻¹ D _H. We show that ifG is such that

(U(p, q), U(p − 1, q)) is a generalized Gelfand pair

Denote by G = U(p, q) the orthogonal group of the sesqui-linear quadratic form on and let H ₁ = U(p − 1, q) be the stabilizer of the first unit vector e ₁. Let H ₀ = U(1) and set H = H ₀ × H ₁. Define the character χ _l of H by where . Define the anti-involution σ on G by . In this note we show that any distribution T on G satisfying T(h ₁ gh ₂) = χ _l (h ₁ h ₂) T(g) (g ∈ G; h ₁, h ₂ ∈ H) is invariant under the anti-involution σ. This result implies that (G,  H ₁) is a generalized Gelfand pair.      

Remarks on Spectral Radius and Laplacian Eigenvalues of a Graph

Let G be a graph with n vertices, m edges and a vertex degree sequence (d ₁, d ₂,..., d _n ), where d ₁ ≥ d ₂ ≥ ... ≥ d _n . The spectral radius and the largest Laplacian eigenvalue are denoted by ϱ(G) and μ(G), respectively. We determine the graphs with

On locally solid topological lattice groups

Let (G, τ) be a commutative Hausdorff locally solid lattice group. In this paper we prove the following:

Maximum set of edges no two covered by a clique

Leth(G) be the largest number of edges of the graphG. no two of which are contained in the same clique. ForG without isolated vertices it is proved that ifh(G)≦5, thenχ( )≦h(G), but ifh(G)=6 thenχ( ) can be arbitrarily large.     

List Point Arboricity of Dense Graphs

Let G be a simple graph. The point arboricity ρ(G) of G is defined as the minimum number of subsets in a partition of the point set of G so that each subset induces an acyclic subgraph. The list point arboricity ρ _l (G) is the minimum k so that there is an acyclic L-coloring for any list assignment L of G which |L(v)| ≥ k. So ρ(G) ≤ ρ _l (G) for any graph G. Xue and Wu proved that the list point arboricity of bipartite graphs can be arbitrarily large. As an analogue to the well-known theorem of Ohba for list chromatic number, we obtain ρ _l (G + K _n ) = ρ(G + K _n ) for any fixed graph G when n is sufficiently large. As a consequence, if ρ(G) is close enough to half of the number of vertices in G, then ρ _l (G) = ρ(G). Particularly, we determine that , where K _2(n) is the complete n-partite graph with each partite set containing exactly two vertices. We also conjecture that for a graph G with n vertices, if then ρ _l (G) = ρ(G). Research supported by NSFC (No.10601044) and XJEDU2006S05.     

A construction of two distinct canonical sets of lifts of Brauer characters of a p-solvable group

In [5], Navarro defines the set , where Q is a p-subgroup of a p-solvable group G, and shows that if δ is the trivial character of Q, then Irr(G|Q, δ) provides a set of canonical lifts of IBr_p(G), the irreducible Brauer characters with vertex Q. Previously, in [2], Isaacs defined a canonical set of lifts B_π(G) of I_π(G). Both of these results extend the Fong-Swan Theorem to π-separable groups, and both construct canonical sets of lifts of the generalized Brauer characters. It is known that in the case that 2∈π, or if |G| is odd, we have B_π(G) = Irr(G|Q, 1_Q). In this note we give a counterexample to show that this is not the case when . It is known that if and χ∈B_π(G), then the constituents of χ_N are in B_π (N). However, we use the same counterexample to show that if , and χ∈Irr(G|Q, 1_Q) is such that θ ∈Irr(N) and [θ, χ _N] ≠ 0, then it is not necessarily the case that θ ∈Irr(N) inherits this property. Received: 17 October 2005     

An extension of almost sure central limit theorem for order statistics

Let {X _n ,n ≥ 1} be a sequence of i.i.d. random variables. Let M _n and m _n denote the first and the second largest maxima. Assume that there are normalizing sequences a _n  > 0, b _n and a nondegenerate limit distribution G, such that . Assume also that {d _k ,k ≥ 1} are positive weights obeying some mild conditions. Then for x > y we have

A Characterization of Some Classes of Harmonic Functions

In this paper we investigate harmonic Hardy-Orlicz and Bergman-Orlicz b _φ,α (B) spaces, using an identity of Hardy-Stein type. We also extend the notion of the Lusin property by introducing (φ, α)-Lusin property with respect to a Stoltz domain. The main result in the paper is as follows: Let be a nonnegative increasing convex function twice differentiable on (0, ∞), and u a harmonic function on the unit ball B in . Then the following statements are equivalent: