Scientific paper Omega Polynomial Revisited Mircea V. Diudea1'* and Sandi Klavžar2 1 Faculty of Chemistry and Chemical Engineering, "Babes-Bolyai" University, 400028 Cluj, Romania 2 Faculty of Mathematics and Physics, University of Ljubljana, Jadranska 19, 1000 Ljubljana, Slovenia and Faculty of Natural Sciences and Mathematics, University of Maribor, Koroška 160, 2000 Maribor, Slovenia * Corresponding author: diudea@gmail.com Received: 11-05-2010 This paper is dedicated to Professor Milan Randi} on the occasion of his 80th birthday Abstract Omega polynomial was proposed by Diudea (Omega Polynomial, Carpath. J. Math., 2006, 22, 43-47) to count the opposite topologically parallel edges in graphs, particularly to describe the polyhedral nanostructures. In this paper, the main definitions are re-analyzed and clear relations with other three related polynomials are established. These relations are supported by close formulas and appropriate examples. Keywords: Counting polynomials: Omega, Theta, Pi, Sadhana; Cluj-Ilmenau CI index 1. Introduction Recently several graph polynomials were introduced in mathematical chemistry to give further insights into the structure and properties of chemical graphs. In particular, the first derivative of such polynomials computed at a given value returns a corresponding topological index of interest. A graph polynomial, also called a counting polynomial, can be written as P(G,x) = Xkm(G,k) ■ xk, 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(G,k) are related to the number of partitions of extent k. Counting polynomials have been introduced, in the Mathematical Chemistry literature, by Hosoya,1,2 to count independent edge sets (the Z-polynomial) and the distances in the graph (the Wiener polynomial, latter called the Hosoya polynomial and denoted H(G,x).3,4 The same author also proposed the sextet polynomial5,6 to count the resonant rings in a benzenoid molecule. Other counting polynomials are the independence polynomial,7 9 domino,10 star,11 and clique12 polynomials. More about polynomials the reader can find in ref .13 Some distance-related properties can be expressed in polynomial form, with coefficients calculable from the layer and shell matrices.14-17 These matrices are built up according to the vertex distance partitions of a graph, as provided by the TOPOCLUJ software package.18 The most important, in this respect, is the evaluation of the coefficients of Hosoya H(G,x) polynomial from the layer of counting (LC) matrix. The aim of this paper is to give a unified approach to these polynomials and invariants and to give links to the existing concepts in pure mathematics. 2. Relation co and Its Relatives Let G=(V(G),E(G)) be a connected graph, with the vertex set V(G) and edge set E(G). Two edges e = uv and f = xy of G are called codistant (briefly: e co f ) if the notation can be selected such that19 d(v, j) = d(v,y) +1 = d(u, x)+\ = d{u,y), (1) where d is the usual shortest-path distance function. Cleary, relation co is reflexive, that is, e co e holds for any edge e of G. Relation co is also symmetric: if e co f then also f co e. On the other hand, co is in general non-transitive, a small example demonstrating this fact is the complete bipartite graph K2 3 (Figure 3, with only three points of degree 2 or with a single bent line inside the square). A graph is called a co-graph if the relation co is transitive and thus an equivalence relation. The cubic net in Figure 1, b is a co-graph. For an edge e e E(G), let C(e): = {f e E(G); f co e} be the set of edges in G that are codistant to e. For instance, if e is an arbitrary edge of the complete bipartite graph K2n, then C(e) consists of all the edges that are not adjacent to e. The set C(e) is called an orthogonal cut (oc for short) of G (with respect to e). If G is a co-graph then its orthogonal cuts C1,C2,...,Ck form a partition of E(G): E(G) = C1 u C2 u ... u Ck, C n Cj = 0, i * j. Let us first turn the attention to bipartite graphs. To state several characterizations of bipartite co-graphs, further definitions are needed. A subgraph H 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. The n-cube Qn is the graph whose vertices are all binary strings of length n, two strings being adjacent if they differ in exactly one position.20 (Note that the distance function in the n-cube is just the Hamming distance: the distance between two vertices of Qn is equal to the number of positions in which they differ.) A graph G is called a partial cube if there exists an integer n such that G is an isometric subgraph of Qn. For any edge ab of a connected graph G let Wab denote the set of vertices lying closer to a than to b: Wab = {w e V(G)\d(w,a) < d(w,b)}. It follows from the definition that Wab = {w e V(G)\d(w,b) = d(w,a) + 1}. We will use Wab also to denote a subgraph induced by these vertices. Then the sets (and subgraphs) Wab are called semicubes of G. The semicubes Wab and Wba are opposite semicubes. Clearly, two opposite semicubes are disjoint. Moreover, a graph G is bipartite if and only if, for any edge of G, the opposite semicubes form a partition of V(G). Finally, let G be a connected graph and e = uv and f = xy edges of G. Then e0f if d(u,x) + d(v,y) * d(u,y) + d(v,x). Now everything is defined for the following result. THEOREM 1. The following statements are equivalent for a bipartite graph G: (i) G is a co graph; (ii) G is a partial cube; (iii) All semicubes of G are convex; (iv) Relation 0 is transitive. Equivalence between (i) and (ii) was observed by Klavzar,21 equivalence between (ii) and (iii) is due to Djo-kovic ,22 while the equivalence between (ii) and (iv) was proved by Winkler.23 Let us return to arbitrary (that is, not necessary bipartite) connected graphs. Let e = uv and f = xy be two edges of a connected graph G. Then Djokovic22 defined relation ~ on E(G) by setting e ~ f iff joins a vertex in W' with a vertex in Wyx. For more information on the relation ~ see refs.24,25 LEMMA 1. In any connected graph, co = ~. Proof. Let e = uv and f = xy be edges of a connected graph G. Suppose first e co f, that is, d(v,x) = d(v,y) + 1 = d(u,x) + 1 = d(u,y). Since d(x,u) < d(x,v), x e Wvu and since d(y,v) < d(y,v), y e Wvu. Thus, e ~ f. Suppose e ~ f, with x e Wvu and y e Wvu. Then d(v,x) = d(v,u) + d(u,x) = d(u,x) + 1 and d(u,y) = d(u,v) + d(v,y) = 1 + d(v,y). Since d(u,x) = d(v,y) we conclude that e co f. Q.E.D. In general ~ c 0 and in bipartite graphs ~ = 0. Hence the above discussion can be briefly summarized as follows: PROPOSITION 1. Let G be a connected graph; then co = ~. If G is also bipartite, then co = ~ = 0. 3. Four Counting Polynomials Relation co is a particular case of the edge equidi-stance (eqd) relation. The equidistance of two edges e = uv and f = xy in a connected graph G is described in part by relation (1), (accounting for topologically parallel edges), to which the condition for topologically perpendicular edges (in tetrahedron and its extensions) must be added: Notice that Ashrafi defined the equidistance of edges by considering the distance from a vertex z to an edge e = uv as the minimum distance between the given point and the two endpoints of that edge:26,27 d(z,e) = min{d(z,u),d(z,v)}. Then, the edges e = uv and f = xy are equidistant if d(x,e) n d(y,e) and d{uj) = d{vj) (3) In tetrahedron and its extensions, relation (3) is still true but in general it is not. Recall that a graph is planar if it allows an embedding into the plane such that no two edges cross. A planar graph together with its fixed embedding into the plane is called a plane graph. In chemistry, not only the structure of a chemical graph but also its geometry is important. Most of the chemical graphs are by their nature planar (and most often also equipped with an embedding into the plane). Moreover, the natural embeddings of these graphs are such that all the inner faces are isometric cycles which we will assume in the following. Hence the following definitions are relevant in this context. We say that 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 the assumption that faces are isometric. Notice that the relation co is defined in the whole graph while op is defined only in faces. We mention that John et al.19,28 implicitly used the "op" relation in defining the Cluj-Ilmenau index CI (see below). Using the relation op we can partition the edge set of G into opposite edge strips (ops) for short, as follows. 1. Any two subsequent edges of an ops are in op relation. 2. Any three subsequent edges of such a strip belong to adjacent faces. 3. An ops starts/ends in either (i) one even face/ring or (ii) two odd faces/rings; in case (i), the ops is a cycle while in case (ii) it is a path. In case of open structures, the open (or infinite) faces are equivalent to the odd faces. There are cases in which the two odd faces/rings superimpose and ops is a pseudo cycle, because the op relation is lastly violated.29,30 The ops is taken as maximum possible, irrespective of the starting edge. The choice is about the maximum size of face/ring, and mode of face/ring counting, which will decide the length of the strip. Let G be an arbitrary connected graph and s1,s2,...,sk be the op-strips of G. Then ops form a partition of E(G) and the Q-polynomial31 of G is defined as (4) Let now the set of edges codistant to edge e of G be C(e). A ©-polynomial32 of G, counting the edges equidistant to the all reference edges e, is written as ®(G,x)=y *ici v ' ' ¿—¡eS£(G) Suppose now G is a co-graph; then k O ,iM Ssi+Xisjdsi-i) V '=1 .1=1 H£(G)|2 -¿(|sy|)2=n'(G,i)=n(G) (18) Only in bipartite co-graphs, n(G) equals the value of PI (Padmakar-Ivan) index,36 proposed by Khadikar to account for the sum of non-equidistant edges in G. In ge- neral, CI(G) ï n(G) ï PI(G), because the edge equidistance eqd relation includes, besides the parallel edges condition (co and op relations), also the condition for perpendicular edges (tetrahedron condition). From the above relations (9), (10) and (18), one can reformulate (11) as M (19) = {[n'(G,l)f-0'(G,l)} Relation ( 19) is just the formula proposed by John et al.28 to calculate the Khadikar's PI index. 4. Examples (a) There exist plane bipartite graphs, which are co-graphs and for which CI(G) = n(G). It is the case of ace-nes and phenacenes, which are polyhex molecular structures. For these classes of structures, analytical formulas were presented in ref.32 Formulas for other classes of polyhex plane graphs, such as phenylenes, spiranes, pyre-nes and coronenes were given in ref.37 (b) There exist planar 3D bipartite graphs, which are non co-graphs and for which CI(G) ï n(G). An example is the cage in Figure 1a: the red edges are non-equidistant to each other although they both belong to the same ops. Conversely, the pcu cubic lattice in Figure 1b is precisely a partial cube (also a co-graph) and their ops represent orthogonal cuts oc; thus CI(G) = n(G) (shaded values). To the list of non co-graphs which are 3D bipartite graphs, we add the toroidal lattices of even faces. Only exceptional tori show CI(G) = n(G) values (Table 1). The tori of entries 1 and 2 of Table 1 are 3D bipartite graphs and show CI(G) = n(G) values, although they do not follow the relations (6) and (7) for n(G,x) and 0(G,x).38 The structure in entry 3 is a non-bipartite graph32 as the whole; however, it represents a union of three strips, each of them being a bipartite, co-graph (Figure 2). As a consequence, the relations (6) and (7) are obeyed. Note that, in Ref.37 n(G,x) was denoted by NQ(G,x). The polynomial calculations were done by the software programs developed at TOPO Group Cluj: Omega Counter39 and Nano Studio.40 (c) In tree graphs, Omega polynomial simply counts the non-equidistant edges as self-equidistant ones, being included in the term of exponent s = 1. In such graphs, CI(G) = n(G) = (v - 1)(v - 2) (a result known from Kha-dikar41) and the Omega and Theta polynomials show the same expression. (d) Finally, there are graphs with a single ops, which is precisely a cycle (called a Hamiltonian ops in ref.29). b) n(G,x) = 6x9; CI = 2430 ; (Rnia\[4|) 0(G,a-) = 54X9; 0(G) = 486 n(G,*) = 54/5 ; n{G)g 2430 Sd(G,x) = 6.X'54-'1 = 6.v45 ; Sd(G) = 270 Figure 1. 3D bipartite graphs; (a) non-co-graph and (b)co-graph (gray marked CI(G) = n(G) values) Table 1. Polynomials in toroidal structures, for which CI(G) = n(G). Torus a(G,x) CI n(G,x) n(G) 0(G,x) 1 TH(6,3)[8,12] 12x4 + 4x24 18240 96x122 + 48x136 18240 48x8 + 96x22 2 TH((4,8)3)[20,8] 10x8 + 8x10 + 2x40 52960 80x218 + 80x220 + 80x224 52960 80x16 + 80x20 + 80x22 3 TWV3(4,4)[6,10] 10x6 + 3x20 12840 60x100 + 60x114 12840 60x6 + 60x20 Figure 2. Twisted torus TWV3[6,10](4,4); non-bipartite (a); union of 3 co-graphs, one of them is shown, alternating white-red colors (b). For such graphs, one calculates: Q(G,x) = 1x; CI(G) = s2 -(s + s(s - 1)) = 0. An example is given in Figure 3. Q{G,x) = *2" (all rings) Ci'(G,l) = e-2n Q'(G, 1) = 2n(2n -1) Cf(G) = 0 e(G,x) = 2nx" 0'(G,1) = 0(G) = 2n2 U{G,x) = 2nxi-" =2nx2"'" =2 nx" n'(G,!) = n(G) = 2«2 Sci{G,x) = xe-2" =x1-2" = 1 Sd(G) = 0 Ex. For «=5, CI, ©, II, Sd: 0; 50; 50; 0. Figure 3. A complete bipartite graph K2n; n = 8; non-co-graph; Ha-miltonian ops 5. One More Question It is natural to ask whether there is a simple criterion/condition to be used in order to decide if a given bipartite graph is a co-graph (or a partial cube). More precisely, one would like to have a criterion that can be applied fast either by hand or by computer. Unfortunately, no such condition is known and, in fact, such a condition would be a big breakthrough in the area of metric graph theory. In the papers,42'43 two algorithms of the complexity O(mn) for recognizing co-graphs have been developed, where n is the order and m the size of a given graph. (Note that in a co graph, m = O(n log n).) Recently Eppstein,44 using some sophisticated computational tricks, reduced the complexity to O(n2) thus removing the factor log n. In some special cases the complexity can be further reduced, see ref.45 but in general a (close to) linear criterion does not seem realistic. *** Omega polynomial found application in the topolo-gical description of complex nanostructures showing polyhedral covering.46-48 In tubular/toroidal structures this polynomial accounts for the spirality and ring distribu-tion.49-51 The coefficient of the first power term, called np has found to have good ability in predicting the heat of formation and strain energy in small fullerenes or the resonance energy in planar benzenoids.37,38 6. Conclusions. Omega polynomial was designed to count the opposite topologically parallel edges in graphs, particularly to describe the polyhedral nanostructures. In four years, 43 papers have been published or sent for publication by TOPO Group Cluj and further papers by other scientists, Omega polynomial already getting a scientific success. In this paper, the main definitions were re-analyzed and clear relations with other three related polynomials were established. These relations were supported by close formulas and appropriate examples. 7. References 1. H. Hosoya, Bull. Chem. Soc. Japan, 1971, 44, 2332-2339. 2. H. Hosoya, Discrete Appl. Math., 1988, 19, 239-257. 3. E. V. Konstantinova, M. V. Diudea, Croat. Chem. Acta, 2000, 75, 383-403. 4. I. Gutman, S. Klavžar, M. Petkovšek, P. Žigert, MATCH Commun. Math. Chem., 2001, 43 49-66. 5. H. Hosoya, T. Yamaguchi, Tetrahedron Lett., 1975, 52, 4659-4662. 6. H. Hosoya, Topics Curr. Chem., 1990, 153, 255-272. 7. I. Gutman, H. Hosoya, Z Naturforsch., 1990, 45a, 645-648. 8. I. Gutman, Rev. Roum. Chim., 1991, 36, 379-388. 9. D. Stevanovic, Graph Theory Notes, New York, 1998, 34, 31-36. 10. A. Motoyama, H. King. Hosoya, J. Math. Phys, 1977, 18, 1485-1490. 11. E. J. Farrell, C. De Matas, Int. J. Math. Math. Sci., 1988, 11, 87-94. 12. C. Hoede, X. L. Li, Discr. Math., 1994, 125, 219-228. 13. M. V. Diudea, I. Gutman, L. Jäntschi, Molecular Topology, NOVA, New York, 2002. 14. M. V. Diudea, J. Chem. Inf. Comput. Sci., 1994, 34, 10641071. 15. M. V. Diudea, O. Ursu, Indian J. Chem., 2003, 42A, 12831294. 16. M. V. Diudea, MATCH Commun. Math. Comput. Chem., 2002, 45, 109-122. 17. M. Stefu, M. V. Diudea, in: Diudea, M. V. (Ed.), Nanostruc-tures, Novel Architecture, NOVA, New York, 2005, 127-165. 18. O. Ursu, M. V. Diudea, TOPOCLUJ software program, Ba-bes-Bolyai University, Cluj, 2005; Available, on line at http://chem.ubbcluj.ro/~diudea. 19. P. E. John, A. E. Vizitiu, S. Cigher, M. V. Diudea, MATCH Commun. Math. Comput. Chem., 2007, 57, 479-484. 20. F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969. 21. S. Klavžar, MATCH Commun. Math. Comput. Chem., 2008, 59, 217-222. 22. D. Ž. Djokovic, J. Combin. Theory Ser. B, 1973, 14, 263267. 23. P.M. Winkler, Discrete Appl. Math., 1984, 8, 209-212. 24. E. Wilkeit, J. Combin. Theory Ser. B, 1990, 50, 179-197. 25. B. Brešar, Discrete Math., 2001, 237, 13-27. 26. A. R. Ashrafi, B. Manoochehrian, H. Yousefi-Azari, Util. Math, 2006, 71, 97-108. 27. A. R., Ashrafi, M. Jalali, M. Ghorbani, M. V. Diudea, MATCH Commun. Math. Comput. Chem., 2008, 60, 905-916. 28. P. E. John, P. V. Khadikar, J. Singh, J. Math. Chem., 2007, 42, 37-45. 29. M. V. Diudea, A. Ilic, Carpath. J. Math. 2009, 25 (2) 177-185. 30. Diudea, M. V., Nagy, K., Nagy, L. Cs., Ilic, A., MATCH Commun. Math. Comput. Chem. 2011, 65(1), 000-000. 31. M. V. Diudea, Carpath. J. Math., 2006, 22, 43-47. 32. M. V. Diudea, S. Cigher, P. E. John, MATCH Commun. Math. Comput. Chem., 2008, 60, 237-250. 33. A. R., Ashrafi, M. Ghorbani, M. Jalali, Indian J. Chem., 2008, 47A, 535-537. 34. P. V. Khadikar, V. K. Agrawal, S. Karmarkar, Bioorg. Med. Chem , 2002, 10, 3499-3507. 35. M. V. Diudea, A. E. Vizitiu, M. Mirzargar, A. R. Ashrafi, Carpath. J. Math., (accepted). 36. P. V. Khadikar, Nat. Acad. Sci. Lett, 2000, 23, 113-118. 37. M. V. Diudea, A. E. Vizitiu, D. Janežic, J. Chem. Inf. Model., 2007, 47, 864-874. 38. M. V. Diudea, S. Cigher, A. E. Vizitiu, M. S. Florescu, P. E. John, J. Math. Chem., 2009, 45, 316-329. 39. S. Cigher, M. V. Diudea, Omega polynomial counter, "Ba-bes-Bolyai" Univ., 2007. 40. Cs. L. Nagy, M. V. Diudea, Nano Studio software, "Babes-Bolyai" Univ., 2009. 41. M. V. Diudea, M. S. Florescu, P. V. Khadikar, Molecular Topology and Its Applications, EFICON, Bucharest, 2006. 42. F. Aurenhammer, J. Hagauer, Math. Systems Theory, 1995, 28, 387-396. 43. W. Imrich, S. Klavžar, Bull. Inst. Comb. Appl., 1993, 9, 4556. 44. D. Eppstein, Recognizing partial cubes in quadratic time, 19th ACM-SIAM Symp. Discrete Algorithms, San Francisco, 2008, 1258-1266. 45. B. Brešar, W. Imrich, S. Klavžar, Discrete Appl. Math., 2003, 131, 51-61. 46. M. V. Diudea, S. Cigher, A. E. Vizitiu, O. Ursu, , P. E. John, Croat. Chem. Acta, 2006, 79, 445-448. 47. A. E. Vizitiu, S. Cigher, M. V. Diudea, M. S. Florescu, MATCH Commun. Math. Comput. Chem., 2007, 57, 457462. 48. A. E. Vizitiu, M. V. Diudea, MATCH Commun. Math. Com-put. Chem, 2008, 60, 927-933. 49. M. V. Diudea, J. Math. Chem, 2009, 45, 309-315. 50. M. V. Diudea, A. E. Vizitiu, F.Gholaminezhad, A. R., Ashrafi, MATCH Commun. Math. Comput. Chem., 2008, 60, 945953. 51. M. V. Diudea, MATCH Commun. Math. Comput. Chem., 2008, 60, 935-944. Povzetek Omega polinom je predlagal Diudea (ref.: Omega Polynomial, Carpath. J. Math., 22 43-47) za štetje nasprotnih topo-loško vzporednih povezav v grafih, še posebej za opis poliedričnih nanostruktur. V tem članku so ponovno analizirane glavne definicije in vzpostavljene jasne povezave z ostalimi tremi sorodnimi polinomi. Te povezave so podprte z izpeljanimi formulami in ustreznimi primeri.