Decompositions of complete graphs and complete bipartite graphs into isomorphic supersubdivision graphs

A graph H is called a supersubdivison of a graph G if H is obtained from G by replacing every edge uv of G by a complete bipartite graph K_2,m (m may vary for each edge) by identifying u and v with the two vertices in K_2,m that form one of the two partite sets. We denote the set of all such supersubdivision graphs by SS(G). Then, we prove the following results.

1. Each non-trivial connected graph G and each supersubdivision graph HSS(G) admits an α-valuation. Consequently, due to the results of Rosa (in: Theory of Graphs, International Symposium, Rome, July 1966, Gordon and Breach, New York, Dunod, Paris, 1967, p. 349) and El-Zanati and Vanden Eynden (J. Combin. Designs 4 (1996) 51), it follows that complete graphs K_2cq+1 and complete bipartite graphs K_mq,nq can be decomposed into edge disjoined copies of HSS(G), for all positive integers m,n and c, where q=|E(H)|.

2. Each connected graph G and each supersubdivision graph in SS(G) is strongly n-elegant, where n=|V(G)| and felicitous.

3. Each supersubdivision graph in EASS(G), the set of all even arbitrary supersubdivision graphs of any graph G, is cordial.

Further, we discuss a related open problem.     

More on Stochastic Comparisons and Dependence among Concomitants of Order Statistics

For a sample of iid observations {(X_i, Y_i)} from an absolutely continuous distribution, the multivariate dependence of concomitants Y_[]=(Y_[1], Y_[2], …, Y_[n]) and the stochastic order of subsets of Y_[] are studied. If (X, Y) is totally positive dependent of order 2, Y_[] is multivariate totally positive dependent of order 2. If the conditional hazard rate function of Y given X, h_YX(yx), is decreasing in x for every y, Y_[] is multivariate right corner set increasing. And if Y is stochastically increasing in X, the concomitants are increasing in multivariate stochastic order.     

On <Emphasis Type="Italic">k</Emphasis>-th Power of Upper Bound Graphs

We consider k-th power of upper bound graphs. According to the characterization of upper bound graphs, we obtain a characterization of k-th power of upper bound graphs. That is, for a connected upper bound graph G, G^k is an upper bound graph if and only if for any pair of A^k -simplicial vertices s₁, s₂ such that , there exists a G^k -simplicial vertex s satisfying the conditions: and . Furthermore we also get some properties on squares of upper bound graphs.AMS Subject Classification: 05C62.     

MU-Estimation and Smoothing

In the M-estimation theory developed by Huber (1964, Ann. Math. Statist.43, 1449–1458), the parameter under estimation is the value of θ which minimizes the expectation of what is called a discrepancy measure (DM) δ(X, θ) which is a function of θ and the underlying random variable X. Such a setting does not cover the estimation of parameters such as the multivariate median defined by Oja (1983) and Liu (1990), as the value of θ which minimizes the expectation of a DM of the type δ(X₁, …, X_m, θ) where X₁, …, X_m are independent copies of the underlying random variable X. Arcones et al. (1994, Ann. Statist.22, 1460–1477) studied the estimation of such parameters. We call such an M-type MU-estimation (or μ-estimation for convenience). When a DM is not a differentiable function of θ, some complexities arise in studying the properties of estimators as well as in their computation. In such a case, we introduce a new method of smoothing the DM with a kernel function and using it in estimation. It is seen that smoothing allows us to develop an elegant approach to the study of asymptotic properties and possibly apply the Newton–Raphson procedure in the computation of estimators.     

Tight integral duality gap in the Chinese Postman problem

LetG = (V, E) be a graph and letw be a weight functionw:E Z ⁺. Let be an even subset of the vertices ofG. AT-cut is an edge-cutset of the graph which dividesT into two odd sets. AT-join is a minimal subset of edges that meets everyT-cut (a generalization of solutions to the Chinese Postman problem). The main theorem of this paper gives a tight upper bound on the difference between the minimum weightT-join and the maximum weight integral packing ofT-cuts. This difference is called the (T-join) integral duality gap. Let _w be the minimum weight of aT-join, and letv _w be the maximum weight of an integral packing ofT-cuts. IfF is a non-empty minimum weightT-join, andn _F is the number of components ofF, then we prove that _w —v _w n _F –1.This result unifies and generalizes Fulkerson's result for |T|=2 and Seymour's result for |T|= 4.For a certain integral multicommodity flow problem in the plane, which was recently proved to be NP-complete, the above result gives a solution such that for every commodity the flow is less than the demand by at most one unit.Research of the first author was partially supported by Technion V.P.R. Fund — C. and J. Bishop Research Fund, and Argentinian Research Fund.Part of this work was done as part of the author's D.Sc. Thesis in the Faculty of Industrial and Management Engineering, Technion — Israel Institute of Technology, Haifa. Research of this author was partially supported by Technion V.P.R. Fund — The Baltimore Fund for Industrial Engineering and Management Research.     

On the Conditional Variance for Scale Mixtures of Normal Distributions

For a scale mixture of normal vector, X=A^1/2G, where X, G ⁿ and A is a positive variable, independent of the normal vector G, we obtain that the conditional variance covariance, Cov(X₂ X₁), is always finite a.s. for m2, where X₁ ⁿ and m<n, and remains a.s. finite even for m=1, if and only if the square root moment of the scale factor is finite. It is shown that the variance is not degenerate as in the Gaussian case, but depends upon a function S_A, m(·) for which various properties are derived. Application to a uniform and stable scale of normal distributions are also given.     

Affine Hecke algebras and the Schubert calculus

Using a combinatorial approach that avoids geometry, this paper studies the structure of K_T(G/B), the T-equivariant K-theory of the generalized flag variety G/B. This ring has a natural basis (the double Grothendieck polynomials), where is the structure sheaf of the Schubert variety X_w. For rank two cases we compute the corresponding structure constants of the ring K_T(G/B) and, based on this data, make a positivity conjecture for general G which generalizes the theorems of M. Brion (for K(G/B)) and W. Graham (for H_T^*(G/B)). Let [X^λ]K_T(G/B) be the class of the homogeneous line bundle on G/B corresponding to the character of T indexed by λ. For general G we prove “Pieri–Chevalley formulas” for the products , , , and , where λ is dominant. By using the Chern character and comparing lowest degree terms the products which are computed in this paper also give results for the Grothendieck polynomials, double Schubert polynomials, and ordinary Schubert polynomials in, respectively K(G/B), H_T^*(G/B) and H^*(G/B).     

Conditions for -graphic sequences to be potentially -graphic

An r-graph is a loopless undirected graph in which no two vertices are joined by more than r edges. An r-complete graph on m+1 vertices, denoted by , is an r-graph on m+1 vertices in which each pair of vertices is joined by exactly r edges. A non-increasing sequence π=(d₁,d₂,…,d_n) of nonnegative integers is said to be r-graphic if it is realizable by an r-graph on n vertices. An r-graphic sequence π is said to be potentially -graphic if it has a realization containing as a subgraph. In this paper, some conditions for r-graphic sequences to be potentially -graphic are given. These are generalizations from 1-graphs to r-graphs of four theorems due to Rao [A.R. Rao, The clique number of a graph with given degree sequence, in: A.R. Rao (Ed.), Proc. Symposium on Graph Theory, in: I.S.I. Lecture Notes Series, vol. 4, MacMillan and Co. India Ltd., (1979), 251–267; A.R. Rao, An Erdös-Gallai type result on the clique number of a realization of a degree sequence (unpublished)] and Kézdy and Lehel [A.E. Kézdy, J. Lehel, Degree sequences of graphs with prescribed clique size, in: Y. Alavi et al., (Eds.), in: Combinatorics, Graph Theory, and Algorithms, vol. 2, New Issues Press, Kalamazoo Michigan, 1999, 535–544].     

Nonparametric Empirical Bayes Estimation of the Matrix Parameter of the Wishart Distribution

We consider independent pairs (X₁, Σ₁), (X₂, Σ₂), …, (X_n, Σ_n), where eachΣ_iis distributed according to some unknown density functiong(Σ) and, givenΣ_i=Σ,X_ihas conditional density functionq(xΣ) of the Wishart type. In each pair the first component is observable but the second is not. After the (n+1)th observationX_n+1is obtained, the objective is to estimateΣ_n+1corresponding toX_n+1. This estimator is called the empirical Bayes (EB) estimator ofΣ. An EB estimator ofΣis constructed without any parametric assumptions ong(Σ). Its posterior mean square risk is examined, and the estimator is demonstrated to be pointwise asymptotically optimal.     

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.     

F-Continuous Graphs

For a nontrivial connected graph F, the F-degree of a vertex in a graph G is the number of copies of F in G containing . A graph G is F-continuous (or F-degree continuous) if the F-degrees of every two adjacent vertices of G differ by at most 1. All P₃-continuous graphs are determined. It is observed that if G is a nontrivial connected graph that is F-continuous for all nontrivial connected graphs F, then either G is regular or G is a path. In the case of a 2-connected graph F, however, there always exists a regular graph that is not F-continuous. It is also shown that for every graph H and every 2-connected graph F, there exists an F-continuous graph G containing H as an induced subgraph.     

Minimum degree of minimal defect -extendable bipartite graphs

A near perfect matching is a matching saturating all but one vertex in a graph. If G is a connected graph and any n independent edges in G are contained in a near perfect matching, then G is said to be defect n-extendable. If for any edge e in a defect n-extendable graph G, G−e is not defect n-extendable, then G is minimal defect n-extendable. The minimum degree and the connectivity of a graph G are denoted by δ(G) and κ(G) respectively. In this paper, we study the minimum degree of minimal defect n-extendable bipartite graphs. We prove that a minimal defect 1-extendable bipartite graph G has δ(G)=1. Consider a minimal defect n-extendable bipartite graph G with n≥2, we show that if κ(G)=1, then δ(G)≤n+1 and if κ(G)≥2, then 2≤δ(G)=κ(G)≤n+1. In addition, graphs are also constructed showing that, in all cases but one, there exist graphs with minimum degree that satisfies the established bounds.     

On super edge-antimagic total labelings of

A graph G of order p and size q is called (a,d)-edge-antimagic total if there exists a bijective function f:V(G)E(G)→{1,2,…,p+q} such that the edge-weights w(uv)=f(u)+f(v)+f(uv), uvE(G), form an arithmetic sequence with first term a and common difference d. The graph G is said to be super (a,d)-edge-antimagic total if the vertex labels are 1,2,…,p. In this paper we study super (a,d)-edge-antimagic properties of mK_n, that is, of the graph formed by the disjoint union of m copies of K_n.     

Characterizations of multivariate normality II. Through linear regressions

It is established that a vector (X′₁, X′₂, …, X′_k) has a multivariate normal distribution if (i) for each X_i the regression on the rest is linear, (ii) the conditional distribution of X₁ about the regression does not depend on the rest of the variables, and (iii) the conditional distribution of X₂ about the regression does not depend on the rest of the variables, provided that the regression coefficients satisfy some more conditions that those given by [4]J. Multivar. Anal. 6 81–94].     

On Thompson's Theorem

Let p be a prime divisor of the order of a finite group G. Thompson (1970, J. Algebra14, 129–134) has proved the following remarkable result: a finite group G is p-nilpotent if the degrees of all its nonlinear irreducible characters are divisible by p (in fact, in that case G is solvable). In this note, we prove that a group G, having only one nonlinear irreducible character of p′-degree is a cyclic extension of Thompson's group. This result is a consequence of the following theorem: A nonabelian simple group possesses two nonlinear irreducible characters χ₁ and χ₂ of distinct degrees such that p does not divide χ₁(1)χ₂(1) (here p is arbitrary but fixed). Our proof depends on the classification of finite simple groups. Some properties of solvable groups possessing exactly two nonlinear irreducible characters of p′-degree are proved. Some open questions are posed.     

Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians

The Pfaffian method enumerating perfect matchings of plane graphs was discovered by Kasteleyn. We use this method to enumerate perfect matchings in a type of graphs with reflective symmetry which is different from the symmetric graphs considered in [J. Combin. Theory Ser. A 77 (1997) 67, MATCH—Commun. Math. Comput. Chem. 48 (2003) 117]. Here are some of our results: (1) If G is a reflective symmetric plane graph without vertices on the symmetry axis, then the number of perfect matchings of G can be expressed by a determinant of order |G|/2, where |G| denotes the number of vertices of G. (2) If G contains no subgraph which is, after the contraction of at most one cycle of odd length, an even subdivision of K_2,3, then the number of perfect matchings of G×K₂ can be expressed by a determinant of order |G|. (3) Let G be a bipartite graph without cycles of length 4s, s{1,2,…}. Then the number of perfect matchings of G×K₂ equals ∏(1+θ²)^m_θ, where the product ranges over all non-negative eigenvalues θ of G and m_θ is the multiplicity of eigenvalue θ. Particularly, if T is a tree then the number of perfect matchings of T×K₂ equals ∏(1+θ²)^m_θ, where the product ranges over all non-negative eigenvalues θ of T and m_θ is the multiplicity of eigenvalue θ.     

Approximation Algorithms for the Achromatic Number

The achromatic number for a graph G = V, E is the largest integer m such that there is a partition of V into disjoint independent sets {V₁, …, V_m} such that for each pair of distinct sets V_i, V_j, V_i V_j is not an independent set in G. Yannakakis and Gavril (1980, SIAM J. Appl. Math.38, 364–372) proved that determining this value for general graphs is NP-complete. For n-vertex graphs we present the first o(n) approximation algorithm for this problem. We also present an O(n^5/12) approximation algorithm for graphs with girth at least 5 and a constant approximation algorithm for trees.     

Second-Order Properties of a Two-Stage Fixed-Size Confidence Region for the Mean Vector of a Multivariate Normal Distribution

We consider the classical fixed-size confidence region estimation problem for the mean vectorμin theN_p(μ, Σ) population where Σ is unknown but positive definite. We writeλ₁for the largest characteristic root of Σ and assume thatλ₁is simple. Moreover, we suppose that, in many practical applications, we will often have available a numberλ*(>0) and that we can assumeλ₁>λ*. Given this addi- tional, and yet very minimal, knowledge regardingλ₁, the two-stage procedure of Chatterjee (Calcutta Statist. Assoc. Bull.8(1959a), 121–148;9(1959b), 20–28;11(1962), 144–159) is revised appropriately. The highlight in this paper involves the verification ofsecond-order propertiesassociated with such revised two-stage estimation techniques, along with the maintenance of the nominal confidence coefficient.     

A Chromatic Symmetric Function in Noncommuting Variables

Stanley (Advances in Math. 111, 1995, 166–194) associated with a graph G a symmetric function X _G which reduces to G's chromatic polynomial under a certain specialization of variables. He then proved various theorems generalizing results about , as well as new ones that cannot be interpreted on the level of the chromatic polynomial. Unfortunately, X _G does not satisfy a Deletion-Contraction Law which makes it difficult to apply the useful technique of induction. We introduce a symmetric function Y _G in noncommuting variables which does have such a law and specializes to X _G when the variables are allowed to commute. This permits us to further generalize some of Stanley's theorems and prove them in a uniform and straightforward manner. Furthermore, we make some progress on the (3 + 1)-free Conjecture of Stanley and Stembridge (J. Combin Theory (A) J. 62, 1993, 261–279).     

Spectra of Some Interesting Combinatorial Matrices Related to Oriented Spanning Trees on a Directed Graph

The Laplacian of a directed graph G is the matrix L(G) = O(G) –, A(G) where A(G) is the adjaceney matrix of G and O(G) the diagonal matrix of vertex outdegrees. The eigenvalues of G are the eigenvalues of A(G). Given a directed graph G we construct a derived directed graph D(G) whose vertices are the oriented spanning trees of G. Using a counting argument, we describe the eigenvalues of D(G) and their multiplicities in terms of the eigenvalues of the induced subgraphs and the Laplacian matrix of G. Finally we compute the eigenvalues of D(G) for some specific directed graphs G. A recent conjecture of Propp for D(H _n ) follows, where H _n stands for the complete directed graph on n vertices without loops.