Exact colorations of graphs and digraphs

A coloration is an exact regular coloration if whenever two vertices are colored the same they have identically colored neighborhoods. For example, if one of the two vertices that are colored the same is connected to three yellow vertices, two white and red, then the other vertex is as well. Exact regular colorations have been discussed informally in the social network literature. However they have been part of the mathematical literature for some time, though in a different format. We explore this concept in terms of social networks and illustrate some important results taken from the mathematical literature. In addition we show how the concept can be extended to ecological and perfect colorations, and discuss how the CATREGE algorithm can be extended to find the maximal exact regular coloration of a graph.

A generational scheme for partitioning graphs

Graph partitioning divides a graph into several pieces by cutting edges. Very effective heuristic partitioning algorithms have been developed which run in real-time, but it is unknown how good the partitions are since the problem is, in general, NP-complete. This paper reports an evolutionary search algorithm for finding benchmark partitions. Distinctive features are the transmission and modification of whole subdomains (the partitioned units) that act as genes, and the use of a multilevel heuristic algorithm to effect the crossover and mutations. Its effectiveness is demonstrated by improvements on previously established benchmarks.

On Hamilton cycles in locally connected graphs with vertex degree constraints

It is shown that every connected, locally connected graph with the maximum vertex degree Δ(G)=5 and the minimum vertex degree δ(G)3 is fully cycle extendable. For Δ(G)4, all connected, locally connected graphs, including infinite ones, are explicitly described. The Hamilton Cycle problem for locally connected graphs with Δ(G)7 is shown to be NP-complete

Counter-terrorism, anti-extremism, armed conflict and human rights: using a Russian case study

This paper critically examines Russia’s compliance with human rights obligations and the rule of law in its ‘war on terror’. It seeks to draw wider parallels with respect for human rights in the framework of the fight against ‘new global terrorism’. Threats to due process, the discriminatory application of the forces of law and order specifically against perceived “non-traditional” Muslim communities, and a ratcheting up of fear of an Islamist threat can be traced following the war in Chechnya and the handling of the Dubrovka Theatre and Beslan school sieges. To what extent are there commonalities with UK complicity in the practice of extraordinary rendition, with atrocities perpetrated in Iraq and Afghanistan, and abuses in Abu Ghraib and Guantanamo? Are the impact of these reflected in domestic security policy and British minority ethnic community relations? [From the Author]

Explicit finite volume modeling of aircraft anti-icing and de-icing

In this paper, a runback water and ice prediction model is extended to anti-icing and thermal de-icing situations. The resulting coupled equations that govern thin-film flow, ice accretion, and heat conduction in the multilayered system substrate-ice-water are solved using an explicit finite volume approach. The procedure is implemented in the three-dimensional icing code ICECREMO2, and both structured and unstructured grids can be considered. Numerical results are presented to compare the present code simulations to some data provided by other ice prediction codes and to show the capabilities of the present numerical tool.