Rainbow connection number and connected dominating sets

The rainbow connection number of a connected graph is the minimum number of colors needed to color its edges, so that every pair of its vertices is connected by at least one path in which no two edges are colored the same. In this article we show that for every connected graph on n vertices with minimum degree delta, the rainbow connection number is upper bounded by 3n/(delta + 1) + 3. This solves an open problem from Schiermeyer (Combinatorial Algorithms, Springer, Berlin/Hiedelberg, 2009, pp. 432437), improving the previously best known bound of 20n/delta (J Graph Theory 63 (2010), 185191). This bound is tight up to additive factors by a construction mentioned in Caro et al. (Electr J Combin 15(R57) (2008), 1). As an intermediate step we obtain an upper bound of 3n/(delta + 1) - 2 on the size of a connected two-step dominating set in a connected graph of order n and minimum degree d. This bound is tight up to an additive constant of 2. This result may be of independent interest. We also show that for every connected graph G with minimum degree at least 2, the rainbow connection number, rc(G), is upper bounded by Gc(G) + 2, where Gc(G) is the connected domination number of G. Bounds of the form diameter(G)?rc(G)?diameter(G) + c, 1?c?4, for many special graph classes follow as easy corollaries from this result. This includes interval graphs, asteroidal triple-free graphs, circular arc graphs, threshold graphs, and chain graphs all with minimum degree delta at least 2 and connected. We also show that every bridge-less chordal graph G has rc(G)?3.radius(G). In most of these cases, we also demonstrate the tightness of the bounds.

Maximum weight independent sets in hole- and dart-free graphs

The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. The complexity of the MWIS problem for hole-free graphs is unknown. In this paper, we first prove that the MWIS problem for (hole, dart, gem)-free graphs can be solved in O(n(3))-time. By using this result, we prove that the MWIS problem for (hole, dart)-free graphs can be solved in O(n(4))-time. Though the MWIS problem for (hole, dart, gem)-free graphs is used as a subroutine, we also give the best known time bound for the solvability of the MWIS problem in (hole, dart, gem)-free graphs. (C) 2012 Elsevier B.V. All rights reserved.

A numerical approach to determine the sufficiency of given boundary data sets for uniquely estimating interior elastic properties

We consider an inverse elasticity problem in which forces and displacements are known on the boundary and the material property distribution inside the body is to be found. In other words, we need to estimate the distribution of constitutive properties using the finite boundary data sets. Uniqueness of the solution to this problem is proved in the literature only under certain assumptions for a given complete Dirichlet-to-Neumann map. Another complication in the numerical solution of this problem is that the number of boundary data sets needed to establish uniqueness is not known even under the restricted cases where uniqueness is proved theoretically. In this paper, we present a numerical technique that can assess the sufficiency of given boundary data sets by computing the rank of a sensitivity matrix that arises in the Gauss-Newton method used to solve the problem. Numerical experiments are presented to illustrate the method.

A Compact and Compliant External Pipe-Crawling Robot

The focus of this paper is on the practical aspects of design, prototyping, and testing of a compact, compliant external pipe-crawling robot that can inspect a closely spaced bundle of pipes in hazardous environments and areas that are inaccessible to humans. The robot consists of two radially deployable compliant ring actuators that are attached to each other along the longitudinal axis of the pipe by a bidirectional linear actuator. The robot imitates the motion of an inchworm. The novel aspect of the compliant ring actuator is a spring-steel compliant mechanism that converts circumferential motion to radial motion of its multiple gripping pads. Circumferential motion to ring actuators is provided by two shape memory alloy (SMA) wires that are guided by insulating rollers. The design of the compliant mechanism is derived from a radially deployable mechanism. A unique feature of the design is that the compliant mechanism provides the necessary kinematic function within the limited annular space around the pipe and serves as the bias spring for the SMA wires. The robot has a control circuit that sequentially activates the SMA wires and the linear actuator; it also controls the crawling speed. The robot has been fabricated, tested, and automated. Its crawling speed is about 45 mm/min, and the weight is about 150 g. It fits within an annular space of a radial span of 15 mm to crawl on a pipe of 60-mm outer diameter.

Benchmarking recognition results on camera captured word image data sets

We have benchmarked the maximum obtainable recognition accuracy on five publicly available standard word image data sets using semi-automated segmentation and a commercial OCR. These images have been cropped from camera captured scene images, born digital images (BDI) and street view images. Using the Matlab based tool developed by us, we have annotated at the pixel level more than 3600 word images from the five data sets. The word images binarized by the tool, as well as by our own midline analysis and propagation of segmentation (MAPS) algorithm are recognized using the trial version of Nuance Omnipage OCR and these two results are compared with the best reported in the literature. The benchmark word recognition rates obtained on ICDAR 2003, Sign evaluation, Street view, Born-digital and ICDAR 2011 data sets are 83.9%, 89.3%, 79.6%, 88.5% and 86.7%, respectively. The results obtained from MAPS binarized word images without the use of any lexicon are 64.5% and 71.7% for ICDAR 2003 and 2011 respectively, and these values are higher than the best reported values in the literature of 61.1% and 41.2%, respectively. MAPS results of 82.8% for BDI 2011 dataset matches the performance of the state of the art method based on power law transform.

Covariance profiles: a signature representation for object sets

We consider the problem of extracting a signature representation of similar entities employing covariance descriptors. Covariance descriptors can efficiently represent objects and are robust to scale and pose changes. We posit that covariance descriptors corresponding to similar objects share a common geometrical structure which can be extracted through joint diagonalization. We term this diagonalizing matrix as the Covariance Profile (CP). CP can be used to measure the distance of a novel object to an object set through the diagonality measure. We demonstrate how CP can be employed on images as well as for videos, for applications such as face recognition and object-track clustering.

Mixing enhancement in a compact trapped vortex combustor

Previous studies on a single-cavity, compact trapped vortex combustor concept showed good flame stability for a wide range of flow conditions. However, achieving good mixing between cavity products and mainstream flow was still a major challenge. In the present study, a passive mixing enhancement strategy of using inclined struts along with a flow guide vane is presented and experimentally tested at atmospheric pressure conditions. Results show excellent mixing and consequently low values of the combustor exit pattern factor in the range of 0.1 and small flame lengths (57 times the main-duct depth). The pressure drop is small in the range of 0.35%, and NOx levels of the order of 12ppm are achieved. The flame stability is excellent, and combustion efficiency is reasonable in the range of 96%. The effectiveness of the proposed strategy is explained on the basis of in-situ OH chemiluminescence images and prior numerical simulations of the resulting complex flow field. The flow guide vane is observed to lead to a counterclockwise cavity vortex, which is conducive to the rise of cavity combustion products along the inclined struts and subsequent mixing with the mainstream flow.

Exponential compact higher order scheme and their stability analysis for unsteady convection-diffusion equations

Exponential compact higher-order schemes have been developed for unsteady convection-diffusion equation (CDE). One of the developed scheme is sixth-order accurate which is conditionally stable for the Peclet number 0 <= Pe <= 2.8 and the other is fourth-order accurate which is unconditionally stable. Schemes for two-dimensional (2D) problems are made to use alternate direction implicit (ADI) algorithm. Example problems are solved and the numerical solutions are compared with the analytical solutions for each case.

Compact polarization dependent EBG surface with fractal boundary patches

Patches with variants of fractal Minkowski curves as boundaries are used here to design a polarization dependent electromagnetic bandgap surface. Reflection phases of the proposed structure depends upon the polarization state of the incident wave and frequency. The phase difference between the x-polarized and y-polarized components of the reflected wave can be as high as 200 degrees and this is achieved without excessive increase in unit cell dimensions and vias. The performance of the surface is analyzed numerically using CST microwave studio. The potential applications of the surface are in polarization conversion surfaces, polarimetric radar calibration, and RCS reduction.

Compact in-plane dual-axis spring-steel accelerometer

Presented in this paper is an improvement over a spring-steel dual-axis accelerometer that we had reported earlier.The fabrication process (which entails wire-cut electro discharge machining of easily accessible and inexpensive spring-steelfoil) and the sensing of the displacement (which is done using off-the-shelf Hall-effect sensors) remain the same. Theimprovements reported here are twofold: (i) the footprint of the packaged accelerometer is reduced from 80 mm square to 40mm square, and (ii) almost perfect de-coupling and symmetry are achieved between the two in-plane axes of the packageddevice as opposed to the previous embodiment where this was not the case. Good linearity with about 40 mV/g was measuredalong both the in-plane axes over a range of 0.1 to 1 g. The first two natural frequencies of the devices are at 30 Hz and 100Hz, respectively, as per the experiment. The highlights of this work are cost-effective processing, easy integration of the Hall-effect sensing capability on a customised printed circuit board, and inexpensive packaging without overly compromising eitherthe overall size or the sensitivity of the accelerometer. Through this work, we have reaffirmed the practicability of spring-steelaccelerometers towards the eventual goal of making it compete with micro machined silicon accelerometers in terms of sizeand performance. The cost is likely to be much lower for the spring-steel accelerometers than that of silicon accelerometers, especially when the volume of production is low and the sensor is to be used as a single packaged unit.

Fixed-orientation equilateral triangle matching of point sets

Given a point set P and a class C of geometric objects, G(C)(P) is a geometric graph with vertex set P such that any two vertices p and q are adjacent if and only if there is some C is an element of C containing both p and q but no other points from P. We study G(del)(P) graphs where del is the class of downward equilateral triangles (i.e., equilateral triangles with one of their sides parallel to the x-axis and the corner opposite to this side below that side). For point sets in general position, these graphs have been shown to be equivalent to half-Theta(6) graphs and TD-Delaunay graphs. The main result in our paper is that for point sets P in general position, G(del)(P) always contains a matching of size at least vertical bar P vertical bar-1/3] and this bound is tight. We also give some structural properties of G(star)(P) graphs, where is the class which contains both upward and downward equilateral triangles. We show that for point sets in general position, the block cut point graph of G(star)(P) is simply a path. Through the equivalence of G(star)(P) graphs with Theta(6) graphs, we also derive that any Theta(6) graph can have at most 5n-11 edges, for point sets in general position. (C) 2013 Elsevier B.V. All rights reserved.

Combining data sets of satellite-retrieved products for basin-scale water balance study: 2. Evaluation on the Mississippi Basin and closure correction model

In this study, we applied the integration methodology developed in the companion paper by Aires (2014) by using real satellite observations over the Mississippi Basin. The methodology provides basin-scale estimates of the four water budget components (precipitation P, evapotranspiration E, water storage change Delta S, and runoff R) in a two-step process: the Simple Weighting (SW) integration and a Postprocessing Filtering (PF) that imposes the water budget closure. A comparison with in situ observations of P and E demonstrated that PF improved the estimation of both components. A Closure Correction Model (CCM) has been derived from the integrated product (SW+PF) that allows to correct each observation data set independently, unlike the SW+PF method which requires simultaneous estimates of the four components. The CCM allows to standardize the various data sets for each component and highly decrease the budget residual (P - E - Delta S - R). As a direct application, the CCM was combined with the water budget equation to reconstruct missing values in any component. Results of a Monte Carlo experiment with synthetic gaps demonstrated the good performances of the method, except for the runoff data that has a variability of the same order of magnitude as the budget residual. Similarly, we proposed a reconstruction of Delta S between 1990 and 2002 where no Gravity Recovery and Climate Experiment data are available. Unlike most of the studies dealing with the water budget closure at the basin scale, only satellite observations and in situ runoff measurements are used. Consequently, the integrated data sets are model independent and can be used for model calibration or validation.

Third post-Newtonian gravitational waveforms for compact binary systems in general orbits: Instantaneous terms

We compute the instantaneous contributions to the spherical harmonic modes of gravitational waveforms from compact binary systems in general orbits up to the third post-Newtonian (PN) order. We further extend these results for compact binaries in quasielliptical orbits using the 3PN quasi-Keplerian representation of the conserved dynamics of compact binaries in eccentric orbits. Using the multipolar post-Minkowskian formalism, starting from the different mass and current-type multipole moments, we compute the spin-weighted spherical harmonic decomposition of the instantaneous part of the gravitational waveform. These are terms which are functions of the retarded time and do not depend on the history of the binary evolution. Together with the hereditary part, which depends on the binary's dynamical history, these waveforms form the basis for construction of accurate templates for the detection of gravitational wave signals from binaries moving in quasielliptical orbits.

Construction of Singer Subgroup Orbit Codes Based on Cyclic Difference Sets

A recent approach for the construction of constant dimension subspace codes, designed for error correction in random networks, is to consider the codes as orbits of suitable subgroups of the general linear group. In particular, a cyclic orbit code is the orbit of a cyclic subgroup. Hence a possible method to construct large cyclic orbit codes with a given minimum subspace distance is to select a subspace such that the orbit of the Singer subgroup satisfies the distance constraint. In this paper we propose a method where some basic properties of difference sets are employed to select such a subspace, thereby providing a systematic way of constructing cyclic orbit codes with specified parameters. We also present an explicit example of such a construction.

L-infinity norms of holomorphic modular forms in the case of compact quotient

We prove a sub-convex estimate for the sup-norm of L-2-normalized holomorphic modular forms of weight k on the upper half plane, with respect to the unit group of a quaternion division algebra over Q. More precisely we show that when the L-2 norm of an eigenfunction f is one, parallel to f parallel to(infinity) <<(epsilon) k(1/2-1/33+epsilon) for any epsilon > 0 and for all k sufficiently large.