Boundary vertices in graphs
Boundary vertices in graphs
复制标题
图中的边界顶点
DOI：
10.1016/s0012-365x(02)00567-8
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Ping Zhang
中科院分区：
文献类型：
--
作者：
G. Chartrand;D. Erwin;Garry L. Johns;Ping Zhang
非平凡连通图 G 中两个顶点 u 和 v 之间的距离 d(u,v) 是 G 中最短 u-v 路径的长度。对于 G 的顶点 v，偏心率 e(v) 是 v 和距 v 最远的顶点之间的距离。如果 e(v) 是 G 的直径，则 G 的顶点 v 是外围顶点。由其外围顶点导出的 G 的子图是外围 Per(G) G. 如果 d(u,v)=e(v)，G 的顶点 u 是顶点 v 的偏心顶点。如果 x 是 G 的某个顶点的偏心顶点，则顶点 x 是 G 的偏心顶点。由其偏心顶点导出的 G 的子图是 G 的偏心子图 Ecc(G)。如果对于所有 w∈N(u) d(w,v)⩽d(u,v)，G 的顶点 u 是顶点 v 的边界顶点。如果u是G的某个顶点的边界顶点，则顶点u是G的边界顶点。由其边界顶点导出的G的子图是G的边界∂(G)。对于某个图G，如果H=∂(G)，则图H是边界图。我们研究连通图的外围、偏心子图和边界之间的关系，并建立所有边界图的表征。结果表明，对于具有 2⩽a⩽b⩽c 的整数的每个三元组 a,b,c，存在一个连通图 G，使得 Per(G) 具有 a 阶，Ecc(G) 具有 b 阶，并且 ∂(G) 具有 c 阶。此外，对于每个 0<r⩽s⩽t⩽1 的有理数三元组 r,s,t，存在一个 n 阶连通图 G，使得 |V(Per(G))|/n=r，|V(Ecc(G))|/n=s，且 |V(∂(G))|/n=t。
The distance d(u,v) between two vertices u and v in a nontrivial connected graph G is the length of a shortest u–v path in G. For a vertex v of G, the eccentricity e(v) is the distance between v and a vertex farthest from v. A vertex v of G is a peripheral vertex if e(v) is the diameter of G. The subgraph of G induced by its peripheral vertices is the periphery Per(G) of G. A vertex u of G is an eccentric vertex of a vertex v if d(u,v)=e(v). A vertex x is an eccentric vertex of G if x is an eccentric vertex of some vertex of G. The subgraph of G induced by its eccentric vertices is the eccentric subgraph Ecc(G) of G. A vertex u of G is a boundary vertex of a vertex v if d(w,v)⩽d(u,v) for all w∈N(u). A vertex u is a boundary vertex of G if u is a boundary vertex of some vertex of G. The subgraph of G induced by its boundary vertices is the boundary ∂(G) of G. A graph H is a boundary graph if H=∂(G) for some graph G. We study the relationship among the periphery, eccentric subgraph, and boundary of a connected graph and establish a characterization of all boundary graphs. It is shown that for each triple a,b,c of integers with 2⩽a⩽b⩽c, there is a connected graph G such that Per(G) has order a, Ecc(G) has order b, and ∂(G) has order c. Moreover, for each triple r,s,t of rational numbers with 0<r⩽s⩽t⩽1, there is a connected graph G of order n such that |V(Per(G))|/n=r, |V(Ecc(G))|/n=s, and |V(∂(G))|/n=t.