On the Arrangement of Cliques in Chordal Graphs with respect to the Cuts

A cut (A, B) (where B = V - A) in a graph G = (V, E) is called internal if and only if there exists a vertex x in A that is not adjacent to any vertex in B and there exists a vertex y is an element of B such that it is not adjacent to any vertex in A. In this paper, we present a theorem regarding the arrangement of cliques in a chordal graph with respect to its internal cuts. Our main result is that given any internal cut (A, B) in a chordal graph G, there exists a clique with kappa(G) + vertices (where kappa(G) is the vertex connectivity of G) such that it is (approximately) bisected by the cut (A, B). In fact we give a stronger result: For any internal cut (A, B) of a chordal graph, and for each i, 0 <= i <= kappa(G) + 1 such that vertical bar K-i vertical bar = kappa(G) + 1, vertical bar A boolean AND K-i vertical bar = i and vertical bar B boolean AND K-i vertical bar = kappa(G) + 1 - i. An immediate corollary of the above result is that the number of edges in any internal cut (of a chordal graph) should be Omega(k(2)), where kappa(G) = k. Prompted by this observation, we investigate the size of internal cuts in terms of the vertex connectivity of the chordal graphs. As a corollary, we show that in chordal graphs, if the edge connectivity is strictly less than the minimum degree, then the size of the mincut is at least kappa(G)(kappa(G)+1)/2 where kappa(G) denotes the vertex connectivity. In contrast, in a general graph the size of the mincut can be equal to kappa(G). This result is tight.

Behaviour of methylmethacrylate-acrylonitrile random copolymers in dilute solution

Studies on the dilute solution properties of methylmethacrylate-acrylonitrile random copolymers of three different compositions, 0.236, 0.5 and 0.74 mole fraction (m.f.) of acrylonitrile (AN) designated as MAa, MAb and MAc, respectively, have been made in good solvents and theta solvents. MAa has been studied in benzene (Bz) and ethylacetate (EAc). MAb in acetonitrile (MeCN), dimethyl sulphoxide (DMSO) and a binary solvent mixture of Bz and dimentyl formamide (DMF) in the volume ratio 6.5:1 designated as BM1 and MAc in MeCN, DMSO and Bz + DMF in the volume ratio 1.667:1 designated as BM2. The Mark-Houwink exponent ‘a’ reveals that Bz is a theta solvent for MAa at 20°C. For MAb and MAc, BM1 and BM2, respectively have ‘a’ values of 0.5 at all three temperatures studied (30°, 40° and 50°C). It is not clear whether they represent theta states or preferential adsorption plays a role complicating the behaviour in solution. The values of A2 are very low in MeCN considering that it is a very good solvent for the copolymer, ‘a’ values for MAb and MAc being 0.75 and 0.7, respectively.

Nonstationary Random Critical Seismic Excitations

A method is presented to find nonstationary random seismic excitations with a constraint on mean square value such that the response variance of a given linear system is maximized. It is also possible to incorporate the dominant input frequency into the analysis. The excitation is taken to be the product of a deterministic enveloping function and a zero mean Gaussian stationary random process. The power spectral density function of this process is determined such that the response variance is maximized. Numerical results are presented for a single-degree system and an earth embankment modeled as shear beam.

Calculating the Fickian diffusivity for a lattice-based random walk with agents and obstacles of different shapes and sizes

Random walk models are often used to interpret experimental observations of the motion of biological cells and molecules. A key aim in applying a random walk model to mimic an in vitro experiment is to estimate the Fickian diffusivity (or Fickian diffusion coefficient),D. However, many in vivo experiments are complicated by the fact that the motion of cells and molecules is hindered by the presence of obstacles. Crowded transport processes have been modeled using repeated stochastic simulations in which a motile agent undergoes a random walk on a lattice that is populated by immobile obstacles. Early studies considered the most straightforward case in which the motile agent and the obstacles are the same size. More recent studies considered stochastic random walk simulations describing the motion of an agent through an environment populated by obstacles of different shapes and sizes. Here, we build on previous simulation studies by analyzing a general class of lattice-based random walk models with agents and obstacles of various shapes and sizes. Our analysis provides exact calculations of the Fickian diffusivity, allowing us to draw conclusions about the role of the size, shape and density of the obstacles, as well as examining the role of the size and shape of the motile agent. Since our analysis is exact, we calculateDdirectly without the need for random walk simulations. In summary, we find that the shape, size and density of obstacles has a major influence on the exact Fickian diffusivity. Furthermore, our results indicate that the difference in diffusivity for symmetric and asymmetric obstacles is significant.

Random Breath Testing Operation and Effectiveness in 1987

• In December 1986 funds were approved to double the intensity of random breath testing (RBT) and provide publicity support for police efforts. These changes were considered necessary to make RBT effective. • RBT methods were changed in the metropolitan area to enable block testing (pulling over a block of traffic rather than one or two cars), deployment of police to cut off escape routes, and testing by traffic patrols in all police subdivisions. Additional operators were trained for country RBT. • A publicity campaign was developed, aimed mainly at male drivers aged 18-50. The campaign consisted of the “cardsharp” television commercials, radio commercials, newspaper articles, posters and pamphlets. • Increased testing and the publicity campaigns were launched on 10 April 1987. • Police tests increased by 92.5% in May – December 1987, compared with the same period in the previous four years. • The detection rate for drinking drivers picked up by police who were cutting off escape routes was comparatively high, indicating that drivers were attempting to avoid RBT, and that this police method was effective at detecting these drivers. • A telephone survey indicated that drivers were aware of the messages of the publicity campaign. • The telephone survey also indicated that the target group had been exposed to high levels of RBT, as planned, and that fear of apprehension was the major factor deterring them from drink driving. • A roadside survey of driver blood alcohol concentrations (BACs) by the University of Adelaide’s Road Accident Research Unit (RARU) showed that, between 10p.m. and 3a.m., the proportion of drivers in Adelaide with a BAC greater than or equal to 0/08 decreased by 42%. • Drivers under 21 were identified as a possible problem area. • Fatalities in the twelve month period commencing May 1987 decreased by 18% in comparison with the previous twelve month period, and by 13% in comparison with the average of the previous two twelve month periods (commencing May 1985 and May 1986). There are indications that this trend is continuing. • It is concluded that the increase in RBT, plus publicity, was successful in achieving its aims of reductions in drink driving and accidents.

Random Breath Testing Operation and Effectiveness in 1985

Random breath testing (RBT) was introduced in South Australia in 1981 with the intention of reducing the incidence of accidents involving alcohol. In April 1985, a Select Committee of the Upper House which had been established to “review the operation of random breath testing in this State and any other associated matters and report accordingly” presented its report. After consideration of this report, the Government introduced extensive amendments to those sections of the Motor Vehicles Act (MVA) and Road Traffic Act (RTA) which deal with RBT and drink driving penalties. The amended section 47da of the RTA requires that: “(5) The Minister shall cause a report to be prepared within three months after the end of each calendar year on the operation and effectiveness of this section and related sections during that calendar year. (6) The Minister shall, within 12 sitting days after receipt of a report under subsection (5), cause copies of the report to be laid before each House of Parliament.” This is the first such report. Whilst it deals with RBT over a full year, the changed procedures and improved flexibility allowed by the revision to the RTA were only introduced late in 1985 and then only to the extent that the existing resources would allow.

High-resolution melt-curve analysis of random amplified polymorphic DNA (RAPD-HRM) for the characterisation of pathogenic leptospires: intra-serovar divergence, interserovar convergence, and evidence of attenuation in Leptospira reference collections.

High-resolution melt-curve analysis of random amplified polymorphic DNA (RAPD-HRM) is a novel technology that has emerged as a possible method to characterise leptospires to serovar level. RAPD-HRM has recently been used to measure intra-serovar convergence between strains of the same serovar as well as inter-serovar divergence between strains of different serovars. The results indicate that intra-serovar heterogeneity and inter-serovar homogeneity may limit the application of RAPD-HRM in routine diagnostics. They also indicate that genetic attenuation of aged, high-passage-number isolates could undermine the use of RAPD-HRM or any other molecular technology. Such genetic attenuation may account for a general decrease seen in titres of rabbit hyperimmune antibodies over time. Before RAPD-HRM can be further advanced as a routine diagnostic tool, strains more representative of the wild-type serovars of a given region need to be identified. Further, RAPD-HRM analysis of reference strains indicates that the routine renewal of reference collections, with new isolates, may be needed to maintain the genetic integrity of the collections.

Salmonella Virchow and Salmonella Weltevreden in a Random Survey of the Asian House Gecko, Hemidactylus frenatus, in Houses in Northern Australia.

Background: Salmonella enterica serotype Virchow is the most common cause of invasive nontyphoid salmonellosis in North Queensland, particularly in infants, but the zoonotic source is unknown. This study aimed at determining (i) the prevalence of the introduced Asian house gecko, Hemidactylus frenatus, in houses in North Queensland and (ii) whether they were a potential source of Salmonella Virchow. Methods: Asian house geckos were collected in a random survey of houses in Townsville, North Queensland. Gut contents underwent microbiological analysis within 2 h of removal using both direct plating and enrichment broth methods. Any organism found to be a presumptive Salmonella spp. was then sent to a reference lab for confirmation of genus/species, serotyping, and phage typing if indicated. Results: One hundred Asian house geckos were collected from 57 houses. Geckos were present in 100% of houses surveyed, and prevalence of Salmonella in large intestinal contents was 7% (95% confidence interval 2, 12%). Three serotypes were found: Virchow (phage type 8), Weltevreden, and an untypable subspecies 1 serotype 11:-:1,7. Conclusion: Since Salmonella Virchow (phage type 8) is associated with invasive disease, the introduced Asian house gecko may play a significant role in the epidemiology of sporadic salmonellosis in places invaded by these peridomestic reptiles. These results justify more detailed epidemiological studies on the role of the Asian house gecko in sporadic salmonellosis and development of evidence-based strategies to decrease this potential zoonotic hazard.

A necessary and sufficient condition for acyclic graphs

This letter gives a new necessary and sufficient condition to determine whether a directed graph is acyclic.

Distribution of the angle of rotation plane random walks

We study the probability distribution of the angle by which the tangent to the trajectory rotates in the course of a plane random walk. It is shown that the determination of this distribution function can be reduced to an integral equation, which can be rigorously transformed into a differential equation of Hill's type. We derive the asymptotic distribution for very long walks.

Improvement On Brooks Chromatic Bound For A Class Of Graphs

Brooks' Theorem says that if for a graph G,Δ(G)=n, then G is n-colourable, unless (1) n=2 and G has an odd cycle as a component, or (2) n>2 and Kn+1 is a component of G. In this paper we prove that if a graph G has none of some three graphs (K1,3;K5−e and H) as an induced subgraph and if Δ(G)greater-or-equal, slanted6 and d(G)<Δ(G), then χ(G)<Δ(G). Also we give examples to show that the hypothesis Δ(G)greater-or-equal, slanted6 can not be non-trivially relaxed and the graph K5−e can not be removed from the hypothesis. Moreover, for a graph G with none of K1,3;K5−e and H as an induced subgraph, we verify Borodin and Kostochka's conjecture that if for a graph G,Δ(G)greater-or-equal, slanted9 and d(G)<Δ(G), then χ(G)<Δ(G).

Approximation algorithm for maximum independent set in planar traingle-free graphs

The maximum independent set problem is NP-complete even when restricted to planar graphs, cubic planar graphs or triangle free graphs. The problem of finding an absolute approximation still remains NP-complete. Various polynomial time approximation algorithms, that guarantee a fixed worst case ratio between the independent set size obtained to the maximum independent set size, in planar graphs have been proposed. We present in this paper a simple and efficient, O(|V|) algorithm that guarantees a ratio 1/2, for planar triangle free graphs. The algorithm differs completely from other approaches, in that, it collects groups of independent vertices at a time. Certain bounds we obtain in this paper relate to some interesting questions in the theory of extremal graphs.

Algorithms for Constructing Hierarchical Graphs

An algorithm is described for developing a hierarchy among a set of elements having certain precedence relations. This algorithm, which is based on tracing a path through the graph, is easily implemented by a computer.

A note on the effective medium theory of random resistive-reactive medium

The effective medium theory for a system with randomly distributed point conductivity and polarisability is reformulated, with attention to cross-terms involving the two disorder parameters. The treatment reveals a certain inconsistency of the conventional theory owing to the neglect of the Maxwell-Wagner effect. The results are significant for the critical resistivity and dielectric anomalies of a binary liquid mixture at the phase separation point.

Dilute Solution Properties of Methyl Methacrylate/Acrylonitrile Random Copolymers, 2a)

The Stockmayer-Fixman relation was used to evaluate the short range and long range interaction parameters for methyl methacrylate/acrylonitrile copolymers of 0,566 and 0,657 mole fraction of monomeric units of acrylonitrile in the solvents acetonitrile, 2-butanone, dimethyl formamide, and y-butyrolactone, at different temperatures (30, 45, and 60 “C). The values of KO were found to be lower than those of the parent homopolymers, and their values depend on both solvent and temperature. Even negative Ko-values were obtained, in cases in which the Mark Houwink exponent a is nearly unity. The values of the polymer-solvent interaction parameter, x, , are high and close to 0,5, indicating that these solvents are not good. The values of the excess interaction parameter, xAB, are negative and are not affected by temperature. The large extension of these copolymer chains, as exhibited by a and a;-values, can be understood in terms of unusual short range interactions only. Similar results were obtained for some cellulose derivatives.