Properties of mixed Moore graphs of directed degree one. (English) Zbl 1305.05239
Summary: Mixed graphs of order \(n\) such that for any pair of vertices there is a unique trail of length at most \(k\) between them are known as mixed Moore graphs. These extremal graphs may only exist for diameter \(k = 2\) and certain (infinitely many) values of \(n\). In this paper we give some properties of mixed Moore graphs of directed degree one and reduce their existence to the existence of some (undirected) strongly regular graphs.
MSC:
| 05E30 | Association schemes, strongly regular graphs |
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C35 | Extremal problems in graph theory |
| 05C07 | Vertex degrees |
References:
| [1] | Bannai, E.; Ito, T., On finite Moore graphs, J. Fac. Sci. Univ. Tokyo, 20, 191-208 (1973) · Zbl 0275.05121 |
| [2] | Bosák, J., Partially directed Moore graphs, Math. Slovaca, 29, 181-196 (1979) · Zbl 0407.05057 |
| [3] | Bridges, W. G.; Toueg, S., On the impossibility of directed Moore graphs, J. Combin. Theory B, 29, 339-341 (1980) · Zbl 0388.05019 |
| [4] | Damerell, R. M., On Moore graphs, Proc. Camb. Phil. Soc., 74, 227-236 (1973) · Zbl 0262.05132 |
| [5] | Duval, Art M., A directed graph version of strongly regular graphs, J. Combin. Theory Ser. A, 47, 71-100 (1988) · Zbl 0642.05025 |
| [6] | Hoffman, A. J.; Singleton, R. R., On Moore graphs with diameter 2 and 3, IBM Res. Develop., 4, 497-504 (1960) · Zbl 0096.38102 |
| [8] | Nguyen, M. H.; Miller, M., Moore bounds for mixed networks, Discrete Math., 308, 5499-5503 (2008) · Zbl 1197.05066 |
| [9] | Nguyen, M. H.; Miller, M.; Gimbert, J., On mixed Moore graphs, Discrete Math., 307, 964-970 (2007) · Zbl 1112.05031 |
| [10] | Plesník, J.; Znám, Š., Strongly geodetic directed graphs, Acta F. R. N. Univ. Comen.-Mathematica, XXIX, 29-34 (1974) · Zbl 0291.05106 |
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.
