Bipartite Permutation Graphs Are Reconstructible

被引：0
作者：
Kiyomi, Masashi [1 ]
Saitoh, Toshiki [2 ]
Uehara, Ryuhei [1 ]
机构：
[1] JAIST, Sch Informat Sci, 1-1 Asahidai, Nomi, Ishikawa 9231292, Japan
[2] ERATO, MINATO, Discrete Struct Manipulat Syst Project, JST, Sapporo, Hokkaido 0600814, Japan
来源：
COMBINATORIAL OPTIMIZATION AND APPLICATIONS, PT II | 2010年 / 6509卷
关键词：
the graph reconstruction conjecture; bipartite permutation graphs;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
The graph reconstruction conjecture is a long-standing open problem in graph theory. The conjecture has been verified for all graphs with at most 11 vertices. Further, the conjecture has been verified for regular graphs, trees, disconnected graphs, unit interval graphs, separable graphs with no pendant vertex, outer-planar graphs, and unicyclic graphs. We extend the list of graph classes for which the conjecture holds. We give a proof that bipartite permutation graphs are reconstructible.
引用
收藏
页码：362 / +
页数：2
相关论文
共 39 条
[21]   Finding Maximum Edge Bicliques in Convex Bipartite Graphs [J].
Doron Nussbaum ;
Shuye Pu ;
Jörg-Rüdiger Sack ;
Takeaki Uno ;
Hamid Zarrabi-Zadeh .
Algorithmica, 2012, 64 :311-325
[22]   Finding Maximum Edge Bicliques in Convex Bipartite Graphs [J].
Nussbaum, Doron ;
Pu, Shuye ;
Sack, Joerg-Ruediger ;
Uno, Takeaki ;
Zarrabi-Zadeh, Hamid .
ALGORITHMICA, 2012, 64 (02) :311-325
[23]   Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms [J].
Abbas, N ;
Stewart, L .
DISCRETE APPLIED MATHEMATICS, 1999, 91 (1-3) :1-23
[24]   NP-completeness results for some problems on subclasses of bipartite and chordal graphs [J].
Asdre, Katerina ;
Nikolopoulos, Stavros D. .
THEORETICAL COMPUTER SCIENCE, 2007, 381 (1-3) :248-259
[25]   On orthogonal ray graphs [J].
Shrestha, Anish Man Singh ;
Tayu, Satoshi ;
Ueno, Shuichi .
DISCRETE APPLIED MATHEMATICS, 2010, 158 (15) :1650-1659
[26]   Reconstruction of interval graphs [J].
Kiyomi, Masashi ;
Saitoh, Toshiki ;
Uehara, Ryuhei .
THEORETICAL COMPUTER SCIENCE, 2010, 411 (43) :3859-3866
[27]   Reconstruction of Interval Graphs [J].
Kiyomi, Masashi ;
Saitoh, Toshiki ;
Uehara, Ryuhei .
COMPUTING AND COMBINATORICS, PROCEEDINGS, 2009, 5609 :106-115
[28]   Biclique graphs of interval bigraphs [J].
Cruz, E. P. ;
Groshaus, M. ;
Guedes, A. L. P. ;
Puppo, J. P. .
DISCRETE APPLIED MATHEMATICS, 2020, 281 :134-143
[29]   UNIVERSAL GRAPHS AND UNIVERSAL PERMUTATIONS [J].
Atminas, Aistis ;
Lozin, Vadim V. ;
Kitaev, Sergey ;
Valyuzhenich, Alexandr .
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2013, 5 (04)
[30]   Partitioning graphs into Hamiltonian ones [J].
Chen, L .
PARALLEL COMPUTING, 1996, 22 (04) :607-618
1234