On primitive 3-smooth partitions of .
One of the most outstanding problems in combinatorial mathematics and geometry is the problem of existence of finite projective planes whose order is not a prime power.
If is a connected graph with distance function , then by a step in is meant an ordered triple of vertices of such that and . A characterization of the set of all steps in a connected graph was published by the present author in 1997. In Section 1 of this paper, a new and shorter proof of that characterization is presented. A stronger result for a certain type of connected graphs is proved in Section 2.
A graph is called 1-planar if there exists a drawing in the plane so that each edge contains at most one crossing. We study maximal 1-planar graphs from the point of view of properties of their diagrams, local structure and hamiltonicity.
A graph having a perfect matching is called -extendable if every matching of size can be extended to a perfect matching. It is proved that in the hypercube , a matching with can be extended to a perfect matching if and only if it does not saturate the neighbourhood of any unsaturated vertex. In particular, is -extendable for every with
We define digraphs minimal, critical, and maximal by three types of radii. Some of these classes are completely characterized, while for the others it is shown that they are large in terms of induced subgraphs.
The paper gives an overview of results for radially minimal, critical, maximal and stable graphs and digraphs.