Moore mixed graphs from Cayley graphs
Abstract
A Moore (r, z, k)-mixed graph G has every vertex with undirected degree r, directed in- and out-degree z, diameter k, and number of vertices (or order) attaining the corresponding Moore bound M(r, z, k) for mixed graphs. When the order of G is close to M(r, z, k) vertices, we refer to it as an almost Moore graph. The first part of this paper is a survey about known Moore (and almost Moore) general mixed graphs that turn out to be Cayley graphs. Then, in the second part of the paper, we give new results on the bipartite case. First, we show that Moore bipartite mixed graphs with diameter three are distance-regular, and their spectra are fully characterized. In particular, an infinity family of Moore bipartite (1, z, 3)-mixed graphs is presented, which are Cayley graphs of semidirect products of groups. Our study is based on the line digraph technique, and on some results about when the line digraph of a Cayley digraph is again a Cayley digraph.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2023.11.1.15
References
J. Bosák, Partially directed Moore graphs, Math. Slovaca 29(2) (1979), 181–196.
J.M. Brunat, M. Espona, M.A. Fiol, and O. Serra, On Cayley line digraphs, Discrete Mat. 138(1) (1995), 147–159.
D. Buset, M. El Amiri, G. Erskine, M. Miller, and H. Pérez-Rosés, A revised Moore bound for mixed graphs, Discrete Math. 339(8) (2016), 2066–2069.
D. Buset, N. López, and J.M. Miret, The unique mixed almost Moore graph with parameters k = 2, r = 2 and z = 1, J. Intercon. Networks 17 (2017), 1741005.
C. Dalfó, A new general family of mixed graphs, Discrete Appl. Math 269 (2019), 99–106.
C. Dalfó, M.A. Fiol, and N. López, Sequence mixed graphs, Discrete Appl. Math. 219 (2017), 110–116.
C. Dalfó, M.A. Fiol, and N. López, On bipartite mixed graphs, J. Graph Theory 89(4) (2018), 386–394.
C. Dalfó, M.A. Fiol, and N. López, An improved Moore bound for mixed graphs and an optimal case with diameter three, Discrete Math. 341 (2018), 2872–2877.
G. Erskine, Mixed Moore Cayley graphs, J. Intercon. Networks 17, no. 03n04, (2017) 1741010.
M.L. Fiol, M.A. Fiol, and J.L.A. Yebra, When the arc-colored line digraph of a Cayley colored digraph is again a Cayley colored digraph, Ars Combin. 34 (1992), 65–73.
M.A. Fiol, J.L.A. Yebra, and I. Alegre, Line digraph iterations and the (d, k) digraph problem, IEEE Trans. Comput. C-33 (1984), 400–403.
A.L. Gavrilyuk, M. Hirasaka, and V. Kabanov, A note on Moore Cayley digraphs, Graphs Combin. 37 (2021) 1509–1520.
A.J. Hoffman and M.H. McAndrew, The polynomial of a directed graph, Proc. Amer. Math. Soc. 16 (1965), 303–309.
L.K. Jørgensen, New mixed Moore graphs and directed strongly regular graphs, Discrete Math. 338 (2015), 1011–1016.
N. López and J.M. Miret, On mixed almost Moore graphs of diameter two, Electron. J. Combin. 23(2) (2016), 1–14.
N. López, J.M. Miret, and C. Fernández, Non existence of some mixed Moore graphs of diameter 2 using SAT, Discrete Math. 339(2) (2016), 589–596.
N. López, H. Pérez-Rosés, and J. Pujolàs, Mixed Moore Cayley graphs, Electron. Notes Discrete Math. 46 (2014), 193–200.
M. Miller and J. Širáň, Moore graphs and beyond: A survey of the degree/diameter problem, Electron. J. Combin. 20(2) (2013), #DS14v2.
M.H. Nguyen, M. Miller, and J. Gimbert, On mixed Moore graphs, Discrete Math. 307 (2007), 964–970.
J. Tuite and G. Erskine, On total regularity of mixed graphs with order close to the Moore bound, Graphs Combin. 35(6) (2019), 1253–1272.
J. Tuite and G. Erskine, On networks with order close to the Moore bound, Graphs Combin. 38(143) (2022).
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.