Structural and Spectral Properties of Chordal Ring, Multi-Ring, and Mixed Graphs

Abstract

The chordal ring (CR) graphs are a well-known family of graphs used to model some interconnection networks for computer systems in which all nodes are in a cycle. Generalizing the CR graphs, in this paper, we introduce the families of chordal multi-ring (CMR), chordal ring mixed (CRM), and chordal multi-ring mixed (CMRM) graphs. In the case of mixed graphs, we can have edges (without direction) and arcs (with direction). The chordal ring and chordal ring mixed graphs are bipartite and 3-regular. They consist of a number r (for r≥1) of (undirected or directed) cycles with some edges (the chords) joining them. In particular, for CMR, when r=1, that is, with only one undirected cycle, we obtain the known families of chordal ring graphs. Here, we used plane tessellations to represent our chordal multi-ring graphs. This allowed us to obtain their maximum number of vertices for every given diameter. Additionally, we computationally obtained their minimum diameter for any value of the number of vertices. Moreover, when seen as a lift graph (also called voltage graph) of a base graph on Abelian groups, we obtained closed formulas for the spectrum, that is, the eigenvalue multi-set of its adjacency matrix.

Keywords

• chordal ring graphs
• diameter
• the degree/diameter problem
• lift graphs
• Abelian group
• plane tessellations