<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 6 Issue 1" %>
Edge-Wide-Diameter of Graphs with Diameter d
Toru Kojima1, Kiyoshi Ando1 and A. Kaneko2
1University of Electro-Communications, Chofu, Tokyo, Japan
kojima@im.uec.ac.jp,    ando@ice.uec.ac.jp
2Kougakuin University, Shinjuku, Tokyo, Japan
Annals of Combinatorics 6 (1) p.57-64 March, 2002
AMS Subject Classification: 05C12
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.
Keywords: diameter, wide-diameter, edge-wide-diameter


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.