A mixed regular graph is a graph where every vertex has z incoming arcs, z outgoing arcs, and r edges. If in addition it has girth g , we say that the graph is a [z, r; g]-mixed graph. A [z, r; g]-mixed cage is a [z, r; g ]-mixed graph with the smallest number of vertices. We give constructions for mixed graphs with girth 5 and 6 using the incidence graph of projective planes. In particular, we present a family of [z, q; 5]-mixed graphs for a power of prime q ≥ 7 such that q - 1 ≤ 4z + R with z ≥ 1 and R ε {1,..., 5}. For girth 6, we present an infinite family for pairs of a prime q and a number p = q−1/2. If p is odd, the construction gives [p+1/2,q;6]-mixed graphs, otherwise we obtain [p/2,q;6]-mixed graphs.

In this work, I use some specific voltage graphs to study a generalization of the Cage Problem. In particular, we construct families of semi-cubic graphs with fixed girth and few vertices. Some of them are the smallest that exist because they attain the previously lower bounds.

It is a classic result that a set of n non-collinear points in the Euclidean plane defines at least n different lines. Chen and Chvátal conjectured in 2008 that the same results is true in metric spaces for an adequate definition of line. More recently, this conjecture was studied in the context of quasi-metric spaces. One way to study lines in an space is though its betweenness. Given a quasi-metric space (V,ρ), its induced quasi-metric be-tweenness is the set of triples (x, y, z) ϵ V3 such that ρ(x, z) = ρ(x, y) +ρ(y, z). In this work, we prove the existence of a quasi-metric space on four points a, b, c and d whose quasi-metric betweenness is ẞ = {(c, a, b), (a, b, c), (d, b, a), (b, a, d)}. This space has only three lines, none of which has four points. Moreover, we show that the betweenness of any quasi-metric space on four points with this property is isomorphic to B. Since B is not metric, we conclude that Chen and Chvatal's conjecture is valid for any metric space on four points.

A digraph D = (V, A) is semi-complete if for each pair of distinct vertices x and y in V, either xy or yx belong to A. A subset ℓ of vertices is a line of D if there are two distinct vertices x and y such that for any vertex z ε V, z ε ℓ if and only if a directed shortest path exists containing x, y and z. A classic result proved by Erdös says that any set of n points in the Euclidean plane endowed with the Euclidean distance defines a metric space with at least n different lines unless there is a line containing the n points. Chen and Chvátal in 2008 conjectured that the same results is true for any metric spaces where lines are defined in a manner similar to above. In this paper we prove that in any semi-complete digraphs with n vertices the number of lines defined by vertices connected by an arc is at least n. Then, the quasi-metric spaces defined by semi-complete digraphs fulfill Chen and Chvátal conjecture in a stronger manner as, on the one hand, they always have at least n lines, and on the other hand, these n lines are defined by vertices at distance one.

In this article, some structures in the projective plane of order are found which allow us to construct small -regular balanced bipartite graphs of girth 6 for all . When , the order of these -regular graphs is ; and when , the order of these -regular graphs is . Moreover, the incidence matrix of a -regular balanced bipartite graph of girth 6 having vertices, where is an integer and is a prime power with , is provided. These graphs improve upon the best known upper bounds for the number of vertices in regular graphs of girth 6. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(2), 121–127 2011