Critical and Maximal Directed Graphs
Versandkostenfrei!
Versandfertig in 6-10 Tagen
24,99 €
inkl. MwSt.
PAYBACK Punkte
12 °P sammeln!
In this Memoir we investigate finite directed graphs (digraphs) without loops with extreme properties with respect to certain metric or quasi-metric functionals. An n-vertex digraph G is called critical with respect to some functional F if adding an arbitrary missing arc to G results in decreasing F, and maximal if G has the maximum number of arcs among all n-vertex digraphs with the same value of F. The distance from a vertex x to a vertex y in the digraph G equals the minimum number of arcs in a directed path from x to y; if there are no directed path from x to y, then the distance is infini...
In this Memoir we investigate finite directed graphs (digraphs) without loops with extreme properties with respect to certain metric or quasi-metric functionals. An n-vertex digraph G is called critical with respect to some functional F if adding an arbitrary missing arc to G results in decreasing F, and maximal if G has the maximum number of arcs among all n-vertex digraphs with the same value of F. The distance from a vertex x to a vertex y in the digraph G equals the minimum number of arcs in a directed path from x to y; if there are no directed path from x to y, then the distance is infinite. The quasi-distance between x and y is defined as the minimum of distances from x to y and from y to x. We also define in the usual way diameter, radius and, similarly, quasi-diameter and quasi-radius of the digraph G. We characterize up to isomorphism the critical digraphs with infinite value of diameter, radius, quasi-diameter and quasi-radius. Moreover, the maximal digraphs with finitevalue of radius and quasi-diameter are studied. And we leave the problem of describing the maximal digraphs with finite quasi-radius to the next generation.
Andere Kunden interessierten sich für
