Graphes d'arches

Mathématiques et sciences humaines. Mathematics and social sciences

Leclerc, Bruno¹ 

关键词: graph;    algorithm;    tree;    2-tree;    tree encoding;    distance;    cycle;   

DOI  :  10.4000/msh.2858

学科分类：数学（综合）

来源: College de France * Ecole des Hautes Etudes en Sciences Sociales (E H E S S)

【 摘 要 】

An arch-graph may be obtained from a simple edge by successive addings of 3-paths, grafted on their extremities. Equivalently, it admits no subgraph of which every vertex has degree at least three, and is maximal with this property, for a fixed number of vertices. It is known that a tree distance may be summarized by 2n-3 of its entries, conveniently chosen. Arch graphs with n vertices correspond to such sets of entries. They include the graphs of the so-called 2-tree type. We study these graphs, and the k-arch graphs and k-trees which naturally generalize them. It is recalled how a tree metric or function is associated to a valued arch graph, and the properties of this correspondence are investigated.

【 授权许可】

Unknown