Binary clustering systems are closely related to monotone transit functions. An interesting class are pyramidal transit functions defined by the fact that their transit sets form an interval hypergraph. We investigate here properties of transit function R, such as union-closure, that are sufficient to ensure that R is at least weakly pyramidal. Necessary conditions for pyramidal transit functions are derived from the five forbidden configurations in Tucker’s characterization of interval hypergraphs. The first corresponds to β-acyclicity, also known as total balancedness, for which we obtain three alternative characterizations. For monotonous transit functions, the last forbidden configuration becomes redundant, leaving us with characterization of pyramidal transit functions in terms of four additional conditions.

The general position number gp( G) of a graph G is the cardinality of a largest set of vertices S such that no element of S lies on a geodesic between two other elements of S. The complementary prism G[Formula: see text] of G is the graph formed from the disjoint union of G and its complement [Formula: see text] by adding the edges of a perfect matching between them. It is proved that gp( G[Formula: see text]) ≤ n( G) + 1 if G is connected and gp( G[Formula: see text]) ≤ n( G) if G is disconnected. Graphs G for which gp( G[Formula: see text]) = n( G) + 1 holds, provided that both G and [Formula: see text] are connected, are characterized. A sharp lower bound on gp( G[Formula: see text]) is proved. If G is a connected bipartite graph or a split graph then gp( G[Formula: see text]) ∈ { n( G), n( G)+1}. Connected bipartite graphs and block graphs for which gp( G[Formula: see text]) = n( G) + 1 holds are characterized. A family of block graphs is constructed in which the gp-number of their complementary prisms is arbitrary smaller than their order.

The distance DG(v) of a vertex v in an undirected graph G is the sum of the distances between v and all other vertices of G. The set of vertices in G with maximum (minimum) distance is the antimedian (median) set of a graph G. It is proved that for arbitrary graphs G and J and a positive integer r > 2, there exists a connected graph H, such that G is the antimedian and J the median subgraphs of H, respectively, and that dH(G,J) = r. When both G and J are connected, G and J can in addition be made convex subgraphs of H. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010