ALMOST-PERIPHERAL GRAPHS

作者：Klavzar Sandi^*; Narayankar Kishori P; Walikar H B; Lokesh S B

来源：Taiwanese Journal of Mathematics, 2014, 18(2): 463-471.

DOI：10.11650/tjm.18.2014.3267

The center C(G) and the periphery P(G) of a connected graph G consist of the vertices of minimum and maximum eccentricity, respectively. Almost-peripheral (AP) graphs are introduced as graphs G with vertical bar P(G)vertical bar = vertical bar V(G)vertical bar-1 (and vertical bar C(G)vertical bar = 1). AP graph of radius r is called an r-AP graph. Several constructions of AP graph are given, in particular implying that for any r %26gt;= 1, any graph can be embedded as an induced subgraph into some r-AP graph. A decomposition of AP-graphs that contain cut-vertices is presented. The r-embedding index Phi(r) (G) of a graph G is introduced as the minimum number of vertices which have to be added to G such that the obtained graph is an r-AP graph. It is proved that Phi(2)(G) %26lt;= 5 holds for any non-trivial graphs and that equality holds if and only if G is a complete graph.

• 出版日期2014-4