×

Minimum average distance of strong orientations of graphs. (English) Zbl 1055.05042

The average distance of a graph or digraph \(G\) of order \(n\), denoted by \(\mu (G)\), is the average among the distances between all \(n(n-1)\) ordered pairs of vertices of \(G\) [see e.g. J. Plesník, J. Graph Theory 8, 1–21 (1984; Zbl 0552.05048)]. If \(G\) is a 2-edge-connected graph, then \(\overrightarrow{\mu}_{\min }(G)\) is the minimum average distance taken over all strong orientations of \(G\). A sharp lower bound for \(\overrightarrow{\mu}_{\min }(G)\) is established in terms of the order, size, girth and \(\mu (G)\). In general, there is no upper bound for \(\overrightarrow{\mu}_{\min }(G)\) in terms of \(\mu (G)\). However, for some special classes of graphs such a bound is given.

MSC:

05C12 Distance in graphs
05C20 Directed graphs (digraphs), tournaments

Citations:

Zbl 0552.05048
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bang-Jensen, J.; Gutin, G., Digraphs: Theory, Algorithms and Applications (2001), Springer: Springer Berlin · Zbl 0958.05002
[2] Chartrand, G.; Oellermann, O. R., Applied and Algorithmic Graph Theory (1993), McGraw-Hill: McGraw-Hill New York
[3] Chvátal, V.; Thomassen, C., Distances in orientations of graphs, J. Combin. Theory Ser. B, 24, 61-75 (1978) · Zbl 0311.05115
[4] Füredi, Z.; Horak, P.; Pareek, C. M.; Zhu, X., Minimal oriented graphs of diameter 2, Graphs Combin, 14, 345-350 (1998) · Zbl 0917.05033
[5] Koh, K. M.; Tan, B. P., The minimum diameter of orientations of complete multipartite graphs, Graphs Combin, 12, 333-339 (1996) · Zbl 0861.05029
[6] Ng, C. P.; Teh, H. H., On finite graphs of diameter 2, Nanta Math, 1, 72-75 (1966/67) · Zbl 0182.58004
[7] Plesnı́k, J., On the sum of all distances in a graph or digraph, J. Graph Theory, 8, 1-21 (1984) · Zbl 0552.05048
[8] Plesnı́k, J., On minimal graphs of diameter 2 with every edge in a 3-cycle, Math. Slovaca, 36, 145-149 (1986) · Zbl 0603.05040
[9] S̆oltés, L., Orientations of graphs minimizing the radius or the diameter, Math. Slovaca, 36, 289-296 (1986) · Zbl 0613.05035
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.