On bipartite (1,1, k)-mixed graphs

Dalfó, Cristina; Erskine, Grahame; Exoo, Geoffrey; Fiol, Miguel Angel and Tuite, James (2024). On bipartite (1,1, k)-mixed graphs. The Art of Discrete and Applied Mathematics (In press).

Abstract

The degree/diameter problem consists of finding the graph (or graphs) with the largest possible number of vertices, given a maximum degree and a diameter. This famous problem was extended to digraphs and mixed graphs. Mixed graphs can be seen as digraphs with arcs and edges (or digons, that is, two opposite arcs). In this paper, we consider the case where such graphs are bipartite and in which the undirected and directed degrees are one. The largest graphs, in terms of the number of vertices, are presented for small diameters. Moreover, two infinite families of such graphs with diameter k and number of vertices of the order of 2^k/2 are proposed, one of them being totally regular (1, 1)-mixed graphs. In addition, we present two more infinite families called chordal ring and chordal double ring mixed graphs, which are bipartite and related to tessellations of the plane. Finally, we give an upper bound that improves the Moore bound for bipartite mixed graphs for r = z = 1.

Viewing alternatives

Item Actions

Export

You can export this page using these formats