کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420619 | 683961 | 2008 | 11 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Geodeticity of the contour of chordal graphs Geodeticity of the contour of chordal graphs](/preview/png/420619.png)
A vertex vv is a boundary vertex of a connected graph G if there exists a vertex u such that no neighbor of vv is further away from u than vv. Moreover, if no vertex in the whole graph V(G)V(G) is further away from u than vv, then vv is called an eccentric vertex of G . A vertex vv belongs to the contour of G if no neighbor of vv has an eccentricity greater than the eccentricity of vv. Furthermore, if no vertex in the whole graph V(G)V(G) has an eccentricity greater than the eccentricity of vv, then vv is called a peripheral vertex of G. This paper is devoted to study these kinds of vertices for the family of chordal graphs. Our main contributions are, firstly, obtaining a realization theorem involving the cardinalities of the periphery, the contour, the eccentric subgraph and the boundary, and secondly, proving both that the contour of every chordal graph is geodetic and that this statement is not true for every perfect graph.
Journal: Discrete Applied Mathematics - Volume 156, Issue 7, 1 April 2008, Pages 1132–1142