Gennady Fridman

Critical and Maximal Directed Graphs

• Broschiertes Buch

Produktbeschreibung

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.

Produktdetails

• Verlag: LAP Lambert Academic Publishing
• Seitenzahl: 56
• Erscheinungstermin: 10. Mai 2018
• Englisch
• Abmessung: 220mm x 150mm x 4mm
• Gewicht: 102g
• ISBN-13: 9786139819188
• ISBN-10: 6139819180
• Artikelnr.: 52677915

Autorenporträt

Graduated from the Physics and Mathematics School at Novosibirsk Academic town and Math Department of the Novosibirsk State University. Researcher at the A.A.Lyapunov Laboratory of Theoretical Cybernetics and Math Dept of the Institute of Economics. Associate Prof., later Chair Prof. for Applied and Computing Math of the Omsk State University.