Spanning tree of a multiple graph

Alexander V. Smirnov ()
Additional contact information
Alexander V. Smirnov: P.G. Demidov Yaroslavl State University

Journal of Combinatorial Optimization, 2022, vol. 43, issue 4, No 6, 850-869

Abstract: Abstract We study undirected multiple graphs of any natural multiplicity $$k>1$$ 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)$$ ( 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.

Keywords: Multiple graph; Multiple tree; Spanning tree; Complete spanning tree; Minimum spanning tree (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00810-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:43:y:2022:i:4:d:10.1007_s10878-021-00810-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00810-5

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().