Vertex splitting and connectivity augmentation in hypergraphs

We consider problems of splitting and connectivity augmentation in hypergraphs. In a hypergraph G = (V +s, E), to split two edges su, sv, is to replace them with a single edge uv. We are interested in doing this in such a way as to preserve a defined level of connectivity in V . The splitting technique is often used as a way of adding new edges into a graph or hypergraph, so as to augment the connectivity to some prescribed level. We begin by providing a short history of work done in this area. Then several preliminary results are given in a general form so that they may be used to tackle several problems. We then analyse the hypergraphs G = (V + s, E) for which there is no split preserving the local-edge-connectivity present in V. We provide two structural theorems, one of which implies a slight extension to Mader’s classical splitting theorem. We also provide a characterisation of the hypergraphs for which there is no such “good” split and a splitting result concerned with a specialisation of the local-connectivity function. We then use our splitting results to provide an upper bound on the smallest number of size-two edges we must add to any given hypergraph to ensure that in the resulting hypergraph we have λ(x, y) ≥ r(x, y) for all x, y in V, where r is an integer valued, symmetric requirement function on V*V. This is the so called “local-edge-connectivity augmentation problem” for hypergraphs. We also provide an extension to a Theorem of Szigeti, about augmenting to satisfy a requirement r, but using hyperedges. Next, in a result born of collaborative work with Zoltán Király from Budapest, we show that the local-connectivity augmentation problem is NP-complete for hypergraphs. Lastly we concern ourselves with an augmentation problem that includes a locational constraint. The premise is that we are given a hypergraph H = (V,E) with a bipartition P = {P1, P2} of V and asked to augment it with size-two edges, so that the result is k-edge-connected, and has no new edge contained in some P(i). We consider the splitting technique and describe the obstacles that prevent us forming “good” splits. From this we deduce results about which hypergraphs have a complete Pk-split. This leads to a minimax result on the optimal number of edges required and a polynomial algorithm to provide an optimal augmentation.

Poly[(2,2 '-bipyridine-kappa N-2,N ')-(mu(2)-dihydrogen phosphato-kappa O-2 : O ')-(mu(2)-hydrogen phosphato-kappa O-2 : O ')-aluminium(III)], Al(2,2 '/bipy)-(HPO4)(H2PO4), a layered inorganic - organic hybrid material

The title compound, [Al(HPO4)(H2PO4)(C10H8N2)]n, consists of AlO4N2 octahedra vertex-linked to H2PO4 and HPO4 tetrahedra to form layers based on a (4,12)- net. The layers stack in an AAA fashion, held in place by pi-pi interactions between 2,2 '-bipyridine molecules coordinated to Al atoms in adjacent layers.

Ruthenium complexes of C,C '-bis(ethynyl)carboranes: an investigation of electronic interactions mediated by spherical pseudo-aromatic spacers

The complexes [Ru(1-C=C-1,10-C2B8H9)(dppe)Cp*] (3a), [Ru(1-C C-1,12-C2B10H11)(dppe)-Cp*] (3b), [{Ru(dppe)Cp*}(2){mu-1,10-(C C)(2)-1,10-C2B8H8}] (4a) and [{Ru(dppe)Cp*}(2){mu-1,12-(C C)2- 1,12-C2B10-H-10}] (4b), which form a representative series of mono- and bimetallic acetylide complexes featuring 10- and 12-vertex carboranes embedded within the dethynyl bridging ligand, have been prepared and structurally characterized. In addition, these compounds have been examined spectroscopically (UV-is-NIR, IR) in all accessible redox states. The significant separation of the two, one-electron anodic waves observed in the cyclic voltammograms of the bimetallic complexes 4a and 4b is largely independent of the nature of the electrolyte and is attributed to stabilization of the intermediate redox products [4a](+) and [4b](+) through interactions between the metal centers across a distance of ca. 12.5 angstrom. The mono-oxidized bimetallic complexes (4a](+) and [4b](+) exhibit spectroscopic properties consistent with a description of these species in terms of valence-localized (class II) mixed-valence compounds, including a unique low-energy electronic absorption band, attributed to an, IVCT-type transition that tails into the IR region. DFT calculations with model systems [4a-H](+) and [4b-H](+) featuring simplified ligand sets reproduce the observed spectroscopic data and localized electronic structures for the mixed-valence cations [4a](+) and [4b](+).

Synthesis and crystal structure of a 3-D zinc phosphate, [C5N2H14][Zn-2(PO3(OH))(3)], containing (4.8) net sheets

A new 3-D zinc phosphate, [C5N2H14][Zn-2(PO3(OH))(3)], has been synthesised under solvothermal conditions in the presence of 1-methylpiperazine. The structure, determined by single-crystal X-ray diffraction at 293 K (RMM = 520.9, orthorhombic, space group P2(1)2(1)2(1); a = 10.0517(2) &ANGS;, b = 10.4293(2) &ANGS; and c = 14.9050(5) &ANGS;; V = 1562.52 &ANGS;(3); Z = 4; R(F) = 2.60%, wR(F) = 2.93%), consists of vertex linked ZnO4 and PO3(OH) tetrahedra assembled into (4.8) net sheets which in turn are linked through further PO3(OH) units to generate a 3-D framework. 1-Methylpiperazinium cations reside within the 3-D channel system, held in place by a strong network of hydrogen bonds. The (4.8) net sheets occur in a number of zeolite structures e.g. ABW and GIS and related zinc phosphate phases. © 2004 Academie des sciences. Published by Elsevier SAS. All rights reserved.

A new solution of the rendering equation with stratified Monte Carlo approach

This paper is turned to the advanced Monte Carlo methods for realistic image creation. It offers a new stratified approach for solving the rendering equation. We consider the numerical solution of the rendering equation by separation of integration domain. The hemispherical integration domain is symmetrically separated into 16 parts. First 9 sub-domains are equal size of orthogonal spherical triangles. They are symmetric each to other and grouped with a common vertex around the normal vector to the surface. The hemispherical integration domain is completed with more 8 sub-domains of equal size spherical quadrangles, also symmetric each to other. All sub-domains have fixed vertices and computable parameters. The bijections of unit square into an orthogonal spherical triangle and into a spherical quadrangle are derived and used to generate sampling points. Then, the symmetric sampling scheme is applied to generate the sampling points distributed over the hemispherical integration domain. The necessary transformations are made and the stratified Monte Carlo estimator is presented. The rate of convergence is obtained and one can see that the algorithm is of super-convergent type.

Fault tolerance of Mobius cubes under two forbidden fault set models

An n-dimensional Mobius cube, 0MQ(n) or 1MQ(n), is a variation of n-dimensional cube Q(n) which possesses many attractive properties such as significantly smaller communication delay and stronger graph-embedding capabilities. In some practical situations, the fault tolerance of a distributed memory multiprocessor system can be measured more precisely by the connectivity of the underlying graph under forbidden fault set models. This article addresses the connectivity of 0MQ(n)/1MQ(n), under two typical forbidden fault set models. We first prove that the connectivity of 0MQ(n)/1MQ(n) is 2n - 2 when the fault set does not contain the neighborhood of any vertex as a subset. We then prove that the connectivity of 0MQ(n)/1MQ(n) is 3n - 5 provided that the neighborhood of any vertex as well as that of any edge cannot fail simultaneously These results demonstrate that 0MQ(n)/1MQ(n) has the same connectivity as Q(n) under either of the previous assumptions.

Diameter of parallelogramic honeycomb torus

The determination of the diameter of an interconnection network is essential in evaluating the performance of the network. Parallelogramic honeycomb torus is an attractive alternative to classical torus network due to smaller vertex degree, and hence, lower implementation cost. In this paper, we present the expression for the diameter of a parallelogramic, honeycomb torus, which extends a known result about rhombic: honeycomb torus. (c) 2005 Elsevier Ltd. All rights reserved.

Synthesis and crystal structure of a 3-D zinc phosphate, [C5N2H14][Zn2(PO3(OH))3], containing (4.8) net sheets

A new 3-D zinc phosphate, [C5N2H14][Zn-2(PO3(OH))(3)], has been synthesised under solvothermal conditions in the presence of 1-methylpiperazine. The structure, determined by single-crystal X-ray diffraction at 293 K (RMM = 520.9, orthorhombic, space group P2(1)2(1)2(1); a = 10.0517(2) &ANGS;, b = 10.4293(2) &ANGS; and c = 14.9050(5) &ANGS;; V = 1562.52 &ANGS;(3); Z = 4; R(F) = 2.60%, wR(F) = 2.93%), consists of vertex linked ZnO4 and PO3(OH) tetrahedra assembled into (4.8) net sheets which in turn are linked through further PO3(OH) units to generate a 3-D framework. 1-Methylpiperazinium cations reside within the 3-D channel system, held in place by a strong network of hydrogen bonds. The (4.8) net sheets occur in a number of zeolite structures e.g. ABW and GIS and related zinc phosphate phases. © 2004 Academie des sciences. Published by Elsevier SAS. All rights reserved.

Structures of Pd(CN)2and Pt(CN)2: intrinsically nanocrystalline materials?

Analysis and modeling of X-ray and neutron Bragg and total diffraction data show that the compounds referred to in the literature as “Pd(CN)2”and“Pt(CN)2” are nanocrystalline materials containing of small sheets of vertex-sharing square-planar M(CN)4 units, layered in a disordered manner with an intersheet separation of 3.44 A at 300 K. The small size of the crystallites means that the sheets’ edges form a significant fraction of each material. The Pd(CN)2 nanocrystallites studied using total neutron diffraction are terminated by water and the Pt(CN)2 nanocrystallites by ammonia, in place of half of the terminal cyanide groups, thus maintaining charge neutrality. The neutron samples contain sheets of approximate dimensions 30 A x 30 A. For sheets of the size we describe, our structural models predict compositions of Pd(CN)2-xH2O and Pt(CN)2-yNH3 (x = y = 0.29). These values are in good agreement with those obtained from total neutron diffraction and thermal analysis, and are also supported by infrared and Raman spectroscopy measurements. It is also possible to prepare related compounds Pd(CN)2-pNH3 and Pt(CN)2-qH2O, in which the terminating groups are exchanged. Additional samples showing sheet sizes in the range 10 A x 10 A (y = 0.67) to 80 A x 80 A (p = q = 0.12), as determined by X-ray diffraction, have been prepared. The related mixed-metal phase, Pd1/2Pt1/2(CN)2-qH2O(q = 0.50), is also nanocrystalline (sheet size 15 A x 15 A). In all cases, the interiors of the sheets are isostructural with those found in Ni(CN)2. Removal of the final traces of water or ammonia by heating results in decomposition of the compounds to Pd and Pt metal, or in the case of the mixed-metal cyanide, the alloy, Pd1/2Pt1/2, making it impossible to prepare the simple cyanides, Pd(CN)2, Pt(CN)2 or Pd1/2Pt1/2(CN)2, by this method.

Primary evolving networks and the comparative analysis of robust and fragile structures

In this paper we consider the structure of dynamically evolving networks modelling information and activity moving across a large set of vertices. We adopt the communicability concept that generalizes that of centrality which is defined for static networks. We define the primary network structure within the whole as comprising of the most influential vertices (both as senders and receivers of dynamically sequenced activity). We present a methodology based on successive vertex knockouts, up to a very small fraction of the whole primary network,that can characterize the nature of the primary network as being either relatively robust and lattice-like (with redundancies built in) or relatively fragile and tree-like (with sensitivities and few redundancies). We apply these ideas to the analysis of evolving networks derived from fMRI scans of resting human brains. We show that the estimation of performance parameters via the structure tests of the corresponding primary networks is subject to less variability than that observed across a very large population of such scans. Hence the differences within the population are significant.

Mean climate and variability of the atmosphere and ocean on an aquaplanet

Numerical experiments are described that pertain to the climate of a coupled atmosphere–ocean–ice system in the absence of land, driven by modern-day orbital and CO2 forcing. Millennial time-scale simulations yield a mean state in which ice caps reach down to 55° of latitude and both the atmosphere and ocean comprise eastward- and westward-flowing zonal jets, whose structure is set by their respective baroclinic instabilities. Despite the zonality of the ocean, it is remarkably efficient at transporting heat meridionally through the agency of Ekman transport and eddy-driven subduction. Indeed the partition of heat transport between the atmosphere and ocean is much the same as the present climate, with the ocean dominating in the Tropics and the atmosphere in the mid–high latitudes. Variability of the system is dominated by the coupling of annular modes in the atmosphere and ocean. Stochastic variability inherent to the atmospheric jets drives variability in the ocean. Zonal flows in the ocean exhibit decadal variability, which, remarkably, feeds back to the atmosphere, coloring the spectrum of annular variability. A simple stochastic model can capture the essence of the process. Finally, it is briefly reviewed how the aquaplanet can provide information about the processes that set the partition of heat transport and the climate of Earth.

Software evolution: a graph based model

A model based on graph isomorphisms is used to formalize software evolution. Step by step we narrow the search space by an informed selection of the attributes based on the current state-of-the-art in software engineering and generate a seed solution. We then traverse the resulting space using graph isomorphisms and other set operations over the vertex sets. The new solutions will preserve the desired attributes. The goal of defining an isomorphism based search mechanism is to construct predictors of evolution that can facilitate the automation of ’software factory’ paradigm. The model allows for automation via software tools implementing the concepts.