Scientific paper Counting Polynomials in Tori T(4,4)S [c,n] Mircea V. Diudea Faculty of Chemistry and Chemical Engineering, Babes-Bolyai University, 3400 Cluj, Romania * Corresponding author: E-mail: diudea@gmail.com Received: 28-04-2010 This paper is dedicated to Professor Milan Randic on the occasion of his 80th birthday Abstract A counting polynomial P(x) is a description of a graph property P(G) in terms of a sequence of numbers so that the exponents express the extent of its partitions while the coefficients are related to the number of partitions of a given extent. Basic definitions and some properties are given for two classes of polynomials, called here polynomials of vertex proximity and edge proximity, respectively. Formulas to calculate these polynomials in T(4,4)[c,n] tori are derived by a cutting procedure. Keywords: counting polynomials, Cluj polynomial, Omega polynomial, cutting procedure. 1. Polynomials in Chemistry A single number, representing a chemical structure, in graph-theoretical terms, is called a topological index TI. It must be a structural invariant, do not depending on the labeling or the pictorial representation of a graph. TIs have found broad applications in the correlation (estimation and prediction) with various molecular properties.1 Another representation which has gained particular attention, both from theoretical point of view and applications is by polynomials. In Quantum Chemistry, the early Huckel theory calculates the levels of n-electron energy of the molecular orbitals, in conjugated hydrocarbons, as roots of the characteristic polynomial:1- In the above, I is the unit matrix of a pertinent order and A the adjacency matrix of the graph G. The characteristic polynomial is involved in the evaluation of topologi-cal resonance energy TRE, the topological effect on molecular orbitals TEMO, the aromatic sextet theory, the Ke-kule structure count, etc.4-8 The coefficients m(k) in the polynomial expression: are calculable from the graph G by a method making use of the Sachs graphs, which are subgraphs of G. Some numeric methods of linear algebra, can eventually be more efficient in large graphs.9,10 The spectrum Sp(M) represents the eigenvalues of the matrix M(G) (or the solutions of its related polynomial P(M, x)); its extreme values MaxSp(M) and Min-Sp(M) are used as topological indices in correlating studies. Other numbers of interest are the values (in x = 1) of the polynomial P(M,1) (or the sum of (absolute values) of the polynomial coefficients, see Hosoya's Z index11) and its first two derivatives P'(M,1) and P''(M,1). More about the characteristic polynomial, the reader can find in ref.1 Relation (2) is a general expression of a counting polynomial (in fact a sequence of numbers), with the exponents showing the extent of partitions p(G), u p(G) = P(G) of a graph property P(G) while the coefficients m(k) are related to the number of partitions of extent k. In the Mathematical Chemistry literature, the counting polynomials have firstly been introduced by Hoso-ya:11,12 Z(x) counts independent edge sets while H(x) (initially called Wiener and later Hosoya)12-14 counts the distances in G. Further, Hosoya also proposed the sextet polynomial1518 for counting the resonant rings in a benze-noid molecule.19,20 Other counting polynomials have later been proposed: independence, king, color, star or clique polynomials.21-28 2. Polynomials of Vertex Proximity Cluj polynomials are defined,29-32 on the basis of vertex proximities p,, as in (2): summation runs over all k = {p} in G with p being the proximity of the vertex i with respect to any vertex j in G, joined to i by an edge {pe i} (the Cluj-edge polynomials) or by a path {ppi} (the Cluj-path polynomials), taken as the shortest (i.e., distance DI) or the longest (i.e., detour DE) paths. In (2), the coefficients m(k) can be calculated from the entries of unsymmetric Cluj matrices (as provided by the TOPOCLUJ software program),33 which represent vertex proximities. To define these, we need some theoretical background, as follows. A graph G is a partial cube if it is embeddable in the «-cube Qn, which is the regular graph whose vertices are all binary strings of length n, two strings being adjacent if they differ in exactly one position.34 The distance function in the n-cube is the Hamming distance. A hyper-cube can also be expressed as the Cartesian product of n edges: Qn = K2, K2 being the complete graph on two points or simply an edge. A subgraph K c G is called isometric, if dH (u, v) = dG (u, v), for any (u, v) e H; it is convex if any shortest path in G between vertices of H belongs to H. For any edge e = (u,v) of a connected graph G let nuv denote the set of vertices lying closer to u than to v: nuv = {we V (G) | d(w, u) < d(w, v)} . It follows that nuv = {we V (G) | d (w, v) = d (w, u) + 1}. The sets (and subgraphs) induced by these vertices, nuv and nvu , are called semicubes of G; the semicubes are called opposite semicubes and are disjoint. 35 A graph G is bipartite if and only if, for any edge of G, the opposite semicubes define a partition of G: nuv + nvu = v = | V(G) . These semicubes are just the vertex proximities of (the endpoints of) edge e = (u,v), which CJ polyno- mial counts. In partial cubes, the semicubes can be estimated by an orthogonal edge-cutting procedure. The orthogonal cuts form a partition of the edges in G: E(G) = c1 u c2 u ... u ck, ct n Cj = 0, i # j. To perform the orthogonal edge-cutting procedure:32,36-39 take a straight line segment, orthogonal to the edge e, and intersect e and all its parallel edges (in a polygonal plane graph). The set of these intersections is called an orthogonal cut ck, k = 1,2,.., kmax of G, with respect to the edge e (Figure 1). To any orthogonal cut ck, two numbers are associated: first one represents the number of edges ek "cut-off', or the cutting cardinality | ck | while the second (in round brackets, in Figure 1) is vk or the number of points lying to the left hand with respect to ck. Cluj polynomials and some related ones are calculable from the semicubes in G (see the polynomial exponents, Figure 1), they differing only in the mathematical operation used in composing the edge contributions to the global graph property. Because, in a bipartite graph, the opposite semicubes define a partition of vertices, it is easily to identify the two semicubes: nuv = vk and nvu = v - vk or vice-versa. The coefficients of these descriptors are calculated (with some exceptions) as the product of three numbers (in the front of brackets - right hand part of Figure 1) with the meaning: (i) symmetry of G; (ii) occurrence of ck (in the whole structure) and (iii) ek. According to the mathematical operation used in composing the graph semicubes, four polynomials can be defined: (i) Summation, and the polynomial is called Cluj-Sum, by Diudea et al.29-32,38-40 (and symbolized CJeS): (3) Figure 1. Calculating of several topological descriptors by the Cutting procedure CJ S(x) = 3 ■ 3 ■ 2(x5 + x19) + 3 ■ 4 ■ 1(x12 + x12) CJ S'(1) = 720; PIv(x) = 3 -3 ■ 2(x5+19) + 3 ■ 4 ■ 1(x12+12) = 30X24; 'Pi; (1) = 720; CJP(x) = 3 ■ 3 ■ 2(x5-19) + 3 ■ 4 ■ 1(x12-12) = 18x95 + 12x144 = SZ(x) CJ P'(1) = 3438; W(x) = 3 ■ 2(x5-19) + 3 ■ 1(x12-12) W'(1) = 1002; Q(x) = 3 ■ 2x3 + 3x4 Q(x) = 30 = e = |E(G)| CI(G) = 798; 0(x) = 3(3 ■ 2)x3 + 4(3)x4 0(1) = 102; n(x) = 3(3 ■ 2)x27 + 4(3)x26 n(1) = 798 = PI'(1) (ii) Pair-wise summation, with the polynomial called (vertex) Padmakar-Ivan41 by Ashrafi42-45 (and symbolized PIv): (4) (iii) Pair-wise product, while the polynomial is called Cluj-Product (and symbolized CJeP)32,38,46-50 or also Szeged polynomial (and symbolyzed SZ):43-45 CJ,P{x) = SZ(x) = XX (5) (iv) Single edge pair-wise product; the polynomial is called Wiener and symbolized W:39 (6) The first derivative (in x = 1) of a (graph) counting polynomial provides single numbers, often called topological indices. It is not difficult to see that the first derivative (in x = 1) of the first two polynomials gives one and the same value; however, their second derivative is different and the following relations hold in any graph:31 C/.S'(1) = /7/(1); C/,S"(l) * /Y/(l) (7) The number of terms is given by the value of the polynomial in x = 1: it is C/eS(1) = 2e and PIv(1) = e, respectively, because in the last case the two endpoint contributions are pair-wise summed for any edge in a bipartite graph. Observe the first derivative (in x = 1) of PIv(x) takes the maximal value in bipartite graphs: P/v'(l) = e-v=| E(G) | • | V(G) | (8) It can also be seen by considering the definition of the corresponding index, as written by Ilic:51 PIJG) = Pi;i 1) = £ «„,,. + «,.„ = \v\-\E\- Z (9) where nu v, n count the non-equidistant vertices with respect to the endpoints of the edge e = (u,v) while m(u,v) is the number of equidistant vertices vs. u and v. However, it is known that, in bipartite graphs, there are no equidistant vertices vs. any edge, so that the last term in (8) will miss. The value of PIv(G) is thus maximal in bipartite graphs, among all graphs on the same number of vertices; the result of (7) can be used as a criterion for checking the "bi-patity" of a graph. The third polynomial uses the pair-wise product; notice that Cluj-Product CJeP(x) is precisely the (vertex) Szeged polynomial SZv(x), defined by Ashrafi et al.43-45 This comes out from the relations between the basic Cluj (Diudea46-485253) and Szeged (Gutman53 54) indices: CJeP\X) = CJpim = SZ{G) = SZ,'(l) (10) The first three above polynomials (and their derived indices) do not count the equidistant vertices, an idea introduced in Chemical Graph Theory by Gutman.54 The last polynomial was called Wiener by Diudea, because it is calculated as Wiener performed the index W(G) in tree graphs: multiply the number of vertices lying to the left and to the right of each edge (actually read orthogonal cut ck): (11) where vk and v-vk are the cardinalities of the disjoint semi-cubes forming a partition with respect to each edge in ck taken, however, as a "single edge" (as in trees). A graph in which the following inequality holds is not a partial cube:38,39 (12) The quantity |S(G)| is the cardinality of the sets of all cuts in G. An example of equality in (12), which represents the upper bond in the cutting procedure, will be given in the next section. However, a value of W(G) lower than the upper bond does not ensure G is a partial cube. In such a case, trying to perform the cutting procedure, a value vk > v/2 will indicate a non-convex, non-isometric subgraph and thus a graph which is not a partial cube. According to Klavzar,37 W(G) is calculable by the cutting procedure only in partial cubes. A last remark on W(x): in partial cubes, its exponents are identical to those in CJP(x) = SZ(x) while the coefficients are those in the above polynomials, divided by ek. When subscript letter is missing, SZ(x) is SZv(x). 3. Polynomials of Vertex Proximity in Square-tiled Tori The cutting procedure we applied on square-tiled tori T(4,4)[c,n]. It can be seen (Figure 2), there are only two cutting types: circular "cir"(around the large hollow) and across "acr" the tube. Accordingly, the proximities are easily calculable from the net parameters c (the number of atoms/points across the tube) and n (the number of cross-sections around the torus large hollow). Formulas are given in Table 1, for the four polynomials and their topolo-gical indices, along with some examples. Note, in Table 1, entry 4, the coefficients of W(x) are just the number of cuts across the tube (n/2) and the circular cuts (c/2), respectively: n/2 + c/2 = | S(G) |, while the exponent is the pair-wise product of the graph semicubes Figure 2. Cutting procedure in square-tiled tori T(4,4)[c,n]: circular (top) and across (bottom) cuttings ((v/2)2 ), of which first derivative (in x = 1) equals the upper bond (11) in the cutting procedure. Also note, W(x) is defined only in "all even" tori, which are partial cubes. 4. Polynomials of Edge Proximity Let G = (V(G),E(G)) be a connected graph, with the vertex set V(G) and edge set E(G). Two edges e = (u,v) and f = (x,y) of G are called co-distant (briefly: e co f ) if the notation can be selected such that35,55 where d is the usual shortest-path distance function. Relation co is reflexive, that is, e co e holds for any edge e of G and it is also symmetric: if e co f then also f co e. In general, co is not transitive. A graph is called a co-graph if the relation co is transitive and thus an equivalence relation. For an edge e e E (G), let c(e): = {f e E(G); f co e} be the set of edges codistant to e in G. The set c(e) can be obtained by an orthogonal cut oc of G, with respect to e. If G is a co-graph then its orthogonal cuts form a partition in G (see above). A bipartite graph G is a co-graph if and on- Table 1. Formulas for the Polynomials of Vertex Proximity in Square-tiled Tori T(4,4)[c,n] Formulas c(n- p,)/2 + xc(n- p„)/2] + cn[x*'c- Pc)'2 + x"^- pc)'2] cn/2. CJS(x) = cn[x' CJS(x) = cn ■ 2xcn/2 + cn ■ 2xa""; c,n - even CJS'(1) = cn(2cn - c -n; c,n - odd CJS'(1) = 2c2 2n2; c,n - even CJS'(1) = cn2 (2c - 1); c - odd; n - even CJS'(1) = c2n2(2n - 1); c - even; n - odd Examples H[7,35]; CJS(x) = 490x119 + 490x105; CJS'(1) = 109760 H[8,40]; CJS(x) = 1280x160; CJS'(1) = 204800 H[7,20]; CJS(x) = 280x70 + 280x60; CJS'(1) =36400 H[8,35]; CJS(x) = 560x140 + 560x136; CJS'(1) = 154560 x["(c- Pc)/2] + cn • x(c"/2)2 c, n - even CJP(x) = cn • x[c(n-p")/2]2 CJP(x) = cn • x(cn/2)2 CJP'(1) = (cn /4)(2c2n2 - 2c2n + c2-2cn2 + n2); c, n - odd CJP'(1) = cn(c2n2 / 4) + cn(c2n2 /4); c, n - even CJP'(1) = (cn3 / 4)(2c2 - 2c + 1); c - odd, n - even CJP'(1) = (c3n / 4)(2n2 - 2n + 1); c - even, n - odd Examples H[7,35]; CJP(x) = 245x11025+245x14161; CJP'(1) = 6170570 H[8,40]; CJP(x) = 3 20x25600 +3 20x25600; CJP'(1) = 16384000 H[7,20]; CJP(x) = 140x3600+140x4900; CJP'(1) = 1190000 H[8,35]; CJP(x) = 280x18496+280x19600; CJP'(1) = 10666880 PIv(x) = cn ■ xc(n-p") + cn ■ xn(c-pc) PIv(x) = 2cn ■ xcn; c, n - even PI'v(1) = cn(2cn - c - n); c, n - odd PI'v(1) = 2c2n2; c, n - even PI'v(1) = cn2(2c - 1); c - odd, n - even PI' (1) = c2n(2n - 1); c - even, n - odd Examples H[7,35]; PIv(x) = 245x238 + 245 x210; PIv'(1) = 109760 H[8,40]; PIv(x) = 640x320; PIv'(1) = 204800 H[7,20]; PIv(x) = 140x140 + 140x120; PIv'(1) = 36400 H[8,35]; PIv(x) = 280x280 + 280x272; PIv'(1) = 154560 4 W(x) = (cn / 2c) ■ x(v / 2)2 + (cn / 2n) ■ x(v / 2)2 = (n / 2 + c /2) ■ x(cn / 2)2; c, n - even W'(1) = (n /2 + c / 2)(c2n2 /4); c, n - even v =| V(G) |= e =| E(G) |= 2cn Example H[8,40]; W(x)= 20x25600+4x25600; W'(1)= 614400 1 2 3 ly if it is a partial cube, and all its semicubes are convex. However, a co-graph can also be non-bipartite39 (e.g., it shows a transitive co-relation but has at least one odd cycle, thus being no more a partial cube). It was proven that relation co is a theta (Djokovic56) and Winkler57) relation. Two edges e and f of a plane graph G are in relation opposite, e op f, if they are opposite edges of an inner face of G. Then e co f holds by assuming the faces are isometric. Note that relation co involves distances in the whole graph while op is defined only locally (it relates face-opposite edges). If G is a co-graph, then its opposite edge strips ops {sj superimpose over the orthogonal cut sets ocs {ck} and |ck| = Isk|. Using the relation op we can partition the edge set of G into opposite edge strips, ops: any two subsequent edges of an ops are in op relation and any three subsequent edges of such a strip belong to adjacent faces. Note that John et al.55 implicitly used the "op" relation in defining the Cluj-Ilmenau index CI (see below). Let us denote by m(s) or simply m the number of ops of length s = jskj and define the Omega polynomial as.35,58-67 (14) The exponents count just the intersected edges by the cut-line (in a cutting procedure), which does not need to be orthogonal on all the edges of an ops. A second polynomial which is calculated from the ops in G, but counting non-opposite edges, is the Sadhana Sd polynomial68,69 Sd{x)=^ m xe~s (15) In co-graphs/partial cubes, other two related polyno- mials can be calculated on ops. (16) (17) The above polynomials count codistant and non-co-distant edges, respectively. Thus, non-co-distance is related to edge-proximity, and the name of these polynomials is immediate. In arbitrary connected graphs, the strips ops {sk} does not fit the orthogonal cuts ocs {ck} any more; then, in formulas (15) and (16) s must be changed by c (now with the meaning of the cardinality of co-distant edges in G) and the coefficients, accordingly. The first derivative (computed at x = 1) of these counting polynomials provide interesting topological in-dices.35,70,71 = m{e-s) = Sd{G) n'(l) = ^sms(e-s) - 77(G) (19) (20) (21) On Q(x) an index, called Cluj-Ilmenau55 CI(G), was defined CI(G) = {[Q'(\)f-m l) + n"(l)]} (22) 35,70 CI(G) = In co-graphs, there is the equality n(G). It can be obtained applying the definition (21): CI(G) = (£ /mf -[ £ m+£tms{s-1)] = = /)iï2=ri(G) (23) Relation (22) is just the formula proposed by John et al.72 to calculate the Khadikar's PI index.28 According to Ashrafi's notations,73 PIe (to difer from PIv) can be written as: «.( d(x,e) = d(y,e) and d(u,f) = d(v,f) (26) In bipartite graphs (26) superimposes to (13) but not in general graphs, thus appearing a difference between the index n(G) and PIe(G) (hereafter denoted n(G)_Diu and PIe(G)_Ash). The problem of equidistance of vertices was firstly put by Gutman when defined the Szeged index54 SZ(G) of which calculation leaves out the equidistant vertices. Similarly, the index PIe(G) does not account for the equidistant edges. This index can be calculated as the first derivative, in x = 1, of the polynomial defined by Ashrafi73 as: (18) Plt(x}= I * eeE{G) In bipartite graphs, either co-graphs or not, the equality: n(G) = PIe(G) is true, but not in general graphs. In partial cubes, since they are also bipartite, the previous equality can be expanded to the triple one a relation precisely true in partial cubes but not in all co-graphs (namely those being non-bipartite). Table 2. Formulas for the Polynomials of Edge Proximity in Square-tiled Tori T(4,4)[c,n] Formulas 1 Q(x) = n ■ xc + c ■ xn Q'(1) = 2nc; Q"(1) = cn(c + n - 2) CI (G) = cn(4cn + c - n) Examples H[5,15]; 15x5 + 5x15; CI = 21000 H[5,20]; 20x5 + 5x20; CI = 37500 H[8,40]; 40x8 + 8x40; CI = 394240 2 Sd(x) = n ■ xe-c + c ■ xe-n Sd'(1) = n(e - c) + c(e - e) Examples H[5,15]; 15x145 + 5x135; Sd'(1) = 2850 H[5,20]; 20x195 + 5x180; Sd'(1) = 4800 H[8,40]; 40x632 + 8x600; Sd'(1) = 30080 3; 0(x) = cn ■ x(c + pc') + cn ■ Xn + p"); c, n - odd c,n-odd; 0'(1) = cn(c + n + 2); c, n - odd nDiu(x) = cn ■ x[2cn - (c + pc)] + cn ■ x[2cn - (n+p«)]; c, n - odd n'Diu(x) = cn(4cn - c - n - 2); c, n - odd PleAsh(x) = nDiu(x) - [m ■ X"eacr~ c + 1) + m ■ x(eacr- " + 1)] = cn ■ x[2cn - (2c+pc) + 1] + cn ■ x[2cn - (2n+p«) + 1]; c, n - odd Pl'eAsh(x) = cn(4cn - 2c - 2n); c, n - odd Examples H[7,35]; 0(x) = 245x8 + 245x36; 0'(1) = 10780 nDiu) = 245x454 + 245x482; WDm(1) = 229320 Pl^h(x) = 245x476 + 245x420; Pl^D = 219520 4; 0(x) = cn ■ x2c + cn ■ x2n; c, n - even c,n-even; 0'(1) = cn(2c + 2n); c, n - even bipartite nDiu(x) = cn ■ x2c(n- 1) + cn ■ x2n(c- 1); c, n - even n'Diu(1) = 2cn(2cn - c - n); c, n - even Ple,Ash(x) = nDiu(x); ^ n - even Examples H[8,40]; 0(x) = 320x16 + 320x80; 0'(1) = 30720 nDiu (x) = 320x560 + 320x624; n^d) = 37888 Ple,Ash(x) = 320x624 + 320x560; Pl^d) = 37888 5; 0(x) = cn ■ x2c + cn ■ xn; c - odd; n - even c-odd; 0'(1) = cn(2c + n); c - odd; n - even n-even nDiu (x) = cn ■ x2c(n - 1) + cn ■ xn(2c - 1); c - odd; n - even n'Diu(1) = cn(4cn - 2c - n); c - odd; n - even Ple,Ash(x) = nDiu^ m ■ x(*cir - n) = cn ■ x2c(n 1) + cn ■ x2n(c 1); c - odd; n - even Pl'Ash(1) = 2cn(2cn - c - n); c - odd; n - even Examples H[7.20]; 0(x) = 140x14+140x20; 0'(1) = 4760 nDiu = 140x260+140x266; n'Diu(1) = 73640 Pl A h(x) = 140x266 + 140x24°u Pl'Ash(1) = 70840 6; 0(x) = cn ■ xc + cn ■ x2"; c - even; n - odd c-even; 0'(1) = cn(c + 2n); c - even; n - odd n-odd nDiu (x) = cn ■ xc(2n - 1) + cn ■ x2nic - 1); c - even; n - odd n'Diu(1) = cn(4cn - c - 2n); c - even; n - odd Ple,Ash(x) = nDiu - m ■ x(*acr - c) = cn ■ x2c(n 1) + cn ■ x2n(c 1); c - even; n - odd Pl'Ash(1) = 2cn(2cn - c - n); c - even; n - odd Examples H[8,35]; 0(x) = 280x8+280x70; 0'(1) = 21840 nDiu = 280x490+280x552; WDm(1) = 291760 _Ple,AJx) = 280x544 + 280x490; Pl'eAJ1) = 289520 Resuming, in bipartite graphs, an orthogonal edge-cutting procedure36-39 can be used to generate the ops. Formulas for the above four polynomials in square-tiled tori T(4,4)[c,n] are given in Table 2, along with some examples. In formulas of 0(x), n(x) and PI(x), more cases must be considered to account for the net parameter parity. The cutting procedure is limited to bipartite graphs, particularly to planar polyhex structures. In such molecular graphs, the descriptors derived from Cluj and Omega polynomials have been successfully used to predict the boiling points, index of chromatographic retention or their 30 47 74-76 resonance energy.30,4/,/4-'6 Among the single number descriptors provided by the Omega polynomial, one is of particular importance: n , which equals the coefficient at the first power term, and also the number of pentagon fusions. This number accounts for more than 90% of variance in the heat of formation or in the strain energy of small fullerenes, e.g., C40 and C50.67 5. Acknowledgements The work was supported by the Romanian Grant CNCSIS PN-IIIDEI 506/2007 6. References 1. M. V. Diudea, I. Gutman, L. Jantschi, Molecular Topology, NOVA, New York, 2002. 2. F. Harary, SIAM Rev. 1962, 4, 202-210. 3. H. Sachs, Publ. Math. (Debrecen), 1964, 11, 119-134. 4. N. Trinajstic, Chemical Graph Theory, IInd Ed. CRC Press, 1992. 5. Gutman, M. Milun, N. Trinajstic, MATCH Commun. Math. Comput. Chem. 1975, 1, 171-175. 6. J. Aihara, J. Am. Chem. Soc. 1976, 98, 2750-2758. 7. Gutman, M. Milun, N. Trinajstic, J. Am. Chem. Soc. 1977, 99, 1692-1704. 8. Tang, Y. Kiang, G. Yan, S. Tai, Graph Theoretical Molecular Orbitals; Science Press, Beijing, 1986. 9. P. S. Dwyes, Linear Computations, Wiley, New York, 1951. 10. D. K. Fadeev, I. S. Sominskii, Problems in Higher Algebra, Freeman, San Francisco, 1965. 11. H. Hosoya, Bull. Chem. Soc. Japan 1971, 44, 2332-2339. 12. H. Hosoya, Discrete Appl. Math. 1988, 19, 239-257. 13. E. V. Konstantinova, M. V. Diudea, Croat. Chem. Acta 2000, 75, 383-403. 14. Gutman, S. Klavzar, M. Petkovsek, P. Zigert, MATCH Commun. Math. Chem. 2001, 43, 49-66. 15. H. Hosoya, T. Yamaguchi, Tetrahedron Lett. 1975, 46594662. 16. N. Ohkami, H. Hosoya, Theoret. Chim. Acta 1983, 64, 153-170. 17. N. Ohkami, A. Motoyama, T. Yamaguchi, H. Hosoya, Tetrahedron, 1981, 37, 1113-1122. 18. H. Hosoya, Topics Curr. Chem. 1990, 153, 255-272. 19. E. Clar, Polycyclic Hydrocarbons, Acad. Press, London, 1964. 20. E. Clar, The Aromatic Sextet, Wiley, New York, 1972. 21. Gutman, H. Hosoya, Z Naturforsch. 1990, 45a, 645-648. 22. Gutman, MATCH Commun. Math. Chem. 1992, 28, 139150. 23. D. Stevanovic, Graph Theory Notes New York 1998, 34, 31-36. 24. Motoyama, H. Hosoya, J. Math. Phys. 1977, 18, 1485-1490. 25. K. Balasubramanian, R. Ramaraj, J. Comput. Chem. 1985, 6, 447-454. 26. E. J. Farrell, Canad. Math. Bull. 1978, 2, 35-46. 27. E. J. Farrell, C. De Matas, Ark. Math. 1988, 26, 185-190. 28. E. J. Farrell, C. De Matas, Util. Math. 1988, 33, 33-45. 29. M. V. Diudea, J. Math. Chem. 2009, 45, 295-308. 30. M. V. Diudea, A. E. Vizitiu, D. Janezic, J. Chem. Inf. Model. 2007, 47, 864-874. 31. M. V. Diudea, A. Ilic, M. Ghorbani, A. R. Ashrafi, Croat. Chem. Acta 2009, accepted. 32. M. V. Diudea, N. Dorosti, A. Iranmanesh, Carpath. J. Math. 2009, accepted. 33. O. Ursu, M. V. Diudea, TOPOCLUJ software program, Ba-bes-Bolyai University, Cluj, 2005. 34. F. Harary, Graph theory, Addison-Wesley, Reading, MA, 1969. 35. M. V. Diudea, S. Klavzar, Acta Chim. Slov. (this issue) 36. Gutman, S. Klavzar, J. Chem. Inf. Comput. Sci. 1995, 35, 1011-1014. 37. S. Klavzar, MATCH Commun. Math. Comput. Chem. 2008, 60, 255274. 38. M. V. Diudea, Counting polynomials in partial cubes, in I. Gutman, B. Furtula, (Eds.) Novel molecular structure descriptors - theory and applications I, Univ. Kragujevac, Kra-gujevac, 2010, pp. 191-215. 39. M. V. Diudea, MATCH Commun. Math. Comput. Chem. 2010, 64(3), 000-000. 40. E. Vizitiu, M. V. Diudea, Studia Univ. »Babes-Bolyai« 2009, 54(1), 173-180. 41. P. V. Khadikar, Nat. Acad. Sci. Lett. 2000, 23, 113-118. 42. M. H. Khalifeh, H. Yousefi-Azari, A. R. Ashrafi, Discrete Appl. Math. 2008, 156, 1780-1789. 43. M. H. Khalifeh, H. Yousefi-Azari, A. R. Ashrafi, Linear Algebra Appl. 2008, 429, 2702-2709. 44. R. Ashrafi, M. Ghorbani, M. Jalali, J. Theor. Comput. Chem. 2008, 7, 221-231. 45. T. Mansour, M. Schork, Discr. Appl. Math. 2009, 157, 1600-1606. 46. M. V. Diudea, J. Chem. Inf. Comput. Sci. 1997, 37, 300-305. 47. M. V. Diudea, MATCH Commun. Math. Comput. Chem. 1997, 35, 169-183. 48. M. V. Diudea, B. Parv, I. Gutman, J. Chem. Inf. Comput. Sci. 1997, 37, 1101-1108. 49. Gutman, M. V. Diudea, J. Serb. Chem. Soc. 1998, 63, 497504. 50. V. Diudea, G. Katona, I. Lukovits, N. Trinajsti}, Croat. Chem. Acta 1998, 71, 459-471. 51. Ilic, Appl. Math. Lett. 2009, submitted. 52. M. V. Diudea, Croat. Chem. Acta 1999, 72, 835-851. 53. M. V. Diudea, I. Gutman, L. Jäntschi, Molecular Topology. NOVA, New York, 2002. 54. Gutman, Graph Theory Notes New York, 1994, 27, 9-15. 55. P. E. John, A. E. Vizitiu, S. Cigher, M. V. Diudea, MATCH Commun. Math. Comput. Chem. 2007, 57, 479-484. 56. D. Ž. Djokovic, J. Combin. Theory Ser. B 1973, 14, 263-267. 57. P. M. Winkler, Discrete Appl. Math. 1984, 8, 209-212. 58. M. V. Diudea, Carpath. J. Math. 2006, 22, 43-47. 59. R. Ashrafi, M. Jalali, M. Ghorbani, M.V. Diudea, MATCH Commun. Math. Comput. Chem. 2008, 60, 905-916. 60. M. V. Diudea, A. Ilic, Carpath. J. Math. 2009, 25, 177-185. 61. E. Vizitiu, M. V. Diudea, MATCH Commun. Math. Comput. Chem. 2008, 60, 927-933. 62. M. V. Diudea, J. Math. Chem. 2009, 45, 309-315. 63. M. V. Diudea, A. E. Vizitiu, F. Gholaminezhad, A. R. Ashrafi, MATCH Commun. Math. Comput. Chem. 2008, 60, 945-953. 64. M. V. Diudea, MATCH Commun. Math. Comput. Chem. 2008, 60, 935-944. 65. M. V. Diudea, S. Cigher, A. E. Vizitiu, O. Ursu, P. E. John, Croat. Chem. Acta, 2006, 79, 445-448. 66. E. Vizitiu, S. Cigher, M. V. Diudea, M. S. Florescu, MATCH Commun. Math. Comput. Chem. 2007, 57, 457-462. 67. M. V. Diudea, S. Cigher, A. E. Vizitiu, M. S. Florescu, P. E. John, J. Math. Chem. 2009, 45, 316-329. 68. R. Ashrafi, M. Ghorbani, M. Jalali, Indian J. Chem. 2008, 47A, 535-537. 69. R. Ashrafi, M. Mirzargar, Indian J. Chem. 2008, 47A, 538541. 70. M. V. Diudea, S. Cigher, P. E. John, MATCH Commun. Math. Comput. Chem. 2008, 60, 237-250. 71. M. V. Diudea, A. E. Vizitiu, M. Mirzargar, A. R. Ashrafi, Carpath. J. Math. 2010 (in press). 72. P. E. John, P. V. Khadikar, J. A. Singh, J. Math. Chem. 2007, 42, 37-45. 73. R. Ashrafi, B. Manoochehrian, H. Yousefi-Azari, Util. Math. 2006, 71, 97-108. 74. M. Randic, New J. Chem. 1995, 19, 781-791. 75. M. Randic, Acta Chim. Slov. 1998,45, 239-252. 76. M. Randic, New J. Chem. 1996, 20, 1001-1009. Povzetek Stevni polinom P(x) opisuje lastnost grafa P(G) v obliki zaporedja številk, tako da eksponenti izražajo obseg njegovih porazdelitev, medtem ko so koeficienti povezani s številom porazdelitev pri danem obsegu. Podane so osnovne definicije in nekaj lastnosti za dva razreda polinomov, tako imenovanih polinomov za opis bližnjosti vozlov in robov. Formule za izračun teh polinomov v T (4,4) [c,n] torih so izpeljane z metodo rezanja.