|
Wiener Polarity Index of Cycle-Block GraphsDOI: 10.1155/2014/476705 Abstract: The Wiener polarity index of a graph is the number of unordered pairs of vertices of such that the distance between and is 3. Cycle-block graph is a connected graph in which every block is a cycle. In this paper, we determine the maximum and minimum Wiener polarity index of cycle-block graphs and describe their extremal graphs; the extremal graphs of 4-uniform cactus with respect to Wiener polarity index are also discussed. 1. Introduction Let be a connected simple graph. The distance between the vertices and of is defined as the length of a shortest path connecting and . is called the th neighbor set of . is called the degree of . If , then is called a pendant vertex of . denotes a cycle of order . The girth of , denoted by , is the length of the shortest cycle of . A block of the graph is a maximal 2-connected subgraph of . A cactus graph is a connected graph in which no edge lies in more than one cycle, such that each block of a cactus graph is either an edge or a cycle. If all blocks of a cactus are cycles, the graph is defined as cycle-block graph. In this paper, suppose the cycle-block graph consist of cycles, the length of the cycles may be different. If all blocks of a cactus are cycles of the same length , the cactus is -uniform. A hexagonal cactus is a -uniform cactus that every block of the graph is a hexagon. A vertex shared by two or more hexagons is called a cut-vertex. If each hexagon of a hexagonal cactus has at most two cut-vertices and each cut-vertex is shared by exactly two hexagons, we say that is a chain hexagonal cactus (see Figure 1(a)). A star cactus is a cactus consisting of cycles, spliced together in a single vertex (see Figure 1(b)). A star hexagonal cactus is a star cactus in which every cycle is a hexagon. Figure 1: A chain hexagonal cactus (a) and a star cactus graph (b). The Wiener polarity index of , denoted by , is the number of unordered vertex pairs of distance 3. It was first used in a linear formula to calculate the boiling points of paraffin [1]: where are constants for a given isomeric group. The Wiener polarity index became popular recently, and many mathematical properties and its chemical applications were discovered [2–6]. In this line, Du et al. [2] characterized the minimum and maximum Wiener polarity index among all trees of order , and Deng [3] determined the largest Wiener polarity indices among all chemical trees of order . M. H. Liu and B. L. Liu [4] determined the first two smallest Wiener polarity indices among all unicyclic graphs of order . Hou et al. [5] determined the maximum Wiener polarity
|