Edge-Wide-Diameter of Graphs with Diameter *d*

Toru Kojima^{1}, Kiyoshi Ando^{1} and A. Kaneko^{2}

kojima@im.uec.ac.jp, ando@ice.uec.ac.jp

Annals of Combinatorics 6 (1) p.57-64 March, 2002

Abstract:

Let *k* be a positive integer and let *G* be a graph.
For two distinct vertices , the *k*-edge-wide-distance
between *x* and *y* is the minimum integer *l* such that
there exist *k* edge-disjoint (*x, y*)-paths whose lengths are at most *l*.
We define =0.
The *k*-edge-wide-diameter of *G* is the maximum value of
the *k*-edge-wide-distance between two vertices of *G*.
We prove that for a fixed positive integer *k*, the
*k*-edge-wide-diameter of a *k*-edge-connected graph with diameter *d* is
bounded by a polynomial of *d* with degree *k*.

References:

1. K. Ando and A. Kaneko, 2-wide-diameter of 2-edge-connected graph with diameter d, preprint.

2. R.J. Faudree, Some strong variations of connectivity, In: Combinatorics, Paul Erdős is Eighty, Vol. 1, 125–144, Bolyai Soc. Math. Stud., János Bolyai Math. Soc., Budapest, 1993.

3. R.J. Faudree, R. J. Gould, and R. H. Schelp, Menger path systems, J. Combin. Math. Combin. Comput. 6 (1989) 9–21.

4. R.J. Faudree, M.S. Jacobson, E.T. Ordman, R.H. Schelp, and Zs. Tuza, Menger's theorem and short paths, J. Combin. Math. Combin. Comput. 2 (1987) 235–253.

5. D.F. Hsu, On container width and length in graphs, groups, and networks, IEICE Trans. Fundamentals E77-A (1994) 668–680.