An (r,z,k)-mixed graph G has every vertex with undirected degree r, directed in- and out-degree z, and diameter k. In this paper, we study the case r = z = 1, proposing some new constructions of (1,1,k)-mixed graphs with a large number of vertices N. Our study is based on computer techniques for small values of k and the use of graphs on alphabets for general k. In the former case, the constructions are either Cayley or lift graphs. In the latter case, some infinite families of (1,1,k)-mixed graphs are proposed with diameter of the order of 2log2 N.

The Mondrian problem consists of dissecting a square of side length n∈N into non-congruent rectangles with natural length sides such that the difference d(n) between the largest and the smallest areas of the rectangles partitioning the square is minimum. In this paper, we compute some bounds on d(n) in terms of the number of rectangles of the square partition. These bounds provide us optimal partitions for some values of n∈N. We provide a sequence of square partitions such that d(n)∕n2 tends to zero for n large enough. For the case of ‘perfect’ partitions, that is, with d(n)=0, we show that, for any fixed powers s1,…,sm, a square with side length n=p1s1⋯pmsm, can have a perfect Mondrian partition only if p1 satisfies a given lower bound. Moreover, if n(x) is the number of side lengths x (with n≤x) of squares not having a perfect partition, we prove that its ‘density’ n(x)x is asymptotic to (log(log(x)))22logx, which improves previous results.

Abstract For graphs with maximum degree d and diameter k, an upper bound on the number of vertices in the graphs is provided by the well‐known Moore bound (denoted by Md,k). Graphs that achieve this bound (Moore graphs) are very rare, and determining how close one can come to the Moore bound has been a major topic in graph theory. Of particular note in this regard are the cage problem and the degree/diameter problem. In this article, we take a different approach and consider questions that arise when we fix the number of vertices in the graph at the Moore bound, but relax, by one, the diameter constraint on a subset of the vertices. In this context, regular graphs of degree d, radius k, diameter k + 1, and order equal to Md,k are called radially Moore graphs. We consider two specific questions. First, we consider the existence question (extending the work of Knor), and second, we consider some natural measures of how well a radially Moore graph approximates a Moore graph. © 2010 Wiley Periodicals, Inc. NETWORKS, 2010