Accretion centers: A generalization of branch weight centroids

An ordered n-tuple (v_i1,v_i2,…,v_in) is called a sequential labelling of graph G if {v_i1,v_i2,…,v_in} = V(G) and the subgraph induced by {v_i1,v_i2,…, v_ij} is connected for 1≤j≤n. Let σ(v;G) denote the number of sequential labellings of G with v_i1=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.