Name
Abstract | ||
|---|---|---|
Let G be a bridgeless connected undirected (b.c.u.) graph. The oriented diameter of G, OD(G), is given by OD(G)=min{diam(H): H is an orientation of G}, where diam(H) is the maximum length computed over the lengths of all the shortest directed paths in H. This work starts with a result stating that, for every b.c.u, graph G, its oriented diameter OD(G) and its domination number γ(G) are linearly related as follows: OD(G)≤ 9γ(G)-5.Since-as shown by Corneil et al. (SIAM J. Discrete Math. 10 (1997) 399)-γ(G)≤ diam(G) for every AT-free graph G, it follows that OD(G) ≤ 9 diam(G)-5 for every b.c.u. AT-free graph G. Our main result is the improvement of the previous linear upper bound. We show that OD(G) ≤ 2 diam(G)+11 for every b.c.u. AT-free graph G. For some subclasses we obtain better bounds: OD(G) ≤ 3/2 diam(G)+25/2 for every interval b.c.u. graph G, and OD(G) ≤ 5/4 diam(G)+ 29/2 for every 2-connected interval b.c.u. graph G. We prove that, for the class of b.c.u. AT-free graphs and its previously mentioned subclasses, all our bounds are optimal (up to additive constants). |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/S0166-218X(03)00376-7 | Discrete Applied Mathematics |
Keywords | Field | DocType |
maximum length,better bound,main result,2-connected interval,domination number,linear bound,at-free graph,oriented diameter,graph g,graph g.,siam j. discrete math,diameter,interval graph,orientation,upper bound | Discrete mathematics,Linear equation,Graph,Combinatorics,Shortest path problem,Bound graph,Interval graph,Upper and lower bounds,Domination analysis,Mathematics | Journal |
Volume | Issue | ISSN |
141 | 1-3 | Discrete Applied Mathematics |
Citations | PageRank | References |
9 | 0.68 | 14 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fedor V. Fomin | 1 | 3139 | 192.21 |
| Martín Matamala | 2 | 158 | 21.63 |
| Erich Prisner | 3 | 225 | 26.12 |
| Ivan Rapaport | 4 | 199 | 21.93 |