On operations preserving semi-transitive orientability of graphs

Ilkyoo Choi (), Jinha Kim () and Minki Kim ()
Additional contact information
Ilkyoo Choi: Hankuk University of Foreign Studies
Jinha Kim: Seoul National University
Minki Kim: Technion – Israel Institute of Technology

Journal of Combinatorial Optimization, 2019, vol. 37, issue 4, No 15, 1366 pages

Abstract: Abstract We consider the class of semi-transitively orientable graphs, which is a much larger class of graphs compared to transitively orientable graphs, in other words, comparability graphs. Ever since the concept of a semi-transitive orientation was defined as a crucial ingredient of the characterization of alternation graphs, also known as word-representable graphs, it has sparked independent interest. In this paper, we investigate graph operations and graph products that preserve semi-transitive orientability of graphs. The main theme of this paper is to determine which graph operations satisfy the following statement: if a graph operation is possible on a semi-transitively orientable graph, then the same graph operation can be executed on the graph while preserving the semi-transitive orientability. We were able to prove that this statement is true for edge-deletions, edge-additions, and edge-liftings. Moreover, for all three graph operations, we show that the initial semi-transitive orientation can be extended to the new graph obtained by the graph operation. Also, Kitaev and Lozin explicitly asked if certain graph products preserve the semi-transitive orientability. We answer their question in the negative for the tensor product, lexicographic product, and strong product. We also push the investigation further and initiate the study of sufficient conditions that guarantee a certain graph operation to preserve the semi-transitive orientability.

Keywords: Oriented graphs; Semi-transitive orientation; Graph Operations (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0358-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:37:y:2019:i:4:d:10.1007_s10878-018-0358-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-0358-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().