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

Hall conditions for edge-weighted bipartite graphs

A weighted variant of Hall's condition for the existence of matchings is shown to be equivalent to the existence of a matching in a lexicographic product. This is used to introduce characterizations of those bipartite graphs whose edges may be replicated so as to yield semiregular multigraphs or, equivalently, semiregular edge-weightings. Such bipartite graphs will be called semiregularizable. Some infinite families of semiregularizable trees are described and all semiregularizable trees on at most 11 vertices are listed. Matrix analogues of some of the results are mentioned and are shown to imply some of the known characterizations of regularizable graphs.

Graphs of relations and Hilbert series

We are discussing certain combinatorial and counting problems related to quadratic algebras. First we give examples which confirm the Anick conjecture on the minimal Hilbert series for algebras given by $n$ generators and $\frac {n(n-1)}{2}$ relations for $n \leq 7$. Then we investigate combinatorial structure of colored graph associated to relations of RIT algebra. Precise descriptions of graphs (maps) corresponding to algebras with maximal Hilbert series are given in certain cases. As a consequence it turns out, for example, that RIT algebra may have a maximal Hilbert series only if components of the graph associated to each color are pairwise 2-isomorphic.