Characterization of a class of graphs related to pairs of disjoint matchings

For a given graph consider a pair of disjoint matchings the union of which contains as many edges as possible. Furthermore, consider the ratio of the cardinalities of a maximum matching and the largest matching in those pairs. It is known that for any graph is the tight upper bound for this ratio. We characterize the class of graphs for which it is precisely . Our characterization implies that these graphs contain a spanning subgraph, every connected component of which is the minimal graph of this class.     

Vertex coloring acyclic digraphs and their corresponding hypergraphs

We consider vertex coloring of an acyclic digraph in such a way that two vertices which have a common ancestor in receive distinct colors. Such colorings arise in a natural way when bounding space for various genetic data for efficient analysis. We discuss the corresponding down-chromatic number and derive an upper bound as a function of , the maximum number of descendants of a given vertex, and the degeneracy of the corresponding hypergraph. Finally, we determine an asymptotically tight upper bound of the down-chromatic number in terms of the number of vertices of and .     

Maximum bipartite subgraphs of cubic triangle-free planar graphs

Thomassen recently proved, using the Tutte cycle technique, that if G is a 3-connected cubic triangle-free planar graph then G contains a bipartite subgraph with at least edges, improving the previously known lower bound . We extend Thomassen’s technique and further improve this lower bound to .     

Optical grooming with grooming ratio nine

Grooming uniform all-to-all traffic in optical ring networks with grooming ratio C requires the determination of graph decompositions of the complete graph into subgraphs each having at most C edges. The drop cost of such a grooming is the total number of vertices of nonzero degree in these subgraphs, and the grooming is optimal when the drop cost is minimum. The minimum drop cost is determined for grooming ratio 9. Previously this bound was shown to be met when with two exceptions and eleven additional possible exceptions for n, and also when with one exception and one possible exception for n. In this paper it is shown that the bound is met for all with four exceptions for n∈{8,11,14,17} and one possible exception for n=20. Using this result, it is further shown that when and n is sufficiently large, the bound is also met.     

Multifractal spectrum and generic properties of functions monotone in several variables

We study the singularity (multifractal) spectrum of continuous functions monotone in several variables. We find an upper bound valid for all functions of this type, and we prove that this upper bound is reached for generic functions monotone in several variables. Let be the set of points at which f has a pointwise exponent equal to h. For generic monotone functions f:d[0,1]→R, we have that for all h∈[0,1], and in addition, we obtain that the set is empty as soon as h>1. We also investigate the level set structure of such functions.     

On the eccentric connectivity index of a graph

If G is a connected graph with vertex set V, then the eccentric connectivity index of G, ξ^C(G), is defined as where is the degree of a vertex v and is its eccentricity. We obtain an exact lower bound on ξ^C(G) in terms of order, and show that this bound is sharp. An asymptotically sharp upper bound is also derived. In addition, for trees of given order, when the diameter is also prescribed, precise upper and lower bounds are provided.     

New bounds on the average distance from the Fermat–Weber center of a planar convex body

The Fermat–Weber center of a planar body Q is a point in the plane from which the average distance to the points in Q is minimal. We first show that for any convex body Q in the plane, the average distance from the Fermat–Weber center of Q to the points in Q is larger than , where Δ(Q) is the diameter of Q. This proves a conjecture of Carmi, Har-Peled and Katz. From the other direction, we prove that the same average distance is at most . The new bound substantially improves the previous bound of due to Abu-Affash and Katz, and brings us closer to the conjectured value of . We also confirm the upper bound conjecture for centrally symmetric planar convex bodies.     

A list heuristic for vertex cover

We analyze a list heuristic for the vertex cover problem that handles the vertices in a given static order based on the degree sequence. We prove an approximation ratio of at most for a nonincreasing degree sequence, and show that no ordering can achieve an approximation ratio of less than .     

Volumes and diophantine inequalities associated with decomposable forms

For homogeneous decomposable forms in n variables with real coefficients, we consider the associated volume of all real solutions to the inequality . We relate this to the number of integral solutions to the Diophantine inequality in the case where F has rational coefficients. We find quantities which bound the volume and which yield good upper bounds on the number of solutions to the Diophantine inequality in the rational case.     

Planarization and fragmentability of some classes of graphs

The coefficient of fragmentability of a class of graphs measures the proportion of vertices that need to be removed from the graphs in the class in order to leave behind bounded sized components. We have previously given bounds on this parameter for the class of graphs satisfying a given constant bound on maximum degree. In this paper, we give fragmentability bounds for some classes of graphs of bounded average degree, as well as classes of given thickness, the class of k-colourable graphs, and the class of n-dimensional cubes. In order to establish the fragmentability results for bounded average degree, we prove that the proportion of vertices that must be removed from a graph of average degree at most in order to leave behind a planar subgraph (in fact, a series-parallel subgraph) is at most , provided or the graph is connected and . The proof yields an algorithm for finding large induced planar subgraphs and (under certain conditions) a lower bound on the size of the induced planar subgraph it finds. This bound is similar in form to the one we found for a previous algorithm we developed for that problem, but applies to a larger class of graphs.     

Quality of move-optimal schedules for minimizing total weighted completion time

We study the minimum total weighted completion time problem on identical machines. We analyze a simple local search heuristic, moving jobs from one machine to another. The local optima can be shown to be approximately optimal with approximation ratio . In a special case, the approximation ratio is .     

Finite-sample inference with monotone incomplete multivariate normal data, II

We continue our recent work on inference with two-step, monotone incomplete data from a multivariate normal population with mean and covariance matrix . Under the assumption that is block-diagonal when partitioned according to the two-step pattern, we derive the distributions of the diagonal blocks of and of the estimated regression matrix, . We represent in terms of independent matrices; derive its exact distribution, thereby generalizing the Wishart distribution to the setting of monotone incomplete data; and obtain saddlepoint approximations for the distributions of and its partial Iwasawa coordinates. We prove the unbiasedness of a modified likelihood ratio criterion for testing , where is a given matrix, and obtain the null and non-null distributions of the test statistic. In testing , where and are given, we prove that the likelihood ratio criterion is unbiased and obtain its null and non-null distributions. For the sphericity test, , we obtain the null distribution of the likelihood ratio criterion. In testing we show that a modified locally most powerful invariant statistic has the same distribution as a Bartlett-Pillai-Nanda trace statistic in multivariate analysis of variance.     

An edge-reduction algorithm for the vertex cover problem

An approximation algorithm for the vertex cover problem is proposed with performance ratio on special graphs. On an arbitrary graph, the algorithm guarantees a vertex cover S₁ such that where S^∗ is an optimal cover and ξ is an error bound identified.