Diameter-essential edges in a graph |
| |
Affiliation: | 1. Department of Mathematics, K.R.C.P.G. Centre, Belgaum 590001, India;2. Department of Mathematics, Baruch College (CUNY), 17 Lexington Ave., New York, NY 10010, USA |
| |
Abstract: | ![]() The eccentricity e(v) of v is the distance to a farthest vertex from v. The diameter diam(G) is the maximum eccentricity among the vertices of G. The contraction of edge e=uv in G consists of removing e and identifying u and v as a single new vertex w, where w is adjacent to any vertex that at least one of u or v were adjacent to. The graph resulting from contracting edge e is denoted G/e. An edge e is diameter-essential if diam(G/e)G). Let c(G) denote the number of diameter-essential edges in graph G. In this paper, we study existence and extremal problems for c(G); determine bounds on c(G) in terms of diameter and order; and obtain characterizations of graphs achieving extreme values of c(G). |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|