Embeddings into almost self-centered graphs of given radius

Kexiang Xu (), Haiqiong Liu (), Kinkar Ch. Das () and Sandi Klavžar ()
Additional contact information
Kexiang Xu: Nanjing University of Aeronautics and Astronautics
Haiqiong Liu: Nanjing University of Aeronautics and Astronautics
Kinkar Ch. Das: Sungkyunkwan University
Sandi Klavžar: University of Ljubljana

Journal of Combinatorial Optimization, 2018, vol. 36, issue 4, No 15, 1388-1410

Abstract: Abstract 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 $$\theta _r(G)$$ θ r ( G ) 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 $$\theta _r(G)\le 2r$$ θ r ( G ) ≤ 2 r holds for any graph G and any $$r\ge 2$$ r ≥ 2 which improves the earlier known bound $$\theta _r(G)\le 2r+1$$ θ r ( G ) ≤ 2 r + 1 . It is further proved that $$\theta _r(G)\le 2r-1$$ θ r ( G ) ≤ 2 r - 1 holds if $$r\ge 3$$ r ≥ 3 and G is of order at least 2. The 3-ASC index of complete graphs is determined. It is proved that $$\theta _3(G)\in \{3,4\}$$ θ 3 ( G ) ∈ { 3 , 4 } 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 $$\theta _3(G) = 4$$ θ 3 ( G ) = 4 . The 3-ASC index of paths of order $$n\ge 1$$ n ≥ 1 , cycles of order $$n\ge 3$$ n ≥ 3 , and trees of order $$n\ge 10$$ n ≥ 10 and diameter $$n-2$$ n - 2 are also determined, respectively, and several open problems proposed.

Keywords: Eccentricity; Diameter; Almost self-centered graph; Graph of diameter 2; ASC index; 05C12; 05C05; 05C75 (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0311-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:36:y:2018:i:4:d:10.1007_s10878-018-0311-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-0311-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().