Graphes d'arches
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 ma...
Αποθηκεύτηκε σε:
| Τόπος έκδοσης: | URI:https://journals.openedition.org/msh, |
|---|---|
| Κύριος συγγραφέας: | |
| Μορφή: | Article ou chapitre numérique |
| Γλώσσα: | Français |
| Έκδοση: |
Mathématiques et sciences humaines
2006
|
| Θέματα: | |
| Διαθέσιμο Online: | Accès Université d'Orléans et IFPM Accès Université d'Orléans et IFPM |
| Περίληψη: | 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. |
|---|