A degree bound on decomposable trees

A n-vertex graph is said to be decomposable if for any partition (λ₁,…,λ_p) of the integer n, there exists a sequence (V₁,…,V_p) of connected vertex-disjoint subgraphs with |V_i|=λ_i. In this paper, we focus on decomposable trees. We show that a decomposable tree has degree at most 4. Moreover, each degree-4 vertex of a decomposable tree is adjacent to a leaf. This leads to a polynomial time algorithm to decide if a multipode (a tree with only one vertex of degree greater than 2) is decomposable. We also exhibit two families of decomposable trees: arbitrary large trees with one vertex of degree 4, and trees with an arbitrary number of degree-3 vertices.     

Arbitrarily vertex decomposable suns with few rays

A graph G of order n is called arbitrarily vertex decomposable if for each sequence (n₁,…,n_k) of positive integers with n₁+?+n_k=n, there exists a partition (V₁,…,V_k) of the vertex set of G such that V_i induces a connected subgraph of order n_i, for all i=1,…,k. A sun with r rays is a unicyclic graph obtained by adding r hanging edges to r distinct vertices of a cycle. We characterize all arbitrarily vertex decomposable suns with at most three rays. We also provide a list of all on-line arbitrarily vertex decomposable suns with any number of rays.     

An Ore-type condition for arbitrarily vertex decomposable graphs

Let G be a graph of order n and r, 1≤r≤n, a fixed integer. G is said to be r-vertex decomposable if for each sequence (n₁,…,n_r) of positive integers such that n₁+?+n_r=n there exists a partition (V₁,…,V_r) of the vertex set of G such that for each i∈{1,…,r}, V_i induces a connected subgraph of G on n_i vertices. G is called arbitrarily vertex decomposable if it is r-vertex decomposable for each r∈{1,…,n}.In this paper we show that if G is a connected graph on n vertices with the independence number at most ⌈n/2⌉ and such that the degree sum of any pair of non-adjacent vertices is at least n−3, then G is arbitrarily vertex decomposable or isomorphic to one of two exceptional graphs. We also exhibit the integers r for which the graphs verifying the above degree-sum condition are not r-vertex decomposable.     

Mean matrices and infinite divisibility

We consider matrices M with entries m_ij = m(λ_i, λ_j) where λ₁, … ,λ_n are positive numbers and m is a binary mean dominated by the geometric mean, and matrices W with entries w_ij = 1/m (λ_i, λ_j) where m is a binary mean that dominates the geometric mean. We show that these matrices are infinitely divisible for several much-studied classes of means.     

Likelihood ratio orderings of spacings of heterogeneous exponential random variables

Let X₁,X₂,…,X_n be independent exponential random variables such that X_i has failure rate λ for i=1,…,p and X_j has failure rate λ^* for j=p+1,…,n, where p≥1 and q=n-p≥1. Denote by D_i:n(p,q)=X_i:n-X_i-1:n the ith spacing of the order statistics , where X_0:n≡0. It is shown that D_i:n(p,q)?_lrD_i+1:n(p,q) for i=1,…,n-1, and that if λ?λ^* then , and for i=1,…,n, where ?_lr denotes the likelihood ratio order. The main results are used to establish the dispersive orderings between spacings.     

A bijective enumeration of labeled trees with given indegree sequence

For a labeled tree on the vertex set {1,2,…,n}, the local direction of each edge (ij) is from i to j if i<j. For a rooted tree, there is also a natural global direction of edges towards the root. The number of edges pointing to a vertex is called its indegree. Thus the local (resp. global) indegree sequence λ=e₁¹e₂²… of a tree on the vertex set {1,2,…,n} is a partition of n−1. We construct a bijection from (unrooted) trees to rooted trees such that the local indegree sequence of a (unrooted) tree equals the global indegree sequence of the corresponding rooted tree. Combining with a Prüfer-like code for rooted labeled trees, we obtain a bijective proof of a recent conjecture by Cotterill and also solve two open problems proposed by Du and Yin. We also prove a q-multisum binomial coefficient identity which confirms another conjecture of Cotterill in a very special case.     

Decomposable critical tensors

Let λ = (λ₁, … , λ_t) be a partition of m and its conjugate partition. Denote also by λ the irreducible C-character of S_m associated with λ. Let V be a finite dimensional vector space over C.The reach of an element of the symmetry class of tensors V_λ (symmetry class of tensors associated with λ) is defined. The concept of critical element is introduced, as an element whose reach has dimension equal to . It is observed that, in ∧^mV, the notions of critical element and decomposable element coincide. Known results for decomposable elements of ∧^mV are extended to critical elements of V_λ. In particular, for a basis of ⊗^mV induced by a basis of V, generalized Plücker polynomials are constructed in a way that the set of their common roots contains the set of the families of components of decomposable critical elements of V_λ.     

Stochastic comparisons of order statistics from gamma distributions

Let (X₁,X₂,…,X_n) and (Y₁,Y₂,…,Y_n) be gamma random vectors with common shape parameter α(0<α?1) and scale parameters (λ₁,λ₂,…,λ_n), (μ₁,μ₂,…,μ_n), respectively. Let X₍₎=(X₍₁₎,X₍₂₎,…,X_(n)), Y₍₎=(Y₍₁₎,Y₍₂₎,…,Y_(n)) be the order statistics of (X₁,X₂,…,X_n) and (Y₁,Y₂,…,Y_n). Then (λ₁,λ₂,…,λ_n) majorizes (μ₁,μ₂,…,μ_n) implies that X₍₎ is stochastically larger than Y₍₎. However if the common shape parameter α>1, we can only compare the the first- and last-order statistics. Some earlier results on stochastically comparing proportional hazard functions are shown to be special cases of our results.     

Minmax subtree cover problem on cacti

Let G=(V,E) be a connected graph such that edges and vertices are weighted by nonnegative reals. Let p be a positive integer. The minmax subtree cover problem (MSC) asks to find a pair (X,T) of a partition X={X₁,X₂,…,X_p} of V and a set T of p subtrees T₁,T₂,…,T_p, each T_i containing X_i so as to minimize the maximum cost of the subtrees, where the cost of T_i is defined to be the sum of the weights of edges in T_i and the weights of vertices in X_i. In this paper, we propose an O(p²n) time (4-4/(p+1))-approximation algorithm for the MSC when G is a cactus.     

New upper bounds for Estrada index of bipartite graphs

Suppose G is a graph and λ₁,λ₂,…,λ_n are the eigenvalues of G. The Estrada index EE(G) of G is defined as the sum of e^λ_i, 1≤i≤n. In this paper some new upper bounds for the Estrada index of bipartite graphs are presented. We apply our result on a (4,6)-fullerene to improve our bound given in an earlier paper.     

Spectra of principal submatrices of nonnegative matrices

Let A be an n×n nonnegative matrix with the spectrum (λ₁,λ₂,…,λ_n) and let A₁ be an m×m principal submatrix of A with the spectrum (μ₁,μ₂,…,μ_m). In this paper we present some cases where the realizability of (μ₁,μ₂,…,μ_m,ν₁,ν₂,…,ν_s) implies the realizability of (λ₁,λ₂,…,λ_n,ν₁,ν₂,…,ν_s) and consider the question whether this holds in general. In particular, we show that the list

(λ₁,λ₂,…,λ_n,-μ₁,-μ₂,…,-μ_m)     

Graham’s pebbling conjecture on product of thorn graphs of complete graphs

The pebbling number of a graph G, f(G), is the least n such that, no matter how n pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of pebbling moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Let p₁,p₂,…,p_n be positive integers and G be such a graph, V(G)=n. The thorn graph of the graph G, with parameters p₁,p₂,…,p_n, is obtained by attaching p_i new vertices of degree 1 to the vertex u_i of the graph G, i=1,2,…,n. Graham conjectured that for any connected graphs G and H, f(G×H)≤f(G)f(H). We show that Graham’s conjecture holds true for a thorn graph of the complete graph with every by a graph with the two-pebbling property. As a corollary, Graham’s conjecture holds when G and H are the thorn graphs of the complete graphs with every .     

On 2-factors with cycles containing specified edges in a bipartite graph

Let k≥1 be an integer and G=(V₁,V₂;E) a bipartite graph with |V₁|=|V₂|=n such that n≥2k+2. In this paper it has been proved that if for each pair of nonadjacent vertices x∈V₁ and y∈V₂, , then for any k independent edges e₁,…,e_k of G, G has a 2-factor with k+1 cycles C₁,…,C_k+1 such that e_i∈E(C_i) and |V(C_i)|=4 for each i∈{1,…,k}. We shall also show that the conditions in this paper are sharp.     

Perturbing non-real eigenvalues of non-negative real matrices

Let σ=(ρ,b+ic,b-ic,λ₄,…,λ_n) be the spectrum of an entry non-negative matrix and t?0. Laffey [T. J. Laffey, Perturbing non-real eigenvalues of nonnegative real matrices, Electron. J. Linear Algebra 12 (2005) 73-76] has shown that σ=(ρ+2t,b-t+ic,b-t-ic,λ₄,…,λ_n) is also the spectrum of some nonnegative matrix. Laffey (2005) has used a rank one perturbation for small t and then used a compactness argument to extend the result to all nonnegative t. In this paper, a rank two perturbation is used to deduce an explicit and constructive proof for all t?0.     

The generalized Roper-Suffridge extension operator

Let f(z) be a normalized convex (starlike) function on the unit disc D. Let , where z=(z₁,z₂,…,z_n), z₁∈D, , p_i?1, i=2,…,n, are real numbers. In this note, we prove that Φ(f)(z)=(f(z₁),f′(z₁)^1/p₂z₂,…,f′(z₁)^1/p_nz_n) is a normalized convex (starlike) mapping on Ω, where we choose the power function such that (f′(z₁))^1/p_i|_z1=0=1, i=2,…,n. Some other related results are proved.     

A generalization of Sperner’s theorem and an application to graph orientations

A generalization of Sperner’s theorem is established: For a multifamily M={Y₁,…,Y_p} of subsets of {1,…,n} in which the repetition of subsets is allowed, a sharp lower bound for the number φ(M) of ordered pairs (i,j) satisfying i≠j and Y_i⊆Y_j is determined. As an application, the minimum average distance of orientations of complete bipartite graphs is determined.     

Construction of nonnegative symmetric matrices with given spectrum

Let σ = (λ₁, … , λ_n) be the spectrum of a nonnegative symmetric matrix A with the Perron eigenvalue λ₁, a diagonal entry c and let τ = (μ₁, … , μ_m) be the spectrum of a nonnegative symmetric matrix B with the Perron eigenvalue μ₁. We show how to construct a nonnegative symmetric matrix C with the spectrum

(λ₁+max{0,μ₁-c},λ₂,…,λ_n,μ₂,…,μ_m).     

Non-simultaneous blow-up of n components for nonlinear parabolic systems

This paper deals with non-simultaneous and simultaneous blow-up for radially symmetric solution (u₁,u₂,…,un) to heat equations coupled via nonlinear boundary (i=1,2,…,n). It is proved that there exist suitable initial data such that ui(i∈{1,2,…,n}) blows up alone if and only if qi+1<pi. All of the classifications on the existence of only two components blowing up simultaneously are obtained. We find that different positions (different values of k, i, n) of ui−k and ui leads to quite different blow-up rates. It is interesting that different initial data lead to different blow-up phenomena even with the same requirements on exponent parameters. We also propose that ui−k,ui−k+1,…,ui blow up simultaneously while the other ones remain bounded in different exponent regions. Moreover, the blow-up rates and blow-up sets are obtained.     

Two equivalent measures on weighted hypergraphs

Let H=(N,E,w) be a hypergraph with a node set N={0,1,…,n-1}, a hyperedge set E⊆2^N, and real edge-weights w(e) for e∈E. Given a convex n-gon P in the plane with vertices x₀,x₁,…,x_n-1 which are arranged in this order clockwisely, let each node i∈N correspond to the vertex x_i and define the area A_P(H) of H on P by the sum of the weighted areas of convex hulls for all hyperedges in H. For 0?i<j<k?n-1, a convex three-cut C(i,j,k) of N is {{i,…,j-1}, {j,…,k-1}, {k,…,n-1,0,…,i-1}} and its size c_H(i,j,k) in H is defined as the sum of weights of edges e∈E such that e contains at least one node from each of {i,…,j-1}, {j,…,k-1} and {k,…,n-1,0,…,i-1}. We show that the following two conditions are equivalent:

•

A_P(H)?A_P(H^′) for all convex n-gons P.

•

c_H(i,j,k)?c_H^′(i,j,k) for all convex three-cuts C(i,j,k).

From this property, a polynomial time algorithm for determining whether or not given weighted hypergraphs H and H^′ satisfy “A_P(H)?A_P(H^′) for all convex n-gons P” is immediately obtained.     

Dense Arbitrarily Vertex Decomposable Graphs

A graph G of order n is said to be arbitrarily vertex decomposable if for each sequence (n ₁, . . . , n _k ) of positive integers such that n ₁ + · · · + n _k = n there exists a partition (V ₁, . . . , V _k ) of the vertex set of G such that for each ${i \in \{1,\ldots,k\}}$ , V _i induces a connected subgraph of G on n _i vertices. The main result of the paper reads as follows. Suppose that G is a connected graph on n ≥ 20 vertices that admits a perfect matching or a matching omitting exactly one vertex. If the degree sum of any pair of nonadjacent vertices is at least n ? 5, then G is arbitrarily vertex decomposable. We also describe 2-connected arbitrarily vertex decomposable graphs that satisfy a similar degree sum condition.