On powers of circular arc graphs and proper circular arc graphs

被引:6
作者
Flotow, C
机构
[1] Mathematisches Seminar, Universität Hamburg, 20146 Hamburg
关键词
D O I
10.1016/0166-218X(95)00091-5
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
In this paper it is shown that the class K of circular are graphs is closed under the operation of power; this means, G is an element of K implies G(k) is an element of K for any positive integer k. Furthermore, G(k) is an element of K implies G(k+2) is an element of K and if diam(G(k)) greater than or equal to 4 then G(k) is an element of K implies G(k+1) is an element of K. Another result on the powers of directed graphs is that if G(k) belongs to the class of in-, out-, or local tournaments, then so does G(k+1). This result is used to prove the closedness of proper circular are graphs under the power operation.
引用
收藏
页码:199 / 207
页数:9
相关论文
共 13 条