Premium
Oriented diameter of graphs with given maximum degree
Author(s) -
Dankelmann Peter,
Guo Yubao,
Surmacs Michel
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22181
Subject(s) - combinatorics , bipartite graph , mathematics , degree (music) , orientation (vector space) , graph , induced subgraph , upper and lower bounds , order (exchange) , enhanced data rates for gsm evolution , discrete mathematics , geometry , vertex (graph theory) , computer science , mathematical analysis , telecommunications , physics , finance , acoustics , economics
In this article, we show that every bridgeless graph G of order n and maximum degree Δ has an orientation of diameter at most n − Δ + 3 . We then use this result and the definitionN G ( H ) = ⋃ v ∈ V ( H )N G ( v ) ∖ V ( H ) , for every subgraph H of G , to give better bounds in the case that G contains certain clusters of high‐degree vertices, namely: For every edge e , G has an orientation of diameter at mostn − | N G( e ) | + 4 , if e is on a triangle and at mostn − | N G( e ) | + 5 , otherwise. Furthermore, for every bridgeless subgraph H of G , there is such an orientation of diameter at mostn − | N G( H ) | + 3 . Finally, if G is bipartite, then we show the existence of an orientation of diameter at most 2 ( | A | − deg G ( s ) ) + 7 , for every partite set A of G and s ∈ V ( G ) ∖ A . This particularly implies that balanced bipartite graphs have an orientation of diameter at most n − 2 Δ + 7 . For each bound, we give a polynomial‐time algorithm to construct a corresponding orientation and an infinite family of graphs for which the bound is sharp.