Moore mixed graphs from Cayley graphs. (English) Zbl 1514.05071
Summary: 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.
MSC:
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C20 | Directed graphs (digraphs), tournaments |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
| 20C30 | Representations of finite symmetric groups |
References:
| [1] | J. Bosák, Partially directed Moore graphs, Math. Slovaca 29 (1979), no. 2, 181-196. · Zbl 0407.05057 |
| [2] | J. M. Brunat, M. Espona, M. A. Fiol, and O. Serra, On Cayley line digraphs, Discrete Mat. 138 (1995), no. 1, 147-159. · Zbl 0849.05031 |
| [3] | 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 (2016), no. 8, 2066-2069. · Zbl 1336.05038 |
| [4] | 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. |
| [5] | C. Dalfó, A new general family of mixed graphs, Discrete Appl. Math 269 (2019), 99-106. · Zbl 1421.05035 |
| [6] | C. Dalfó, M. A. Fiol, and N. López, Sequence mixed graphs, Discrete Appl. Math. 219 (2017), 110-116. · Zbl 1354.05057 |
| [7] | C. Dalfó, M. A. Fiol, and N. López, On bipartite mixed graphs, J. Graph Theory 89 (2018), no. 4, 386-394. · Zbl 1402.05088 |
| [8] | 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. · Zbl 1393.05155 |
| [9] | G. Erskine, Mixed Moore Cayley graphs, J. Intercon. Networks 17, no. 03n04, (2017) 1741010. |
| [10] | 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. · Zbl 0773.05048 |
| [11] | 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. · Zbl 0528.68048 |
| [12] | A. L. Gavrilyuk, M. Hirasaka, and V. Kabanov, A note on Moore Cayley digraphs, Graphs Combin. 37 (2021) 1509-1520. · Zbl 1479.05202 |
| [13] | A. J. Hoffman and M. H. McAndrew, The polynomial of a directed graph, Proc. Amer. Math. Soc. 16 (1965), 303-309. · Zbl 0129.40102 |
| [14] | L. K. Jørgensen, New mixed Moore graphs and directed strongly regular graphs, Discrete Math. 338 (2015), 1011-1016. · Zbl 1371.05322 |
| [15] | N. López and J. M. Miret, On mixed almost Moore graphs of diameter two, Electron. J. Combin. 23(2) (2016), 1-14. · Zbl 1335.05096 |
| [16] | 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 (2016), no. 2, 589-596. · Zbl 1327.05093 |
| [17] | N. López, H. Pérez-Rosés, and J. Pujolàs, Mixed Moore Cayley graphs, Electron. Notes Discrete Math. 46 (2014), 193-200. · Zbl 1337.05031 |
| [18] | M. Miller and J.Širáň, Moore graphs and beyond: A survey of the degree/diameter problem, Electron. J. Combin. 20(2) (2013), #DS14v2. |
| [19] | M. H. Nguyen, M. Miller, and J. Gimbert, On mixed Moore graphs, Discrete Math. 307 (2007), 964-970. · Zbl 1112.05031 |
| [20] | J. Tuite and G. Erskine, On total regularity of mixed graphs with order close to the Moore bound, Graphs Combin. 35 (2019), no. 6, 1253-1272. · Zbl 1440.05130 |
| [21] | J. Tuite and G. Erskine, On networks with order close to the Moore bound, Graphs Combin. 38 143 (2022). · Zbl 1495.05079 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
