Julien Bensmail ; Romaric Duvignau ; Sergey Kirgizov - The complexity of deciding whether a graph admits an orientation with fixed weak diameter

dmtcs:2161 - Discrete Mathematics & Theoretical Computer Science, February 17, 2016, Vol. 17 no. 3 - https://doi.org/10.46298/dmtcs.2161
The complexity of deciding whether a graph admits an orientation with fixed weak diameter

Authors: Julien Bensmail 1; Romaric Duvignau ORCID-iD2; Sergey Kirgizov 3

  • 1 Danmarks Tekniske Universitet = Technical University of Denmark
  • 2 Laboratoire Bordelais de Recherche en Informatique
  • 3 Laboratoire Electronique, Informatique et Image [UMR6306]

An oriented graph $\overrightarrow{G}$ is said weak (resp. strong) if, for every pair $\{ u,v \}$ of vertices of $\overrightarrow{G}$, there are directed paths joining $u$ and $v$ in either direction (resp. both directions). In case, for every pair of vertices, some of these directed paths have length at most $k$, we call $\overrightarrow{G}$ $k$-weak (resp. $k$-strong). We consider several problems asking whether an undirected graph $G$ admits orientations satisfying some connectivity and distance properties. As a main result, we show that deciding whether $G$ admits a $k$-weak orientation is NP-complete for every $k \geq 2$. This notably implies the NP-completeness of several problems asking whether $G$ is an extremal graph (in terms of needed colours) for some vertex-colouring problems.

Volume: Vol. 17 no. 3
Section: Graph Theory
Published on: February 17, 2016
Submitted on: September 18, 2014
Keywords: complexity, weak diameter, strong diameter,oriented graph,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
    Source : OpenAIRE Graph
  • Graph Theory: Colourings, flows, and decompositions.; Funder: European Commission; Code: 320812

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.7151/dmgt.1237
  • 10.7151/dmgt.1237
Analogues of cliques for oriented coloring

Consultation statistics

This page has been seen 401 times.
This article's PDF has been downloaded 301 times.