On optimal orientations of Cartesian products of trees (Q5936094)
From MaRDI portal
scientific article; zbMATH DE number 1612988
Language | Label | Description | Also known as |
---|---|---|---|
English | On optimal orientations of Cartesian products of trees |
scientific article; zbMATH DE number 1612988 |
Statements
On optimal orientations of Cartesian products of trees (English)
0 references
7 May 2002
0 references
An orientation \(D\) of a graph \(G\) is \((r,d)\)-invariant if the radius of \(D\) equals the radius of \(G\) and the diameter of \(D\) equals the diameter of \(G\). The authors prove that the Cartesian product of trees \(\prod^n_{i=1} T_i\) admits an \((r,d)\)-invariant orientation provided that \(\text{diam}(T_1)\geq \text{diam}(T_2)\geq 4\) for \(n=2\), and \(\text{diam}(T_1)\geq 5\), \(\text{diam}(T_2)\geq 4\) for \(n= 3\).
0 references
digraphs
0 references
orientation
0 references
radius
0 references
diameter
0 references
trees
0 references