| Home |
| Last parution |
| Authors |
| Topics |
| Keywords |
| Parutions |
| Videos |
| Search |
| Reading committee |
| Contact |
| Subscription |
| Article submission |
French version |
The issues from 1 to 148 are also available on line at NUMDAM and at Revues.org for the following issues |
- Results for criterions:
- Keyword: Tree encoding
1 match
| Title | Arch graphs |
| Author | LECLERC Bruno |
| Keywords | 2-tree, Algorithm, Cycle, Distance, Graph, Tree, Tree encoding |
| Topics | Algorithms - Algorithmic Theory, Distances, Graphs, Trees |
| Abstract | 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. |
| Number | 157, Spring 2002 |
| Language | French |
The entire journal is licensed under a Creative Commons license