ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2017-2018): c. 84%
Mathematicae Graph Theory 20(1) (2000) 39-56DOI: 10.7151/dmgt.1105
Department of Mathematics, PEF, University of Maribor
Koroska 160, si-2000 Maribor, Slovenia
FME, University of Maribor
Smetanova 17, si-2000 Maribor, Slovenia
In this paper we show that methods for recognizing Cartesian graph bundles can be
generalized to weighted digraphs. The main result is an algorithm which lists the sets of
degenerate arcs for all representations of digraph as a weighted directed Cartesian graph
bundle over simple base digraphs not containing transitive tournament on three vertices.
Two main notions are used. The first one is the new relation δ*→defined among the arcs of a digraph as a weighted directed analogue of the well-known
relation δ*. The second one is the concept of
half-convex subgraphs. A subgraph H is half-convex in G if any vertex x ∈ G∖H has at most one predecessor and at most one successor.
Keywords: graph bundles, Cartesian graph product, weighted digraphs,
1991 Mathematics Subject Classification: 05C60.
Received 8 January 1999
Revised 16 March 2000