On powers of circular arc graphs and proper circular arc graphs
type: Item
instance of: scholarly article
title: On powers of circular arc graphs and proper circular arc graphs
zbMATH Open document ID: 0857.05030
DOI: 10.1016/0166-218X(95)00091-5
author: Carsten Flotow
published in: Discrete Applied Mathematics
publication date: 1997-02-26T00:00:00Z
review text: Let \(\mathcal K\) denote the class of circular arc graphs. The author gives a new proof that if a graph \(G\in {\mathcal K}\), then the power \(G^n\in {\mathcal K}\) for any positive integer \(n\). Moreover, he proves that if \(G^n\in {\mathcal K}\) then \(G^{n+2}\in {\mathcal K}\) and if \(\text{diam}(G^n)\geq 4\) then \(G^n\in {\mathcal K}\) implies \(G^{n+1}\in {\mathcal K}\). For digraphs the author gives an exact terminology and several interesting results. E.g. he proves that if a directed graph \(G^n\) belongs to the class of in-, out- or local tournaments, then \(G^{n+1}\) belongs to the same class. Moreover, the author gives an interesting discussion about possible applications, but no concrete application is given.
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 933096
zbMATH Keywords: distance
zbMATH Keywords: tournaments
zbMATH Keywords: circular arc graphs
zbMATH Keywords: power
zbMATH Keywords: digraphs
reviewed by: Ferdinand Gliviak
MaRDI profile type: Publication
cites work: In-tournament digraphs
cites work: Distances in cocomparability graphs and their powers
cites work: Q3222876
cites work: On powers of \(m\)-trapezoid graphs
cites work: Graphs whose powers are chordal and graphs whose powers are interval graphs
cites work: Efficient algorithms for interval graphs and circular-arc graphs
cites work: Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
cites work: On powers and centers of chordal graphs
cites work: Q3783331
cites work: Q4032992
cites work: A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
cites work: An Efficient Test for Circular-Arc Graphs
description: scientific article; zbMATH DE number 933096