Details

Autor(en) / Beteiligte

• Smirnov, Alexander V.

Titel

Spanning tree of a multiple graph

Ist Teil von

• Journal of combinatorial optimization, 2022-05, Vol.43 (4), p.850-869

Ort / Verlag

New York: Springer US

Erscheinungsjahr

2022

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• We study undirected multiple graphs of any natural multiplicity k > 1 . There are edges of three types: ordinary edges, multiple edges and multi-edges. Each edge of the last two types is a union of k linked edges, which connect 2 or ( k + 1 ) vertices, correspondingly. The linked edges should be used simultaneously. The multiple tree is a multiple graph with no multiple cycles. The number of edges may be different for multiple trees with the same number of vertices. We prove lower and upper bounds on the number of edges in an arbitrary multiple tree. Also we consider spanning trees of an arbitrary multiple graph. Special interest is paid to the case of complete spanning trees. Their peculiarity is that a multiple path joining any two selected vertices exists in the tree if and only if such a path exists in the initial graph. We study the properties of complete spanning trees and the problem of finding the minimum complete spanning tree of a weighted multiple graph.