Name
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)\) 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\) holds for any graph G and any \(r\ge 2\) which improves the earlier known bound \(\theta _r(G)\le 2r+1\). It is further proved that \(\theta _r(G)\le 2r-1\) holds if \(r\ge 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\}\) 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\). The 3-ASC index of paths of order \(n\ge 1\), cycles of order \(n\ge 3\), and trees of order \(n\ge 10\) and diameter \(n-2\) are also determined, respectively, and several open problems proposed. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/s10878-018-0311-9 | J. Comb. Optim. |
Keywords | Field | DocType |
Eccentricity, Diameter, Almost self-centered graph, Graph of diameter 2, ASC index, 05C12, 05C05, 05C75 | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Induced subgraph,Mathematics | Journal |
Volume | Issue | ISSN |
36 | 4 | 1382-6905 |
Citations | PageRank | References |
0 | 0.34 | 14 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kexiang Xu | 1 | 72 | 11.43 |
| Haiqiong Liu | 2 | 0 | 0.34 |
| Kinkar Ch. Das | 3 | 208 | 30.32 |
| sandi klavžar | 4 | 542 | 58.66 |