The greedy algorithm for domination in graphs of maximum degree 3

We show that for a connected graph with n nodes and e edges and maximum degree at most 3, the size of the dominating set found by the greedy algorithm is at most if , if , and if .     

On the complexity of digraph packings

Let be a fixed collection of digraphs. Given a digraph H, a -packing of H is a collection of vertex disjoint subgraphs of H, each isomorphic to a member of . For undirected graphs, Loebl and Poljak have completely characterized the complexity of deciding the existence of a perfect -packing, in the case that consists of two graphs one of which is a single edge on two vertices. We characterize -packing where consists of two digraphs one of which is a single arc on two vertices.     

The 2-dipath chromatic number of Halin graphs

A 2-dipath k-coloring f of an oriented graph is a mapping from to the color set {1,2,…,k} such that f(x)≠f(y) whenever two vertices x and y are linked by a directed path of length 1 or 2. The 2-dipath chromatic number of is the smallest k such that has a 2-dipath k-coloring. In this paper we prove that if is an oriented Halin graph, then . There exist infinitely many oriented Halin graphs such that .     

Structural equation modeling with near singular covariance matrices

Conventional structural equation modeling involves fitting a structural model to the sample covariance matrix . Due to collinearity or small samples with practical data, nonconvergences often occur in the estimation process. For a small constant a, this paper proposes to fit the structural model to the covariance matrix . When treating as the sample covariance matrix in the maximum likelihood (ML) procedure, consistent parameter estimates are still obtained. The asymptotic distributions of the parameter estimates and the corresponding likelihood ratio statistic are studied and compared to those by the conventional ML. Two rescaled statistics for the overall model evaluation with modeling are constructed. Empirical results imply that the estimates from modeling are more efficient than those of fitting the structural model to even when data are normally distributed. Simulations and real data examples indicate that modeling allows us to evaluate the overall model structure even when is literally singular. Implications of modeling in a broader context are discussed.