Extremal total eccentricity of \(k\)-apex trees

1. Introduction

We consider only simple and connected graphs. In a graph \( G \), the eccentricity [1, 2, 3] of a vertex \( v \) is one of the first distance-based, invariants. The \textit{eccentricity} of a vertex \(v\) in a connected graph \(G\) is the distance function as \begin{equation} ecc_{G}(v)= \max\limits_{u \in V(G)} d(u,v) . \end{equation} Total eccentricity of a graph \(G\) is the sum of all vertex eccentricities \begin{equation} Ecc(G)=\sum\limits_{z \in V(G)} ecc_{G}(z). \end{equation}

Fathalikhani et al. [4] computed total eccentricity of some graph operations, and found bound for that of tensor product. Eccentricity, center and radius computations on the cover graphs of distributive lattices were presented by Suzuki and McDermind [5]. Extremal trees, unicyclic, bicyclic graphs and extremal conjugated trees with respect to total eccentricity index were presented by Farooq et al. in [6].

If a graph \(G\) contains a vertex \(x\), such that \(G-x\) is a tree, then it is called apex tree. The vertex \( x \), is called an apex vertex of \(G\). A tree is always an apex tree, therefore a non-trivial apex tree is an apex tree which itself is not a tree. For any natural number \(k\ge1\), a graph \(G\) is called a \(k\)-apex tree if there exists a set \(X\) of \(k\) elements, and subset of \(V(G)\) such that \(G-X\) is a tree, while for any \(Y\subseteq V(G)\) with \(|Y|< k\), \(G-Y\) is not a tree. Any vertex from the set \(X\) is called a \(k\)-apex vertex. \( T_k(n) \) denotes the set of all \( k \)-apex trees of order \( n \), for \(k\ge1\) and \(n\ge3\). Sharp upper bound for the Randic (connectivity) index of \(k\)-apex trees for \(k \ge 2\) were discovered by Akhter et al. [7]. Extremal first reformulated Zagreb index of \(k\)-apex trees was discovered by Akhter et al. in [8]. In this paper we have found minimal total eccentricity of \(k\)-apex trees and corresponding graphs. The join of two vertex-disjoint graphs \(G\) and \(H\) is the graph \(G+H\) with \(V(G+ H) =V(G) \cup V(H)\) and the edges of \(G+H\) are all edges of graphs \(G\) and \(H\) and the edges obtained by joining each vertex of \(G\) with each vertex of \(H\). Let \(G \in T_k(n)\) and \(X\) be the set of \( k \)-apex vertices, by the graph \(X_G\) we mean the subgraph of \(G\) whose vertex set is \(X\). The complete graph with vertex set \(X\) will be denoted by \(KX_G\). The tree obtained from \(G\) by deleting apex vertices will be denoted by \(T_G\). We shall denote the star graph whose vertex set is \(V(G)-X\) by \(S_G\). If \(G \in T_k(n)\), then \(X_G+T_G\) and \(KX_G+S_G\) are also \(k\)-apex trees. A tree of \(n\) vertices will be denoted by \(T_n\). We shall denote the eccentricity of a vertex \(v\) in a graph \(G\) by \(ecc_G(v)\).

2. Minimal total eccentricity of \(k\)-apex trees

The following is a fundamental lemma, and is used to obtain many useful results.

Lemma 1. If \(u,v \in V(G)\) are not adjacent, then \(Ecc(G+uv) \le Ecc(G) .\)

The proof of above lemma is obvious.

Lemma 2. If \(G \in T_k(n)\), \(k \ge 1\) and \(n-k \ge 3\) then \(Ecc(G) \ge Ecc(KX_G+S_G) .\)

Proof. As \(V(G) = V(X_G+T_G) \) and \(G\) is a subgraph of \(X_G+T_G\) so by Lemma 1

As graph \(KX_G+T_G\) is either same as \(X_G+T_G\) or it is obtained by adding edges in \(X_G+T_G\) therefore by Lemma 1 If \(T_G\) is not a star then for every vertex \(v \in V(G)-X\), \(ecc_{KX_G+T_G}(v) \ge 2\) and if \(T_G=S_G\), then \(ecc_{KX_G+S_G}(v) \le 2\), therefore Combining inequalities (1), (2) and (3) we have the result. $$Ecc(G) \ge Ecc(KX_G+S_G) .$$

The following lemma gives a relation between eccentricities of join of graphs and eccentricities of graphs.

Lemma 3. If \(K_n\) and \(S_m\) are vertex disjoint graphs for \(n \ge 2\) and \(m \ge 2\), then \( Ecc(K_n+S_m)=Ecc(K_n)+Ecc(S_m) .\)

Proof. For any vertex \(v \in V(K_n)\), we have \( ecc_{K_n+S_m}(v)=ecc_{K_n}(v)=1\) and for any vertex \(u \in V(S_m)\), we have \( ecc_{K_n+S_m}(u)= ecc(S_m).\) Thus $$ Ecc(K_n+S_m)= \sum\limits_{v \in V(K_n+S_m)} ecc_{K_n+S_m}(v) .$$ As graphs \(K_n\) and \(S_m\) are vertex disjoint, therefore $$ Ecc(K_n+S_m)= \sum\limits_{v \in V(K_n)} ecc_{K_n+S_m}(v) + \sum\limits_{v \in V(S_m} ecc_{K_n+S_m} (v). $$ Since for any vertex \(v \in K_n\), \(ecc_{K_n+Sm}(v)=ecc_{K_n}(v)\) and for any vertex \(u \in (S_m)\), \(ecc_{K_n+S_m}(u)=ecc_{S_m}(u)\) therefore $$ Ecc(K_n+S_m)= \sum\limits_{v \in V(K_n)} ecc_{K_n}(v) + \sum\limits_{v \in V(S_m)} ecc_{S_m} (v) $$ and hence $$ Ecc(K_n+S_m) = Ecc(K_n) + Ecc(S_m) .$$

Theorem 1. If \(G \in T_k(n) \), \(k \ge 1\) and \(n-k \ge 3\), then $$Ecc(G) \ge 2n-k-1$$ and equality holds if there are \(k+1\) vertices of eccentricity \(1\) and all other vertices are of eccentricity \(2\).

Proof. For any graph \(G \in T_k(n)\) and for given conditions on \(k\) and \(n\), by Lemma 2, we have $$Ecc(G) \ge Ecc(KX_G+S_G).$$ As for each \(v \in X\), \(ecc_{KX_G+S_G} (v) = 1\), for one vertex in \(V(G)-X\), eccentricity is one and for all other \(n-k-1\) vertices in \(V(G)-X\), eccentricity is \(2\), therefore $$Ecc(G) \ge 2n-k-1 .$$

Theorem 2. If \(G \in T_k(n) \), \(k \ge 1\) and \(n-k = 2\), then $$Ecc(G) \ge n$$ and equality holds if all vertices are of eccentricity \(1\).

Proof. By Lemma 2, for any \(k\)-apex tree \(G\), we have \(Ecc(G) \ge Ecc(KX_G+S_G)\). In this case star will be of order \(2\) and therefore for every vertex \(v \in KX_G+S_G\), \(ecc(v)=1\) and hence $$Ecc(G) \ge n .$$

Author Contributions

All authors contributed equally to the writing of this paper. All authors read and approved the final manuscript.

Conflicts of Interest:

The authors declare no conflict of interest.