zbMATH — the first resource for mathematics

Direct product decompositions of digraphs. (English) Zbl 0673.05042
For an arbitrary digraph \(\bar G=(V,E)\) the covering graph \(C(\bar G)=(V,E)\) of \(\bar G\) is the graph, whose edges are those pairs (a,b)\(\in E\) for which (a,b)\(\in E\) or (b,a)\(\in E\). It is said that the direct product \(\prod_{i\in I}G_ i\) of graphs \(G_ i\) (i\(\in I)\) is the decomposition of the graph G if G is isomorphic to \(\prod_{i\in I}G_ i\). It is said that the decomposition \(\prod_{i\in I}G_ i\) of the graph \(C(\bar G)\) induces a decomposition of the digraph \(\bar G\) if there exist such digraphs \(G_ i\) (i\(\in I)\) that \(C(\bar G_ i)=G_ i\) for each \(i\in I\) and \(\bar G=\prod_{i\in I}\bar G_ i\). In the paper the question when the decomposition of \(C(\bar G)\) induces a decomposition of \(\bar G\) is investigated.
Reviewer: V.Fleischer

05C20 Directed graphs (digraphs), tournaments
05C99 Graph theory
Full Text: EuDML
[1] GEDEONOVÁ E.: The orientability of the direct product of graphs. Math. Slovaca 31, 1981, 71-78.
[2] HARARY F.: Graph Theory. Addison-Wesley, Reading, 1969. · Zbl 0196.27202
[3] JAKUBÍK J.: Weak product decompositions of discrete lattices. Czechoslov. Math. J. 21, 1971, 399-412. · Zbl 0224.06003
[4] JAKUBÍK J.: Weak product decompositions of partially ordered sets. Colloquium math. 25, 1972, 177-190. · Zbl 0213.29202
[5] JAKUBÍK J.: On weak direct decompositions of lattices and graphs. Czechoslov. Math. J. 35, 1985, 269-277. · Zbl 0576.06006
[6] JAKUBÍK J.: Covering graphs and subdirect decompositions of partially ordered sets. Math. Slovaca 36, 1986, 151-162. · Zbl 0603.06001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.