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
相关论文
共 50 条
  • [1] BIPARTITE PERMUTATION GRAPHS ARE RECONSTRUCTIBLE
    Kiyomi, Masashi
    Saitoh, Toshiki
    Uehara, Ryuhei
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2012, 4 (03)
  • [2] BIPARTITE PERMUTATION GRAPHS
    SPINRAD, J
    BRANDSTADT, A
    STEWART, L
    DISCRETE APPLIED MATHEMATICS, 1987, 18 (03) : 279 - 292
  • [3] Bandwidth of Bipartite Permutation Graphs
    Uehara, Ryuhei
    ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2008, 5369 : 824 - 835
  • [4] On opposition graphs, coalition graphs, and bipartite permutation graphs
    Le, Van Bang
    DISCRETE APPLIED MATHEMATICS, 2014, 168 : 26 - 33
  • [5] Vertex deletion into bipartite permutation graphs
    Bożyk, Lukasz
    Derbisz, Jan
    Krawczyk, Tomasz
    Novotná, Jana
    Okrasa, Karolina
    Leibniz International Proceedings in Informatics, LIPIcs, 2020, 180
  • [6] Critical properties of bipartite permutation graphs
    Alecu, Bogdan
    Lozin, Vadim
    Malyshev, Dmitriy
    JOURNAL OF GRAPH THEORY, 2024, 105 (01) : 34 - 60
  • [7] Acyclic domination on bipartite permutation graphs
    Xu, Guangjun
    Kang, Liying
    Shan, Erfang
    INFORMATION PROCESSING LETTERS, 2006, 99 (04) : 139 - 144
  • [8] Sliding Token on Bipartite Permutation Graphs
    Fox-Epstein, Eli
    Hoang, Duc A.
    Otachi, Yota
    Uehara, Ryuhei
    ALGORITHMS AND COMPUTATION, ISAAC 2015, 2015, 9472 : 237 - 247
  • [9] Vertex Deletion into Bipartite Permutation Graphs
    Łukasz Bożyk
    Jan Derbisz
    Tomasz Krawczyk
    Jana Novotná
    Karolina Okrasa
    Algorithmica, 2022, 84 : 2271 - 2291
  • [10] Vertex Deletion into Bipartite Permutation Graphs
    Bozyk, Lukasz
    Derbisz, Jan
    Krawczyk, Tomasz
    Novotna, Jana
    Okrasa, Karolina
    ALGORITHMICA, 2022, 84 (08) : 2271 - 2291
12345