The PI Index of Polyomino Chains of 4 k -Cycles
- PDF / 347,723 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 10 Downloads / 159 Views
The PI Index of Polyomino Chains of 4k-Cycles Toufik Mansour · Matthias Schork
Received: 10 August 2008 / Accepted: 9 October 2008 / Published online: 16 October 2008 © Springer Science+Business Media B.V. 2008
Abstract The Padmakar-Ivan (PI) index of a graph G is the sum over all edges uv of G of the number of edges which are not equidistant from the vertices u and v. In this paper we compute the PI index of polyomino chains of 4k-cycles and establish bounds for it. Keywords Graph invariant · PI index · Polyomino chain Mathematics Subject Classification (2000) 92E10 · 05B50
1 Introduction Like in many other branches of mathematics one tries to find in graph theory certain invariants of graphs which only depend on the graph G itself (or—in other cases—in addition on an embedding into the plane or some other manifold), see, e.g., [14] and the references given therein. One of the simplest such invariants is the adjacency matrix A(G) with columns and rows indexed by the vertices of the graph, such that the uv-entry of the matrix is equal to the number of arcs between the vertices u and v. The spectrum of the adjacency matrix σ (A(G)) is called the spectrum of the graph and the dependence of the spectrum from the graph has been considered in great detail, see, e.g., [7] and the references given therein. If σ (G) ≡ σ (A(G)) = {λ1 (G), . . . , λn (G)} is the spectrum of G then any function of the eigenvalues may be used as graph invariant. For example, Gutman defined in [15] the energy of the graph G as E (G) = ni=1 |λi (G)| and this invariant has been studied thoroughly since then.As a more recent example, the Estrada-index has been defined by Estrada as EE(G) = ni=1 eλi (G) [11] and many applications of it in chemistry and network science
T. Mansour Department of Mathematics, University of Haifa, 31905 Haifa, Israel e-mail: [email protected] M. Schork () Camillo-Sitte-Weg 25, 60488 Frankfurt, Germany e-mail: [email protected]
672
T. Mansour, M. Schork
have been considered. Of course, it is possible to define many other graph invariants which are not based on the spectrum of the adjacency matrix but directly on the vertices and edges of the graph and the distances between them. For example, in acyclic graphs the Wiener index is defined as W (G) = e∈E(G) Ni,e Nj,e , where E(G) denotes the set of edges of G and Nk,e denotes the number of vertices lying on the side of the edge e having the endpoint k [10, 18, 31]. Arguably, the Wiener index is the most famous such index but many other related indices have been considered, see, e.g., [10]. The motivation for the study of these objects is twofold: on the one hand one has the purely mathematical desire to understand the intrinsic properties of graphs and the connections between them better while on the other hand these indices are applied in chemistry as topological indices, capturing some of the properties of a molecule in a single number. Let us, therefore, turn to chemical applications of graph theory. Soon after the mathematical formulation of quant
Data Loading...
