zbMATH — the first resource for mathematics

WDM and directed star arboricity. (English) Zbl 1216.05044
Summary: A digraph is \(m\)-labelled if every arc is labelled by an integer in \(\{1,\dots, m\}\). Motivated by wavelength assignment for multicasts in optical networks, we introduce and study \(n\)-fibre colourings of labelled digraphs. These are colourings of the arcs of \(D\) such that at each vertex \(v\), and for each colour \(\alpha \), in\((v, \alpha )\) \(+\) out\((v, \alpha ) \leqslant n\) with in\((v, \alpha )\) the number of arcs coloured \(\alpha \) entering \(v\) and out\((v, \alpha )\) the number of labels \(l\) such that there is at least one arc of label \(l\) leaving \(v\) and coloured with \(\alpha \).
The problem is to find the minimum number of colours \(\lambda _{n}(D)\) such that the \(m\)-labelled digraph \(D\) has an \(n\)-fibre colouring. In the particular case when \(D\) is 1-labelled, \(\lambda _{1}(D)\) is called the directed star arboricity of \(D\), and is denoted by dst\((D)\). We first show that dst\((D) \leqslant 2\Delta ^{ - }(D)+1\), and conjecture that if \(\Delta ^{ - }(D) \geqslant 2\), then dst\((D) \leqslant 2\Delta ^{ - }(D)\). We also prove that for a subcubic digraph \(D\), then dst\((D) \leq 3\), and that if \(\Delta ^{+}(D), \Delta ^{ - }(D) \leq 2\), then dst\((D) \leq 4\).
Finally, we study \(\lambda _{n}(m, k) = \max\{\lambda _{n}(D) | D\) is \(m\)-labelled and \(\Delta ^{ - }(D) \leq k\}\). We show that if \(m \geqslant n\), then \(\lceil \frac m n \lceil \frac k n \rceil +\frac k n \rceil \leqslant \lambda _n (m,k)\leqslant \lceil \frac m n \lceil \frac k n \rceil +\frac k n \rceil + C\frac{m^2 \log k}{n}\) for some constant \(C\). We conjecture that the lower bound should be the correct value of \(\lambda _n (m,k)\).

05C20 Directed graphs (digraphs), tournaments
Full Text: DOI
[1] DOI: 10.1016/j.disc.2006.06.007 · Zbl 1106.05050
[2] DOI: 10.1109/35.933446
[3] Lardies, Optical Networks Magazine 2 pp 91– (2001)
[4] DOI: 10.1016/0012-365X(95)00342-T · Zbl 0871.05022
[5] Schrijver, Combinatorial Optimization: Polyhedra and Efficiency (2003)
[6] DOI: 10.1142/S0219265905001484 · Zbl 05001636
[7] DOI: 10.1007/BF01305230 · Zbl 0780.05043
[8] DOI: 10.1016/0012-365X(89)90073-3 · Zbl 0684.05033
[9] Vizing, Metody Diskret. Analyz. 3 pp 25– (1964)
[10] Frank, Acta Scientiarum Mathematicarum 41 pp 77– (1979)
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.