Minimizing and maximizing the diameter in orientations of graphs |
| |
| Authors: | G. Gutin |
| |
| Affiliation: | 1. Raymond and Beverly Sackler Faculty of Exact Sciences, School of Mathematical Sciences, Tel Aviv University, 69978, Ramat-Aviv, Israel
|
| |
| Abstract: | For a graph G, letG′(G″) denote an orientation ofG having maximum (minimum respectively) finite diameter. We show that the length of the longest path in any 2-edge connected (undirected) graph G is precisely diam(G′). LetK(m l ,m 2,...,m n) be the completen-partite graph with parts of cardinalitiesm 1 m2, …,m n . We prove that ifm 1 = m2 = … =m n = m,n ≥ 3, then diam(K″(m1,m2,...,mn)) = 2, unless m=1 andn = 4. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
