Journal of Combinatorics

Volume 15 (2024)

Number 1

Some results on structure of arbitrary arc-locally (out) in-semicomplete digraphs

Pages: 89 – 103

DOI: https://dx.doi.org/10.4310/JOC.2024.v15.n1.a5

Authors

Lucas Freitas (Institute of Computing, State University of Campinas, SP, Brazil)

Orlando Lee (Institute of Computing, State University of Campinas, SP, Brazil)

Abstract

Arc-locally semicomplete digraphs and arc-locally in-semicomplete digraphs were introduced by Bang–Jensen as a common generalization of both semicomplete and semicomplete bipartite digraphs in 1993. Later, Bang–Jensen (2004), Galeana–Sánchez and Goldfeder (2009) and Wang and Wang (2009) provided a characterization of strong arc-locally semicomplete digraphs. In 2009,Wang andWang provided a characterization of strong arc-locally in-semicomplete digraphs. In 2012, Galeana–Sánchez and Goldfeder provided a characterization of arbitrary arc-locally semicomplete digraphs which generalizes some results by Bang–Jensen. In this paper, we characterize the structure of arbitrary arc-locally (out) in-semicomplete digraphs and arbitrary arc-locally semicomplete digraphs.

Keywords

arc-locally semicomplete digraph, arc-locally in-semicomplete digraph, perfect graph, generalization of tournaments

Received 2 October 2021

Accepted 25 February 2023

Published 7 November 2023