# Chain hexagonal cacti with the extremal eccentric distance sum.

1. IntroductionTopological index, which can be used to characterize some property of the molecule graph, is a numeric and invariant quantity of a structure graph under graph isomorphism. Recently a novel graph invariant for predicting biological and physical properties--eccentric distance sum--was introduced by Gupta eta al. [1]. It has a vast potential in structure activity/property relationships. The authors [1] have shown that some structure activity and quantitative structure-property studies using eccentric distance sum were better than the corresponding values obtained using the Wiener index.

Throughout this paper we only consider simple connected graphs. Let G be a simple connected graph with the vertex set V(G). For vertices u, v [member of] V(G), the distance d(u, v) is defined as the length of the shortest path between u and v in G; [D.sub.G](v) (or D(v) for short) denotes the sum of distances from v. The eccentricity [[epsilon].sub.G](v) (or [epsilon](v) for short) of a vertex v is the maximum distance from v to any other vertex in G. The eccentric distance sum (EDS) of G is defined as

[[xi].sup.d] (G) = [summation over (v[member of]V)(G)] [[epsilon].sub.G](v)[D.sub.G](v) (1)

In [2] authors investigated the eccentric distance sum of unicyclic graphs with given girth and characterize the extremal graphs with the minimal and the second minimal EDS; they also characterize the trees with the minimal EDS among the n-vertex trees of a given diameter. Ilic et al. [3] studied the various lower and upper bounds for the EDS in terms of other graph invariants including the Wiener index, the degree distance, the eccentric connectivity index, independence number, connectivity, matching number, chromatic number, and clique number. Zhang and Li [4] considered the maximal eccentric distance sum of graphs and determined the n-vertex trees with the first four maximal EDS. Also they characterized the n-vertex unicyclic graphs with the first three maximal EDS. Li et al. [5] investigated the trees with the minimal and second minimal EDS among nvertex trees with given matching number; as a continuance they also determine the trees with the third and fourth minimal EDS among the n-vertex trees and characterized the trees with the second EDS among the n-vertex trees of a given diameter. For other recent results on EDS, the readers are referred to [6,7].

A cactus graph is a connected graph in which no edges lie in more than one cycle. Consequently, each block of a cactus graph is either an edge or a cycle. If all blocks of a cactus G are cycles of the same length m, the cactus is m-uniform. A hexagonal cactus is a 6-uniform cactus, that is, a cactus in which every block is a hexagon. A vertex shared by two or more hexagons is called a cut vertex. If each hexagon of a hexagonal cactus G has at most two cut vertices and each cut vertex is shared by exactly two hexagons, we call G as a chain hexagonal cactus. The number of hexagons in G is called the length of the chain. Evidently, there exit exactly two hexagons which share only one cut vertex in any chain hexagonal cactus of length greater than one. Such hexagons are called terminal hexagons, and other remaining hexagons are called internal hexagons. Let [C.sub.n] be the set of all chain hexagonal cacti of length n.

Let u and v be two vertices in [C.sub.6]. They are said to be in orthoposition if they are adjacent in [C.sub.6]. If the distance between u and v is two, they are in metaposition. They are in paraposition if the distance between them is three. An internal hexagon in a chain hexagonal cactus is called orthohexagon, matahexagon, or parahexagon if its cut vertices are in ortho, meta-, or paraposition, respectively. A chain hexagonal cactus of length n is called an orthochain if all its internal hexagons are orthohexagons, denoted by [O.sub.n]. The metachain and parachain of length n are defined in a completely analogous manner, denoted by [M.sub.n], [L.sub.n], respectively.

Recently, Doslic and Maloy [8] considered the chain hexagonal cacti and derived explicit recurrences for their matching and independence polynomials and explicit recurrences for the number of matchings and independence set of certain types. The present paper was motivated by [8]; we investigate the eccentric distance sum of chain hexagonal cactus of length n and characterize the chain hexagonal cacti with the minimal and the maximal eccentric distance sums among all chain hexagonal cacti of length n(>2), respectively.

2. The Minimal and the Maximal EDS of Chain Hexagonal Cacti

In this section we determine the chain hexagonal cacti with the maximum and minimum EDS. In addition, we give exact formulas for EDS of two types of hexagonal cacti.

Lemma 1. Let [L.sub.i] be a parachain of lengths [n.sub.0] ([n.sub.0] [greater than or equal to] 1) and [u.sub.0] [member of] V([L.sub.i]) (see Figure 1). Let [G.sub.0] be a chain hexagonal cactus of length n - [n.sub.0] and [v.sub.j] [member of] V([G.sub.0]) (j = 0,1,2,3,4, 5) (see Figure 1). Let [G.sub.1] be the chain hexagonal cactus of length n obtained from [L.sub.i] and [G.sub.0] by identifying [u.sub.0] with [v.sub.1]. Let [G.sub.2] be the graph obtained from [L.sub.i] and [G.sub.0] by identifying [u.sub.0] with [v.sub.3]. Let [G.sub.3] be the graph obtained from [L.sub.i] and [G.sub.0] by identifying [u.sub.0]s with [v.sub.5]. If [n.sub.0] [less than or equal to] [(n - 1)/2], then

[[xi].sup.d] ([G.sub.1])< [[xi].sup.d] ([G.sub.2]) < [[xi].sup.d] ([G.sub.3]). (2)

Proof. Let [H.sub.0] be the hexagon consisting of vertices [v.sub.i] (i = 0,1, ... , 5)in [G.sub.0] (see Figure 1). By the definition of eccentric distance sum, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

Let [A.sub.i], [B.sub.i], and [C.sub.i] (i = 1,2,3) denote the three terms of right equality above, respectively. We only need to prove the following three inequalities: [A.sub.3] > [A.sub.2] > [A.sub.1], [B.sub.2] + [C.sub.2] > [B.sub.1] + [C.sub.1], and [B.sub.3] + [C.sub.3] > [B.sub.2] + [C.sub.2].

For any v [member of] V([L.sub.i] - [u.sub.0]), we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

which yield that [A.sub.1] < [A.sub.2] < [A.sub.3].

For any v [member of] V([G.sub.0]), it is evident that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Moreover,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

Note that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For the part [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we divide into two cases to deal with it.

Case 1 (v [member of] V([G.sub.0] - [H.sub.0])). Consider the following:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

Case 2 (v [member of] V([H.sub.0]) = {[v.sub.0], [v.sub.3], [v.sub.2], [v.sub.3], [v.sub.4], [v.sub.5]}). Consider the following:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

Therefore we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (8)

Similarly, we have [C.sub.3] - [C.sub.2] [greater than or equal to] 25n(n - [n.sub.0] - 1)(n - [n.sub.0] + 2).

For [v.sub.i] [member of] V([H.sub.0]) (i = 0,1,2,3,4, 5), it follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)

So we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

Similarly, we can get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

So we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (12)

We complete the proof.

By Lemma 1, we can get the following result.

Theorem 2. Let [G.sub.n] be a chain hexagonal cactus of length n. Then

[[xi].sup.d] ([O.sub.n]) [less than or equal to] [[xi].sup.d] ([G.sub.n]) [less than or equal to] [[xi].sup.d]([L.sub.n]). (13)

In the following, we will calculate the values of [[xi].sup.d]([O.sub.n]) and [[xi].sup.d]([L.sub.n]).

Theorem 3. Consider

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (14)

For some v [member of] V([H.sub.k]), assume that d(v, [v.sub.k]) = y and d(v, [v.sub.k+1]) = z. Then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (15)

For some hexagon [H.sub.i] (i [less than or equal to] n) (see Figure 2) in [L.sub.n], the eccentricity of every vertex on [H.sub.i] can be derived as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (16)

When n is even, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (17)

When n is odd, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (18)

Let [H.sub.k] be a hexagon in [O.sub.n]. For some v [member of] V([H.sub.k]), assume that d(v, [v.sub.k]) = y and d(v, [v.sub.k+1]) = z. Similar to the case in [L.sub.n], we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (19)

For some hexagon [H.sub.i] (i < (n + 1)/2) (see Figure 3), the eccentricities of every vertex on [H.sub.i] can be derived as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (20)

When n is even, then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (21)

When n is odd, then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (22)

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

http://dx.doi.org/10.1155/2014/897918

Acknowledgments

This research was supported by Natural Science Foundation of China (nos. 11101245, 11301302), Natural Science Foundation of Shandong (no. ZR2011AQ005, no. BS2013SF009), China Postdoctoral Science Foundation funded project (no. 2013M530869), Foundation of Shandong Institute of Business and Technology (no. 2013QN056).

References

[1] S. Gupta, M. Singh, and A. K. Madan, "Eccentric distance sum: a novel graph invariant for predicting biological and physical properties," Journal of Mathematical Analysis and Applications, vol. 275, no. 1, pp. 386-401, 2002.

[2] G. Yu, L. Feng, and A. Ilic, "On the eccentric distance sum of trees and unicyclic graphs," Journal of Mathematical Analysis and Applications, vol. 375, no. 1, pp. 99-107, 2011.

[3] A. Ilic, G. Yu, and L. Feng, "On the eccentric distance sum of graphs," Journal of Mathematical Analysis and Applications, vol. 381, no. 2, pp. 590-600, 2011.

[4] J. Zhang and J. Li, "On the maximal eccentric distance sum of graphs," ISRN Applied Mathematics, vol. 2011, Article ID 421456, 9 pages, 2011.

[5] S. Li, M. Zhang, G. Yu, and L. Feng, "On the extremal values of the eccentric distance sum of trees," Journal of Mathematical Analysis and Applications, vol. 390, no. 1, pp. 99-112, 2012.

[6] H. Hua, S. Zhang, and K. Xu, "Further results on the eccentric distance sum," Discrete Applied Mathematics, vol. 160, no. 1-2, pp. 170-180, 2012.

[7] H. Hua, K. Xu, and S. Wen, "A short and unified proof of Yu et al.'s two results on the eccentric distance sum," Journal of Mathematical Analysis and Applications, vol. 382, no. 1, pp. 364-366, 2011.

[8] T. Doslic and F. Maloy, "Chain hexagonal cacti: matchings and independent sets," Discrete Mathematics, vol. 310, no. 12, pp. 1676-1690, 2010.

Hui Qu and Guihai Yu

School of Mathematics, Shandong Institute of Business and Technology, 191 Binhaizhong Road, Yantai, Shandong 264005, China

Correspondence should be addressed to Guihai Yu; yuguihai@126.com

Received 11 November 2013; Accepted 4 February 2014; Published 10 March 2014

Academic Editors: A. Previtali and A. Woldar

Printer friendly Cite/link Email Feedback | |

Title Annotation: | Research Article |
---|---|

Author: | Qu, Hui; Yu, Guihai |

Publication: | The Scientific World Journal |

Article Type: | Report |

Date: | Jan 1, 2014 |

Words: | 2008 |

Previous Article: | Overexpression of MMP13 is associated with clinical outcomes and poor prognosis in oral squamous cell carcinoma. |

Next Article: | Color temperature tunable white-light LED cluster with extrahigh color rendering index. |

Topics: |