AT-free graphs: linear bounds for the oriented diameter

✍ Scribed by Fedor V Fomin; Martı́n Matamala; Erich Prisner; Ivan Rapaport

• Book ID: 104294276
• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 268 KB
• Volume: 141
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(03)00376-7

✦ Synopsis

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) 6 9 (G) -5.

Since-as shown by Corneil et al. (SIAM J. Discrete Math. 10 (1997) 399)-(G) 6 diam(G) for every AT-free graph G, it follows that OD(G) 6 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) 6 2 diam(G)+11 for every b.c.u. AT-free graph G. For some subclasses we obtain better bounds: OD(G) 6 3 2 diam(G) + 25 2 for every interval b.c.u. graph G, and OD(G) 6 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).