{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T06:39:18Z","timestamp":1775716758194,"version":"3.50.1"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,1,28]],"date-time":"2024-01-28T00:00:00Z","timestamp":1706400000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,1,28]],"date-time":"2024-01-28T00:00:00Z","timestamp":1706400000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001321","name":"National Research Foundation","doi-asserted-by":"publisher","award":["118521"],"award-info":[{"award-number":["118521"]}],"id":[{"id":"10.13039\/501100001321","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100009978","name":"Ernest Oppenheimer Memorial Trust","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100009978","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2024,2]]},"abstract":"Abstract<\/jats:title>Let G<\/jats:italic> be a bridgeless graph. An orientation of G<\/jats:italic> is a digraph obtained from G<\/jats:italic> by assigning a direction to each edge. The oriented diameter of G<\/jats:italic> is the minimum diameter among all strong orientations of G<\/jats:italic>. The connected domination number $$\\gamma _c(G)$$<\/jats:tex-math>\n \n \n \u03b3<\/mml:mi>\n c<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of G<\/jats:italic> is the minimum cardinality of a set S<\/jats:italic> of vertices of G<\/jats:italic> such that every vertex of G<\/jats:italic> is in S<\/jats:italic> or adjacent to some vertex of S<\/jats:italic>, and which induces a connected subgraph in G<\/jats:italic>. We prove that the oriented diameter of a bridgeless graph G<\/jats:italic> is at most $$2 \\gamma _c(G) +3$$<\/jats:tex-math>\n \n 2<\/mml:mn>\n \n \u03b3<\/mml:mi>\n c<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n +<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> if $$\\gamma _c(G)$$<\/jats:tex-math>\n \n \n \u03b3<\/mml:mi>\n c<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is even and $$2 \\gamma _c(G) +2$$<\/jats:tex-math>\n \n 2<\/mml:mn>\n \n \u03b3<\/mml:mi>\n c<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n +<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> if $$\\gamma _c(G)$$<\/jats:tex-math>\n \n \n \u03b3<\/mml:mi>\n c<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is odd. This bound is sharp. For $$d \\in {\\mathbb {N}}$$<\/jats:tex-math>\n \n d<\/mml:mi>\n \u2208<\/mml:mo>\n N<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the d<\/jats:italic>-distance domination number $$\\gamma ^d(G)$$<\/jats:tex-math>\n \n \n \u03b3<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msup>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of G<\/jats:italic> is the minimum cardinality of a set S<\/jats:italic> of vertices of G<\/jats:italic> such that every vertex of G<\/jats:italic> is at distance at most d<\/jats:italic> from some vertex of S<\/jats:italic>. As an application of a generalisation of the above result on the connected domination number, we prove an upper bound on the oriented diameter of the form $$(2d+1)(d+1)\\gamma ^d(G)+ O(d)$$<\/jats:tex-math>\n \n \n (<\/mml:mo>\n 2<\/mml:mn>\n d<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n \n (<\/mml:mo>\n d<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n \n \u03b3<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msup>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n +<\/mml:mo>\n O<\/mml:mi>\n \n (<\/mml:mo>\n d<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Furthermore, we construct bridgeless graphs whose oriented diameter is at least $$(d+1)^2 \\gamma ^d(G) +O(d)$$<\/jats:tex-math>\n \n \n \n (<\/mml:mo>\n d<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:msup>\n \n \u03b3<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msup>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n +<\/mml:mo>\n O<\/mml:mi>\n \n (<\/mml:mo>\n d<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, thus demonstrating that our above bound is best possible apart from a factor of about 2.<\/jats:p>","DOI":"10.1007\/s00373-023-02741-w","type":"journal-article","created":{"date-parts":[[2024,1,28]],"date-time":"2024-01-28T10:02:07Z","timestamp":1706436127000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["The Oriented Diameter of Graphs with Given Connected Domination Number and Distance Domination Number"],"prefix":"10.1007","volume":"40","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4376-7546","authenticated-orcid":false,"given":"Peter","family":"Dankelmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jane","family":"Morgan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emily","family":"Rivett-Carnac","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,1,28]]},"reference":[{"key":"2741_CR1","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1016\/j.dam.2021.08.021","volume":"304","author":"J Babu","year":"2021","unstructured":"Babu, J., Benson, D., Rajendraprasad, D., Vaka, S.N.: An improvement to Chv\u00e1tal and Thomassen\u2019s upper bound for oriented diameter. Discrete Appl. Math. 304, 432\u2013440 (2021)","journal-title":"Discrete Appl. Math."},{"key":"2741_CR2","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.ejc.2015.03.003","volume":"49","author":"S Bau","year":"2015","unstructured":"Bau, S., Dankelmann, P.: Diameter of orientations of graphs with given minimum degree. Eur. J. Comb. 49, 126\u2013133 (2015)","journal-title":"Eur. J. Comb."},{"key":"2741_CR3","doi-asserted-by":"publisher","first-page":"P2.25","DOI":"10.37236\/9723","volume":"28","author":"B Chen","year":"2021","unstructured":"Chen, B., Chang, A.: Diameter three orientability of bipartite graphs. Electron. J. Comb. 28, P2.25 (2021)","journal-title":"Electron. J. Comb."},{"key":"2741_CR4","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0095-8956(78)90078-3","volume":"24","author":"V Chv\u00e1tal","year":"1978","unstructured":"Chv\u00e1tal, V., Thomassen, C.: Distances in orientations of graphs. J. Comb. Theory Ser. B 24, 61\u201375 (1978)","journal-title":"J. Comb. Theory Ser. B"},{"key":"2741_CR5","unstructured":"Cochran, G.: Large girth and small oriented diameter graphs (2022). arXiv:2201.07618"},{"key":"2741_CR6","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1007\/s00373-020-02261-x","volume":"37","author":"G Cochran","year":"2021","unstructured":"Cochran, G., Czabarka, \u00c9., Dankelmann, P., Sz\u00e9kely, L.: A size condition for diameter two orientable graphs. Graphs Comb. 37, 527\u2013544 (2021)","journal-title":"Graphs Comb."},{"key":"2741_CR7","doi-asserted-by":"publisher","first-page":"1063","DOI":"10.1016\/j.disc.2018.12.012","volume":"342","author":"\u00c9 Czabarka","year":"2019","unstructured":"Czabarka, \u00c9., Dankelmann, P., Sz\u00e9kely, L.: A degree condition for diameter two orientability of graphs. Discrete Math. 342, 1063\u20131065 (2019)","journal-title":"Discrete Math."},{"key":"2741_CR8","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1002\/jgt.22181","volume":"88","author":"P Dankelmann","year":"2018","unstructured":"Dankelmann, P., Guo, Y., Surmacs, M.: Oriented diameter of graphs with given maximum degree. J. Graph Theory 88, 5\u201317 (2018)","journal-title":"J. Graph Theory"},{"key":"2741_CR9","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/S1571-0653(04)00216-1","volume":"7","author":"FV Fomin","year":"2001","unstructured":"Fomin, F.V., Matamala, M., Prisner, E., Rapaport, I.: Bilateral orientations and domination. Electron. Notes Discrete Math. 7, 26\u201329 (2001)","journal-title":"Electron. Notes Discrete Math."},{"key":"2741_CR10","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0166-218X(03)00376-7","volume":"141","author":"FV Fomin","year":"2004","unstructured":"Fomin, F.V., Matamala, M., Prisner, E., Rapaport, I.: AT-free graphs: linear bounds for the oriented diameter. Discrete Appl. Math. 141, 135\u2013148 (2004)","journal-title":"Discrete Appl. Math."},{"key":"2741_CR11","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1002\/jgt.10160","volume":"45","author":"FV Fomin","year":"2004","unstructured":"Fomin, F.V., Matamala, M., Rapaport, I.: Complexity of approximating the oriented diameter of chordal graphs. J. Graph Theory 45, 255\u2013269 (2004)","journal-title":"J. Graph Theory"},{"key":"2741_CR12","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/S0012-365X(99)00373-8","volume":"219","author":"KM Koh","year":"2000","unstructured":"Koh, K.M., Tay, E.G.: On optimal orientations of $$G$$ vertex-multiplications. Discrete Math. 219, 153\u2013171 (2000)","journal-title":"Discrete Math."},{"key":"2741_CR13","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1007\/s003730200060","volume":"18","author":"KM Koh","year":"2002","unstructured":"Koh, K.M., Tay, E.G.: Optimal orientations of graphs and digraphs: a survey. Graphs Comb. 18, 745\u2013756 (2002)","journal-title":"Graphs Comb."},{"key":"2741_CR14","first-page":"109","volume":"14","author":"S Kurz","year":"2012","unstructured":"Kurz, S., L\u00e4tsch, M.: Bounds for the minimum oriented diameter. Discrete Math. Theor. Comput. Sci. 14, 109\u2013140 (2012)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"2741_CR15","doi-asserted-by":"crossref","unstructured":"Mondal, D., Parthiban, N., Rajasingh, I.: Oriented diameter of planar triangulations (2022). arXiv:2203.04253","DOI":"10.1007\/978-3-031-20796-9_14"},{"key":"2741_CR16","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1016\/j.disc.2005.04.012","volume":"297","author":"KL Ng","year":"2005","unstructured":"Ng, K.L., Koh, K.M.: On optimal orientation of cycle vertex multiplications. Discrete Math. 297, 104\u2013118 (2005)","journal-title":"Discrete Math."},{"key":"2741_CR17","doi-asserted-by":"publisher","first-page":"281","DOI":"10.2307\/2303897","volume":"46","author":"HE Robbins","year":"1939","unstructured":"Robbins, H.E.: A theorem on graphs, with an application to a problem of traffic control. Am. Math. Mon. 46, 281\u2013283 (1939)","journal-title":"Am. Math. Mon."},{"key":"2741_CR18","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/j.ejc.2016.08.006","volume":"59","author":"M Surmacs","year":"2017","unstructured":"Surmacs, M.: Improved bound on the oriented diameter of graphs with given minimum degree. Eur. J. Comb. 59, 187\u2013191 (2017)","journal-title":"Eur. J. Comb."},{"key":"2741_CR19","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1002\/jgt.22707","volume":"98","author":"X Wang","year":"2021","unstructured":"Wang, X., Chen, Y., Dankelmann, P., Guo, Y., Surmacs, M., Volkmann, L.: Oriented diameter of maximal outerplanar graphs. J. Graph Theory 98, 426\u2013444 (2021)","journal-title":"J. Graph Theory"},{"issue":"2","key":"2741_CR20","first-page":"Art. 6","volume":"8","author":"HWW Wong","year":"2021","unstructured":"Wong, H.W.W., Tay, E.G.: A complete characterization of vertex-multiplications of trees with diameter 5. Theory Appl. Graphs 8(2), Art. 6 (2021)","journal-title":"Theory Appl. Graphs"},{"issue":"1","key":"2741_CR21","first-page":"109","volume":"83","author":"HWW Wong","year":"2022","unstructured":"Wong, H.W.W., Tay, E.G.: Optimal orientations of vertex-multiplications of Cartesian products of graphs. Australas. J. Comb. 83(1), 109\u2013128 (2022)","journal-title":"Australas. J. Comb."},{"issue":"10","key":"2741_CR22","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2022.112999","volume":"345","author":"HWW Wong","year":"2022","unstructured":"Wong, H.W.W., Tay, E.G.: Arc reversals of cycles in orientations of $$G$$ vertex-multiplications. Discrete Math. 345(10), 112999 (2022)","journal-title":"Discrete Math."},{"issue":"1","key":"2741_CR23","first-page":"Art. 6","volume":"10","author":"HWW Wong","year":"2023","unstructured":"Wong, H.W.W., Tay, E.G.: Optimal orientations of vertex-multiplications of trees with diameter 4. Theory Appl. Graphs 10(1), Art. 6 (2023)","journal-title":"Theory Appl. Graphs"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-023-02741-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-023-02741-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-023-02741-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,30]],"date-time":"2024-03-30T18:06:03Z","timestamp":1711821963000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-023-02741-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,28]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["2741"],"URL":"https:\/\/doi.org\/10.1007\/s00373-023-02741-w","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,28]]},"assertion":[{"value":"25 May 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 November 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 December 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 January 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"18"}}