[comp.theory] SUMMARY: path properties of graphs

casais@uni2a.unige.ch (11/07/90)

        Several weeks ago, I posted the following enquiry:

          Is there a mathematical (statistical) characterization
          of the length and number of paths between the nodes of 
          a directed graph without circuits ? 

        What I wanted was actually the known bounds on the average
    pathlength and number of paths in a DAG, or for special families
    of directed graphs. Here is what I have been able to find; it is
    not much. The literature on the subject is scarce, as several persons
    told me:

        "I was interested in a related problem: in a complete directed graph 
         with edge weights chosen independently and uniformly from [-x,1-x], 
         with 0<x<1, what are the statistics on shortest paths?  I found that 
         very little was known, and could not analytically determine the 
         answers to my questions, and so resorted to simulation." 

                                        <ney@camelback.Princeton.edu>

        "I've been browsing in this literature almost exclusively for results
         on clique and coloring problems, so I'm afraid I can't help much
         regarding directed graphs. I recall though Bollobas saying that 
         probabilistic results on directed graphs were quite scant."     

                                        <halldors@paul.rutgers.edu>

        The best reference giving some interesting results on distance
    properties --- notably diameters and cycles --- for random graphs is:

            B\'ela Bollob\'as
            Random graphs
            Academic Press, 1985

        It does not talk about average path length in random graphs, though.
    The following book was also suggested, but does not contain what I was 
    looking for: 

            Fred Buckley and Frank Harary
            Distances in graphs
            Addison-Wesley, 1989

        I have also browsed through the AMS Mathematical Reviews, but did not
    come up with anything directly related to the subject. Most papers study
    the bounds on graph diameters or the length of the longest cycle, on the
    basis of the number and maximum/minimum degrees of the vertices. For
    example:

            Mikl\'os Ajtai, Koml\'os J\'anos, and Szemer\'edi Endre
            The largest path in a random graph
            Combinatorica, 1-1, 1981, pp 1-12

            Bill Jackson
            Long paths and cycles in oriented graphs
            Journal of Graph Theory, 5-2, 1981, pp 145-157

            Richard Loulou
            Maximal paths in random dynamic graphs
            European Journal of Combinatorics, 8-3, 1987, pp 303-311

            N. Kusolitsch
            On the 1st long path and the number of long paths in certain
                directed random graphs
            Limit Theorems in Probability and Statistics, I,II, pp 631-647,
                Colloquium of the Mathematical Society J\'anos Bolyai no 36,
                North-Holland 1982

            N. Kusolitsch and T. Nemetz
            R\'ev\'esz-Erd\"os-type asymptotic bounds on the length of the
                longest path in certain random graphs
            Limit Theorems in Probability and Statistics, I,II, pp 649-665,
                Colloquium of the Mathematical Society J\'anos Bolyai no 36,
                North-Holland 1982

            Fan R. K. Cheng
            Diameters in graphs: old problems and new results
            18th Southeastern International Conference on Combinatorics,
                Graph Theory and Computing, Boca Raton, 1987, pp 295-317 

        There are many more references on related subjects in the mathematical
    literature. Needless to say, they are highly theoretical and require a 
    solid background in mathematics. Anybody interested should consult section
    5C of the AMS Reviews to find more about them. 

        After delving in our library, I have come up with two references that 
    study the problem of average path length for trees:

            Hosam M. Mahmoud
            On the average internal path length of m-ary search trees
            Acta Informatica, 23-1, 1986, pp 111-117

            Rolf Klein and Derick Wood 
            On the path length of binary trees
            JACM, 36-2 April 1986, pp 280-289

        I have not tried to launch a full-scale bibliographic search for the 
    articles and articles on the domain. Somebody deeply involved in the 
    problem might want to complete the above list of references. 

        Many thanks to the persons that helped me by providing pointers
    and advice:

        Chris               chris%cs@hub.ucsb.edu
        Magnus              halldors@paul.rutgers.edu
        Kevin McCarty       cup.portal.com!kmc@Sun.com@portal.uucp
        Neal Young          ney@cs.princeton.edu


Eduardo Casais

Centre Universitaire d'Informatique     EARN/BITNET:   casais@cgeuge51.bitnet
12, rue du Lac                          EAN/MHS:       casais@cuisun.unige.ch
1207 Geneve                             UUCP:          mcsun!cui!casais
SUISSE                                                 mcsun!chx400!cui!casais
                                        Telephone:     (41) (22) 787.65.86
                                        Telefax:       (41) (22) 735.39.05