首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号