{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:44:02Z","timestamp":1759063442121},"reference-count":11,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2010,2,5]],"date-time":"2010-02-05T00:00:00Z","timestamp":1265328000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2010,3]]},"abstract":"<jats:p>A digraph is <jats:italic>m<\/jats:italic>-labelled if every arc is labelled by an integer in {1, .\u00a0.\u00a0., <jats:italic>m<\/jats:italic>}. Motivated by wavelength assignment for multicasts in optical networks, we introduce and study <jats:italic>n<\/jats:italic>-fibre colourings of labelled digraphs. These are colourings of the arcs of <jats:italic>D<\/jats:italic> such that at each vertex <jats:italic>v<\/jats:italic>, and for each colour \u03b1, in(<jats:italic>v<\/jats:italic>, \u03b1) + out(<jats:italic>v<\/jats:italic>, \u03b1) \u2264 <jats:italic>n<\/jats:italic> with in(<jats:italic>v<\/jats:italic>, \u03b1) the number of arcs coloured \u03b1 entering <jats:italic>v<\/jats:italic> and out(<jats:italic>v<\/jats:italic>, \u03b1) the number of labels <jats:italic>l<\/jats:italic> such that there is at least one arc of label <jats:italic>l<\/jats:italic> leaving <jats:italic>v<\/jats:italic> and coloured with \u03b1. The problem is to find the minimum number of colours \u03bb<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>(<jats:italic>D<\/jats:italic>) such that the <jats:italic>m<\/jats:italic>-labelled digraph <jats:italic>D<\/jats:italic> has an <jats:italic>n<\/jats:italic>-fibre colouring. In the particular case when <jats:italic>D<\/jats:italic> is 1-labelled, \u03bb<jats:sub>1<\/jats:sub>(<jats:italic>D<\/jats:italic>) is called the directed star arboricity of <jats:italic>D<\/jats:italic>, and is denoted by dst(<jats:italic>D<\/jats:italic>). We first show that dst(<jats:italic>D<\/jats:italic>) \u2264 2\u0394<jats:sup>\u2212<\/jats:sup>(<jats:italic>D<\/jats:italic>)+1, and conjecture that if \u0394<jats:sup>\u2212<\/jats:sup>(<jats:italic>D<\/jats:italic>) \u2265 2, then dst(<jats:italic>D<\/jats:italic>) \u2264 2\u0394<jats:sup>\u2212<\/jats:sup>(<jats:italic>D<\/jats:italic>). We also prove that for a subcubic digraph <jats:italic>D<\/jats:italic>, then dst(<jats:italic>D<\/jats:italic>) \u2264 3, and that if \u0394<jats:sup>+<\/jats:sup>(<jats:italic>D<\/jats:italic>), \u0394<jats:sup>\u2212<\/jats:sup>(<jats:italic>D<\/jats:italic>) \u2264 2, then dst(<jats:italic>D<\/jats:italic>) \u2264 4. Finally, we study \u03bb<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>(<jats:italic>m<\/jats:italic>, <jats:italic>k<\/jats:italic>) = max{\u03bb<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>(<jats:italic>D<\/jats:italic>) | <jats:italic>D<\/jats:italic> is <jats:italic>m<\/jats:italic>-labelled and \u0394<jats:sup>\u2212<\/jats:sup>(<jats:italic>D<\/jats:italic>) \u2264 <jats:italic>k<\/jats:italic>}. We show that if <jats:italic>m<\/jats:italic> \u2265 <jats:italic>n<\/jats:italic>, then <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548309990551_inline1\"><jats:alt-text>$\\ds \\bigl\\lceil\\frac{m}{n}\\bigl\\lceil \\frac{k}{n}\\bigr\\rceil + \\frac{k}{n} \\bigr\\rceil\\leq \\lambda_n(m, k) \\leq\\bigl\\lceil\\frac{m}{n}\\bigl\\lceil \\frac{k}{n}\\bigr\\rceil + \\frac{k}{n} \\bigr\\rceil + C \\frac{m^2\\log k}{n}$<\/jats:alt-text><\/jats:inline-graphic> for some constant <jats:italic>C<\/jats:italic>. We conjecture that the lower bound should be the correct value of \u03bb<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>(<jats:italic>m<\/jats:italic>, <jats:italic>k<\/jats:italic>).<\/jats:p>","DOI":"10.1017\/s0963548309990551","type":"journal-article","created":{"date-parts":[[2010,2,5]],"date-time":"2010-02-05T09:00:48Z","timestamp":1265360448000},"page":"161-182","source":"Crossref","is-referenced-by-count":5,"title":["WDM and Directed Star Arboricity"],"prefix":"10.1017","volume":"19","author":[{"given":"OMID","family":"AMINI","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"FR\u00c9D\u00c9RIC","family":"HAVET","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"FLORIAN","family":"HUC","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ST\u00c9PHAN","family":"THOMASS\u00c9","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2010,2,5]]},"reference":[{"key":"S0963548309990551_ref11","first-page":"25","article-title":"On an estimate of the chromatic class of a p-graph","volume":"3","author":"Vizing","year":"1964","journal-title":"Metody Diskret. Analyz."},{"key":"S0963548309990551_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(95)00342-T"},{"key":"S0963548309990551_ref5","first-page":"77","article-title":"Covering branchings","volume":"41","author":"Frank","year":"1979","journal-title":"Acta Scientiarum Mathematicarum"},{"key":"S0963548309990551_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305230"},{"key":"S0963548309990551_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(89)90073-3"},{"key":"S0963548309990551_ref7","first-page":"91","article-title":"Traffic grooming in a multi-layer network","volume":"2","author":"Lardies","year":"2001","journal-title":"Optical Networks Magazine"},{"key":"S0963548309990551_ref8","doi-asserted-by":"publisher","DOI":"10.1109\/35.933446"},{"key":"S0963548309990551_ref10","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"Schrijver","year":"2003"},{"key":"S0963548309990551_ref3","unstructured":"[3] Brandt R. (2003) Multicasting using WDM in multifiber optical star networks. Thesis, UCSB."},{"key":"S0963548309990551_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2006.06.007"},{"key":"S0963548309990551_ref4","doi-asserted-by":"publisher","DOI":"10.1142\/S0219265905001484"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548309990551","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T20:32:38Z","timestamp":1556483558000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548309990551\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,2,5]]},"references-count":11,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,3]]}},"alternative-id":["S0963548309990551"],"URL":"https:\/\/doi.org\/10.1017\/s0963548309990551","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,2,5]]}}}