Improving the Bounds for the Annular and Marginal Appendage Numbers

摘要

For a connected graph G, the distance d(u, v) between two vertices u and v is the length of a shortest u-v path in G. The eccentricity e(v) of a vertex v is the distance between v and a vertex furthest from v, while the distance d(v) of v is the sum of the distances between v and all vertices of G. The annulus of G is the subgraph induced by those vertices whose eccentricities are strictly between the minimum and maximum eccentricities of the vertices of G and the margin of G is the subgraph induced by the vertices having the maximum distance. For any graph G that is isomorphic to the annulus of some connected graph H, the annular appendage number is the minimum difference between the order of H and the order of G. Similarly, the marginal appendage number is the minimum difference between the order of H and the order of G where G is isomorphic to the margin of the connected graph H. Upper bounds have been found for these appendage numbers, and in this paper, a characterization for the annular appendage number is given and the bound for the marginal appendage number is shown to be exact for an infinite class of graphs.