Conjectura de reconstrução e 2 árvores parciais

24

A conjectura de reconstrução diz que os gráficos (com pelo menos três vértices) são determinados exclusivamente por seus subgrafos deletados. Essa conjectura tem cinco décadas.

Pesquisando literatura relevante, descobri que as seguintes classes de gráficos são conhecidas por serem reconstrutíveis:

  • árvores
  • gráficos desconectados, gráficos cujo complemento está desconectado
  • gráficos regulares
  • Gráficos Outplanplanares máximos
  • gráficos planares máximos
  • gráficos externos
  • Blocos críticos
  • Gráficos separáveis ​​sem vértices finais
  • gráficos unicíclicos (gráficos com um ciclo)
  • gráficos cartesianos não triviais de produtos
  • quadrados de árvores
  • gráficos bidirecionais
  • gráficos de intervalo de unidades
  • gráficos de limiar
  • gráficos quase acíclicos (ou seja, Gv é acíclico)
  • gráficos de cactos
  • gráficos para os quais um dos gráficos excluídos do vértice é uma floresta.

Recentemente, provei que um caso especial de 2 árvores parciais é reconstrutível. Gostaria de saber se 2-árvores parciais (também conhecidas como gráficos paralelos em série ) são conhecidas por serem reconstrutíveis. As 2 árvores parciais não parecem se encaixar em nenhuma das categorias mencionadas acima.

  • Estou perdendo outras classes conhecidas de gráficos reconstrutíveis na lista acima?
  • Em particular, as 2 árvores parciais são conhecidas por serem reconstrutíveis?
Shiva Kintali
fonte
2
Não tenho acesso a ele, mas este documento: springerlink.com/content/p6r03877310411wr afirma que conjuntos ordenados sem N são reconstrutíveis.
Mhum
2
Para aprofundar o comentário de @ mhum: ordens parciais em série são exatamente aquelas que são livres de N, de modo que o artigo afirma que os posets em série são reconstrutíveis. As reduções transitivas dos posets paralelos em série são os gráficos paralelos em série, mas não tenho certeza de como a conjectura da reconstrução interage com as arestas transitivas.
András Salamon
Para sua lista: Kiyomi, Saitoh e Uehara mostraram que os gráficos de permutação bipartidos são reconstrutíveis .
usar o seguinte código
Mais um para sua lista: alguns gráficos planares são reconstrutíveis .
virgi
2
Shiva, você obteve algum resultado novo?
Saeed

Respostas:

4

Eu acredito que não foi demonstrado que os gráficos bidegreed são reconstrutíveis. Os gráficos bidegreed são reconstrutíveis pela borda. Kocay fez um trabalho de reconstrução de gráficos bidirecionais, mas não alcançou um resultado abrangente que consegui encontrar. A noção de que foi provado que os gráficos bidirecionais são reconstrutíveis parece ser um pouco de desinformação circulando na web.

MattM
fonte