Closed orders and closed graphs

被引:2
作者
Crupi, Marilena [1 ]
机构
[1] Univ Messina, Dipartimento Sci Matemat & Informat Sci Fis & Sci, Viale Ferdinado Stagno Alcontres 31, I-98166 Messina, Italy
来源
ANALELE STIINTIFICE ALE UNIVERSITATII OVIDIUS CONSTANTA-SERIA MATEMATICA | 2016年 / 24卷 / 02期
关键词
Closed order; closed graphs; proper interval order; proper interval graphs; PROPER; RECOGNITION; ALGORITHMS;
D O I
10.1515/auom-2016-0034
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
The class of closed graphs by a linear ordering on their sets of vertices is investigated. A recent characterization of such a class of graphs is analyzed by using tools from the proper interval graph theory.
引用
收藏
页码:159 / 167
页数:9
相关论文
共 17 条
[1]   TESTING FOR CONSECUTIVE ONES PROPERTY, INTERVAL GRAPHS, AND GRAPH PLANARITY USING PQ-TREE ALGORITHMS [J].
BOOTH, KS ;
LUEKER, GS .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1976, 13 (03) :335-379
[2]  
Cox D.A., ARS COMBINATORIA APP
[3]   Closed graphs are proper interval graphs [J].
Crupi, Marilena ;
Rinaldo, Giancarlo .
ANALELE STIINTIFICE ALE UNIVERSITATII OVIDIUS CONSTANTA-SERIA MATEMATICA, 2014, 22 (03) :37-44
[4]  
Crupi M, 2011, ELECTRON J COMB, V18
[5]   Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs [J].
Deng, XT ;
Hell, P ;
Huang, J .
SIAM JOURNAL ON COMPUTING, 1996, 25 (02) :390-403
[6]   COHEN-MACAULAY BINOMIAL EDGE IDEALS [J].
Ene, Viviana ;
Herzog, Juergen ;
Hibi, Takayuki .
NAGOYA MATHEMATICAL JOURNAL, 2011, 204 :57-68
[7]   The Roberts characterization of proper and unit interval graphs [J].
Gardi, Frederic .
DISCRETE MATHEMATICS, 2007, 307 (22) :2906-2908
[8]   CHARACTERIZATION OF COMPARABILITY GRAPHS + OF INTERVAL GRAPHS [J].
GILMORE, PC ;
HOFFMAN, AJ .
CANADIAN JOURNAL OF MATHEMATICS, 1964, 16 (03) :539-&
[9]  
Golumbic M., 1980, ALGORITHM GRAPH THEO
[10]   Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing [J].
Habib, M ;
McConnell, R ;
Paul, C ;
Viennot, L .
THEORETICAL COMPUTER SCIENCE, 2000, 234 (1-2) :59-84