Accretion centers: A generalization of branch weight centroids |
| |
Authors: | Peter J. Slater |
| |
Affiliation: | Sandia National Laboratories (A U.S. Dept. of Energy Facility), Albuquerque, NM 87135, USA |
| |
Abstract: | An ordered n-tuple (vi1,vi2,…,vin) is called a sequential labelling of graph G if {vi1,vi2,…,vin} = V(G) and the subgraph induced by {vi1,vi2,…, vij} is connected for 1≤j≤n. Let σ(v;G) denote the number of sequential labellings of G with vi1=v. Vertex v is defined to be an accretion center of G if σ is maximized at v. This is shown to generalize the concept of a branch weight centroid of a tree since a vertex in a tree is an accretion center if and only if it is a centroid vertex. It is not, however, a generalization of the concept of a median since for a general graph an accretion center is not necessarily a vertex of minimum distance. A method for computing σ(v;G) based upon edge contractions is described. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|