Embeddings into almost self-centered graphs of given radius

作者：Xu, Kexiang^*; Liu, Haiqiong; Das, Kinkar Ch; Klavzar, Sandi

来源：Journal of Combinatorial Optimization, 2018, 36(4): 1388-1410.

DOI：10.1007/s10878-018-0311-9

• Eccentricity
• Diameter
• Almost self-centered graph
• Graph of diameter 2
• ASC index

A graph is almost self-centered (ASC) if all but two of its vertices are central. An almost self-centered graph with radius r is called an r-ASC graph. The r-ASC index of a graph G is the minimum number of vertices needed to be added to G such that an r-ASC graph is obtained that contains G as an induced subgraph. It is proved that holds for any graph G and any which improves the earlier known bound . It is further proved that holds if and G is of order at least 2. The 3-ASC index of complete graphs is determined. It is proved that if G has diameter 2 and for several classes of graphs of diameter 2 the exact value of the 3-ASC index is obtained. For instance, if a graph G of diameter 2 does not contain a diametrical triple, then . The 3-ASC index of paths of order , cycles of order , and trees of order and diameter are also determined, respectively, and several open problems proposed.

• 出版日期2018-11
• 单位南京航空航天大学