Oriented diameter of maximal outerplanar graphs

Xiaolin Wang; Yaojun Chen; Peter Dankelmann; Yubao Guo; Michel Surmacs; Lutz Volkmann

doi:10.1002/jgt.22707

Oriented diameter of maximal outerplanar graphs

Xiaolin Wang, Yaojun Chen, Peter Dankelmann, Yubao Guo, Michel Surmacs, Lutz Volkmann

Mathematics and Applied Mathematics

Research output: Contribution to journal › Article › peer-review

6 Citations (Scopus)

Abstract

Let (Formula presented.) be a finite connected undirected graph and (Formula presented.) a strong orientation of (Formula presented.). The diameter of (Formula presented.), denoted by (Formula presented.), is the maximum directed distance between any two vertices of (Formula presented.). The oriented diameter of (Formula presented.) is defined as (Formula presented.) In this paper, we show that (Formula presented.) for any maximal outerplanar graph (Formula presented.) of order (Formula presented.), with four exceptions, and the upper bound is sharp.

Original language	English
Pages (from-to)	426-444
Number of pages	19
Journal	Journal of Graph Theory
Volume	98
Issue number	3
DOIs	https://doi.org/10.1002/jgt.22707
Publication status	Published - Nov 2021

Keywords

diameter
maximal outerplanar graph
orientation
oriented diameter

ASJC Scopus subject areas

Geometry and Topology
Discrete Mathematics and Combinatorics

Access to Document

10.1002/jgt.22707

Cite this

@article{88a89819366a4fc18b36e15902a8e022,

title = "Oriented diameter of maximal outerplanar graphs",

abstract = "Let (Formula presented.) be a finite connected undirected graph and (Formula presented.) a strong orientation of (Formula presented.). The diameter of (Formula presented.), denoted by (Formula presented.), is the maximum directed distance between any two vertices of (Formula presented.). The oriented diameter of (Formula presented.) is defined as (Formula presented.) In this paper, we show that (Formula presented.) for any maximal outerplanar graph (Formula presented.) of order (Formula presented.), with four exceptions, and the upper bound is sharp.",

keywords = "diameter, maximal outerplanar graph, orientation, oriented diameter",

author = "Xiaolin Wang and Yaojun Chen and Peter Dankelmann and Yubao Guo and Michel Surmacs and Lutz Volkmann",

note = "Publisher Copyright: {\textcopyright} 2021 Wiley Periodicals LLC",

year = "2021",

month = nov,

doi = "10.1002/jgt.22707",

language = "English",

volume = "98",

pages = "426--444",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "3",

}

TY - JOUR

T1 - Oriented diameter of maximal outerplanar graphs

AU - Wang, Xiaolin

AU - Chen, Yaojun

AU - Dankelmann, Peter

AU - Guo, Yubao

AU - Surmacs, Michel

AU - Volkmann, Lutz

PY - 2021/11

Y1 - 2021/11

N2 - Let (Formula presented.) be a finite connected undirected graph and (Formula presented.) a strong orientation of (Formula presented.). The diameter of (Formula presented.), denoted by (Formula presented.), is the maximum directed distance between any two vertices of (Formula presented.). The oriented diameter of (Formula presented.) is defined as (Formula presented.) In this paper, we show that (Formula presented.) for any maximal outerplanar graph (Formula presented.) of order (Formula presented.), with four exceptions, and the upper bound is sharp.

AB - Let (Formula presented.) be a finite connected undirected graph and (Formula presented.) a strong orientation of (Formula presented.). The diameter of (Formula presented.), denoted by (Formula presented.), is the maximum directed distance between any two vertices of (Formula presented.). The oriented diameter of (Formula presented.) is defined as (Formula presented.) In this paper, we show that (Formula presented.) for any maximal outerplanar graph (Formula presented.) of order (Formula presented.), with four exceptions, and the upper bound is sharp.

KW - diameter

KW - maximal outerplanar graph

KW - orientation

KW - oriented diameter

UR - http://www.scopus.com/inward/record.url?scp=85109611154&partnerID=8YFLogxK

U2 - 10.1002/jgt.22707

DO - 10.1002/jgt.22707

M3 - Article

AN - SCOPUS:85109611154

SN - 0364-9024

VL - 98

SP - 426

EP - 444

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 3

ER -

Oriented diameter of maximal outerplanar graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this