Graphs and digraphs represented by intervals and circular arcs

被引：1

作者：

Das, Ashok Kumar ^{[1
]}

Chakraborty, Ritapa ^{[1
]}

机构：

[1] Univ Calcutta, Dept Pure Math, 35 Ballygunge Circular Rd, Kolkata 700019, India

来源：

DISCRETE APPLIED MATHEMATICS | 2017年 / 228卷

关键词：

Circular arc graph; Circular arc digraph; Proper interval bigraph; Threshold graph; Proper circular arc bigraph; INDIFFERENCE DIGRAPHS; RECOGNITION; BIGRAPHS;

D O I：

10.1016/j.dam.2016.11.004

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper, we have shown that a graph is a circular arc graph if and only if the corresponding symmetric digraph with loops is a circular arc digraph. We characterize circular arc digraphs and circular arc graphs using circular ordering of their edges. We also characterize a circular arc graph as a union of an interval graph and a threshold graph. Finally, we characterize proper interval bigraphs and proper circular arc bigraphs using two linear orderings of their vertex set. (C) 2016 Elsevier B.V. All rights reserved.

引用

页码：41 / 49

页数：9

共 29 条

[1] [Anonymous], GRAPHS AND GENES
[2] [Anonymous], 2004, ANN DISCRETE MATH
[3] [Anonymous], CONGR NUMBER
[4] Circular-Arc Bigraphs and Its Subclasses
Basu, Asim
Das, Sandip
Ghosh, Shamik
Sen, Malay
[J]. JOURNAL OF GRAPH THEORY, 2013, 73 (04) : 361 - 376
[5] CONNECTION DIGRAPHS AND 2ND-ORDER LINE DIGRAPHS
BEINEKE, LW
ZAMFIRESCU, CM
[J]. DISCRETE MATHEMATICS, 1982, 39 (03) : 237 - 254
[6] Brown D., 2002, C NUMER, V157, P79
[7] New characterizations of proper interval bigraphs
Das, Ashok Kumar
Chakraborty, Ritapa
[J]. AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2015, 12 (01) : 47 - 53
[8] Forbidden substructure for interval digraphs/bigraphs
Das, Ashok Kumar
Das, Sandip
Sen, Malay
[J]. DISCRETE MATHEMATICS, 2016, 339 (02) : 1028 - 1051
[9] Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs
Deng, XT
Hell, P
Huang, J
[J]. SIAM JOURNAL ON COMPUTING, 1996, 25 (02) : 390 - 403
[10] List homomorphisms and circular arc graphs
Feder, T
Hell, P
Huang, J
[J]. COMBINATORICA, 1999, 19 (04) : 487 - 505

← 1 2 3 →