A linear algorithm for disjoint matchings in trees

An O(N) algorithm is presented which decides whether a given tree with N vertices possesses two disjoint matchings and finds them if they exist.     

A k-tableau characterization of k-Schur functions

We study k-Schur functions characterized by k-tableaux, proving combinatorial properties such as a k-Pieri rule and a k-conjugation. This new approach relies on developing the theory of k-tableaux, and includes the introduction of a weight-permuting involution on these tableaux that generalizes the Bender-Knuth involution. This work lays the groundwork needed to prove that the set of k-Schur Littlewood-Richardson coefficients contains the 3-point Gromov-Witten invariants; structure constants for the quantum cohomology ring.     

On the mutual embeddability of (2k, k, k − 1) and (2k − 1, k, k) quasi-residual designs

The complements of blocks containing a given point in a (2k ? 1, k, k) design, enlarged by this point, and the blocks not containing it, form a (2k ? 1, k, k) design. Likewise, the complements of blocks containing a given point in a (2k, k, k ? 1) design and the blocks not containing it, form a (2k ? 1, k, k) design. In this paper we show that if a quasi-residual (2k ? 1, k, k) design is obtained from an embeddable (2k ? 1, k, k) or (2k, k, k ? 1) design, then it is also embeddable, and describe an example of non-embeddable (12, 6, 5) design such that all (11, 6, 6) designs obtained from it are embeddable.     

Characterization of the graphs of the Johnson schemes G(3k, k) and G(3k + 1, k)

The graphs of the Johnson schemes G(3k, k) and G(3k + 1, k) are characterized by their parameters. In particular this finishes the characterization of the tetrahedral graphs G(n, 3).     

The signless Laplacian spectral radius of tricyclic graphs and trees with k pendant vertices

In this paper, we consider the following problem: of all tricyclic graphs or trees of order n with k pendant vertices (n,k fixed), which achieves the maximal signless Laplacian spectral radius?We determine the graph with the largest signless Laplacian spectral radius among all tricyclic graphs with n vertices and k pendant vertices. Then we show that the maximal signless Laplacian spectral radius among all trees of order n with k pendant vertices is obtained uniquely at T_n,k, where T_n,k is a tree obtained from a star K_1,k and k paths of almost equal lengths by joining each pendant vertex to one end-vertex of one path. We also discuss the signless Laplacian spectral radius of T_n,k and give some results.     

A note on the kth eigenvalue of trees

In [Linear Algebra Appl. 149 (1991) 19-34], Shao proved that for a tree T on n vertices, the kth eigenvalue

     

Characterization of k-variegated graphs, k ⩾ 3

A graph is said to be k-variegated if its vertex set can be partitioned into k equal parts such that each vertex is adjacent to exactly one vertex from every other part not containing it. Bednarek and Sanders [1] posed the problem of characterizing k-variegated graphs. V.N. Bhat-Nayak, S.A. Choudum and R.N. Naik [2] gave the characterization of 2-variegated graphs. In this paper we characterize k-variegated graphs for k ? 3.     

On 2-factors with k components

In this paper we study the minimum degree condition for a Hamiltonian graph to have a 2-factor with k components. By proving a conjecture of Faudree et al. [A note on 2-factors with two components, Discrete Math. 300 (2005) 218-224] we show the following. There exists a real number ε>0 such that for every integer k?2 there exists an integer n₀=n₀(k) such that every Hamiltonian graph G of order n?n₀ with has a 2-factor with k components.     

Spanning trees with leaf distance at least four

For a graph G, we denote by i(G) the number of isolated vertices of G. We prove that for a connected graph G of order at least five, if i(G–S) < |S| for all ?? ≠ S ? V(G), then G has a spanning tree T such that the distance in T between any two leaves of T is at least four. This result was conjectured by Kaneko in “Spanning trees with constrains on the leaf degree”, Discrete Applied Math, 115 (2001), 73–76. Moreover, the condition in the result is sharp in a sense that the condition i(G–S) < |S| cannot be replaced by i(G–S) ≤ |S|. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 83–90, 2007     

Perfect matchings in random bipartite graphs with minimal degree at least 2

We show that a random bipartite graph with n+n vertices and cn random edges, and minimum degree at least two, has a perfect matching whp . © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 26, 2005     

Sums and k-sums in abelian groups of order k

Let G be an abelian group of order k. How is the problem of minimizing the number of sums from a sequence of given length in G related to the problem of minimizing the number of k-sums? In this paper we show that the minimum number of k-sums for a sequence a₁,…,ar that does not have 0 as a k-sum is attained at the sequence b₁,…,br−k+1,0,…,0, where b₁,…,br−k+1 is chosen to minimise the number of sums without 0 being a sum. Equivalently, to minimise the number of k-sums one should repeat some value k−1 times. This proves a conjecture of Bollobás and Leader, and extends results of Gao and of Bollobás and Leader.     

A characterization of k-hyponormality via weak subnormality

An operator T acting on a Hilbert space is said to be weakly subnormal if there exists an extension acting on such that for all . When such partially normal extensions exist, we denote by m.p.n.e.(T) the minimal one. On the other hand, for k?1, T is said to be k-hyponormal if the operator matrix is positive. We prove that a 2-hyponormal operator T always satisfies the inequality T∗[T∗,T]T?‖T‖2[T∗,T], and as a result T is automatically weakly subnormal. Thus, a hyponormal operator T is 2-hyponormal if and only if there exists B such that BA∗=A∗T and is hyponormal, where A:=[T∗,T]1/2. More generally, we prove that T is (k+1)-hyponormal if and and only if T is weakly subnormal and m.p.n.e.(T) is k-hyponormal. As an application, we obtain a matricial representation of the minimal normal extension of a subnormal operator as a block staircase matrix.     

Total colorings of planar graphs with maximum degree at least 8

Planar graphs with maximum degree Δ ⩾ 8 and without 5- or 6-cycles with chords are proved to be (δ + 1)-totally-colorable. This work was supported by Natural Science Foundation of Ministry of Education of Zhejiang Province, China (Grant No. 20070441)