On the Number of Realizations of Certain Henneberg Graphs arising in Protein Conformation

Abstract : Several application fields require finding Euclidean coordinates consistent with a set of distances. More precisely, given a simple undirected edge-weighted graph, we wish to find a realization in a Euclidean space so that adjacent vertices are placed at a distance which is equal to the corresponding edge weight. Realizations of a graph can be either flexible or rigid. In certain cases, rigidity can be seen as a property of the graph rather than the realization. In the last decade, several advances have been made in graph rigidity, but most of these, for applicative reasons, focus on graphs having a unique realization. In this paper we consider a particular type of Henneberg graphs that model protein backbones and show that almost all of them give rise to sets of incongruent realizations whose cardinality is a power of two.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2014, 165, pp.213-232. 〈http://www.sciencedirect.com/science/article/pii/S0166218X13000449〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01093060
Contributeur : Antonio Mucherino <>
Soumis le : mercredi 10 décembre 2014 - 09:47:06
Dernière modification le : jeudi 12 avril 2018 - 01:49:26

Identifiants

  • HAL Id : hal-01093060, version 1

Citation

Leo Liberti, Benoît Masson, Jon Lee, Carlile Lavor, Antonio Mucherino. On the Number of Realizations of Certain Henneberg Graphs arising in Protein Conformation. Discrete Applied Mathematics, Elsevier, 2014, 165, pp.213-232. 〈http://www.sciencedirect.com/science/article/pii/S0166218X13000449〉. 〈hal-01093060〉

Partager

Métriques

Consultations de la notice

574