Construction of extremal mixed graphs of diameter two. (English) Zbl 1414.05162
Summary: Graphs and digraphs with maximum order allowed by its degree and diameter have been widely studied in the context of the degree/diameter problem. This problem turns out to be very interesting in the mixed case, where many open problems arise, specially when the diameter is two and the order of the graph achieves the largest theoretical value given by the mixed Moore bound. These extremal graphs are known as mixed Moore graphs. In this paper we construct by voltage assignment some infinite families of mixed graphs of diameter two and order approaching the Moore bound. One of these families, in particular, yields most of the known mixed Moore graphs. We also present other families which are the result of the first known extension of the paradigmatic McKay-Miller-Širáň construction [B. D. McKay et al., J. Comb. Theory, Ser. B 74, No. 1, 110–118 (1998; Zbl 0911.05031)].
MSC:
| 05C35 | Extremal problems in graph theory |
| 05C12 | Distance in graphs |
| 05C20 | Directed graphs (digraphs), tournaments |
Citations:
Zbl 0911.05031References:
| [1] | Alegre, I.; Fiol, M. A.; Yebra, J. L.A., Some large graphs with given degree and diameter, J. Graph Theory, 10, 2, 219-224 (1986) · Zbl 0592.05032 |
| [2] | Araujo-Pardo, C.; Balbuena, C.; Miller, M.; Ždímalová, M., A construction of dense mixed graphs of diameter 2, Electron. Notes Discrete Math., 54, 235-240 (2016) · Zbl 1356.05076 |
| [3] | Baskoro, E.; Branković, L.; Miller, M.; Plesník, J.; Ryan, J.; Širáň, J., Large digraphs with small diameter: A voltage assignment approach, J. Comb. Math. Comb. Comput., 24, 161-176 (1997) · Zbl 0884.05046 |
| [4] | Bosák, J., Partially directed Moore graphs, Math. Slovaca, 29, 181-196 (1979) · Zbl 0407.05057 |
| [5] | Branković, L.; Miller, M.; Plesník, J.; Ryan, J.; Širáň, J., Large graphs with small diameter: A voltage assignment approach, Australas. J. Combin., 18, 65-76 (1998) · Zbl 0929.05040 |
| [6] | Branković, L.; Miller, M.; Plesník, J.; Ryan, J.; Širáň, J., A note on constructing large Cayley graphs of given degree and diameter by voltage assignments, Electron. J. Combin., 5 (1998) · Zbl 0885.05071 |
| [7] | Brualdi, R., Introductory Combinatorics (1977), North-Holland: North-Holland Amsterdam · Zbl 0385.05001 |
| [8] | Brunat, J.; Espona, M.; Fiol, M.; Serra, O., On cayley line digraphs, 14th British Combinatorial Conference. 14th British Combinatorial Conference, Discrete Math., 138, 1-3, 147-159 (1995) · Zbl 0849.05031 |
| [9] | Buset, D.; El Amiri, M.; Erskine, G.; Miller, M.; Pérez-Rosés, H., A revised Moore bound for mixed graphs, Discrete Math., 339, 2066-2069 (2016) · Zbl 1336.05038 |
| [10] | C. Dalfó, M. Fiol, N. López, On bipartite mixed graphs, arXiv preprints, 2016.; C. Dalfó, M. Fiol, N. López, On bipartite mixed graphs, arXiv preprints, 2016. |
| [11] | Dalfó, C.; Fiol, M.; López, N., Sequence mixed graphs, Discrete Appl. Math., 219, 110-116 (2017) · Zbl 1354.05057 |
| [12] | Gross, J. L.; Tucker, T. W., Topological Graph Theory (1987), Courier Corporation · Zbl 0621.05013 |
| [13] | Jørgensen, L. K., New mixed Moore graphs and directed strongly regular graphs, Discrete Math., 338, 6, 1011-1016 (2015) · Zbl 1371.05322 |
| [14] | López, N.; Miret, J., On mixed almost moore graphs of diameter two, Electron. J. Combin., 2, 23, 1-14 (2016) · Zbl 1335.05096 |
| [15] | López, N.; Miret, J. M.; Fernández, C., Non existence of some mixed Moore graphs of diameter 2 using SAT, Discrete Math., 339, 2, 589-596 (2016) · Zbl 1327.05093 |
| [16] | N. López, Q. Monserrat, El problema de la regularidad de los grafos cuasi de moore mezclados, in: Proceedings of the 10th Andalusian Meeting on Discrete Mathematics, 2017, pp. 151-154.; N. López, Q. Monserrat, El problema de la regularidad de los grafos cuasi de moore mezclados, in: Proceedings of the 10th Andalusian Meeting on Discrete Mathematics, 2017, pp. 151-154. |
| [17] | López, N.; Pérez-Rosés, H.; Pujolàs, J., Cayley mixed Moore graphs, Electron. Notes Discrete Math., 46, 193-200 (2014) · Zbl 1337.05031 |
| [18] | López, N.; Pérez-Rosés, H.; Pujolàs, J., The Degree \(/\) Diameter problem for mixed abelian Cayley graphs, Algorithmic Graph Theory on the Adriatic Coast. Algorithmic Graph Theory on the Adriatic Coast, Discrete Appl. Math., 231, Supplement C, 190-197 (2017) · Zbl 1369.05106 |
| [19] | Loz, E.; Miller, M.; Šiagiová, J.; Širáň, J.; Tomanová, J., Small vertex-transitive and cayley graphs of girth six and given degree: an algebraic approach, J. Graph Theory, 68, 4, 265-284 (2011) · Zbl 1234.05121 |
| [20] | Loz, E.; Pineda-Villavicencio, G., New benchmarks for large-scale networks with given maximum degree and diameter, Comput. J. (2009) |
| [21] | Loz, E.; Širáň, J., New record graphs in the degree/diameter problem, Australas. J. Combin., 41, 63-80 (2008) · Zbl 1178.05038 |
| [22] | Macbeth, H.; Šiagiová, J.; Širáň, J.; Vetrík, T., Large cayley graphs and vertex-transitive non-cayley graphs of given degree and diameter, J. Graph Theory, 64, 2, 87-98 (2010) · Zbl 1230.05158 |
| [23] | McKay, B. D.; Miller, M.; Širáň, J., A note on large graphs of diameter two and given maximum degree, J. Combin. Theory Ser. B, 74, 1, 110-118 (1998) · Zbl 0911.05031 |
| [24] | Nguyen, M. H.; Miller, M.; Gimbert, J., On mixed Moore graphs, Discrete Math., 307, 7-8, 964-970 (2007) · Zbl 1112.05031 |
| [25] | Šiagiová, J., Approaching the mixed Moore bound for diameter two by Cayley graphs, Australas. J. Combin., 61, 73-81 (2015) · Zbl 1309.05095 |
| [26] | Šiagiová, J., A note on the McKay \(-\) Miller \(-\) Širáň graphs, J. Combin. Theory Ser. B, 81, 2, 205-208 (2001) · Zbl 1024.05039 |
| [27] | Zlatoš, J., The diameter of lifted digraphs, Australas. J. Combin., 19, 73-82 (1999) · Zbl 0933.05069 |
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.
