ࡱ> %'$q  bjbjt+t+ )6AAW]8 j\6 ^: : : : : : $i: : : : : ": : 6 """: : : : ""6:,: " @-OL COMPLEXITY OF MOLECULES Sonja Nikoli and Nenad Trinajsti The Rugjer Boakovi Institue, PP 180, 10002 Zagreb, Croatia  HYPERLINK mailto:sonja@irb.hr; sonja@irb.hr;  HYPERLINK mailto:trina@irb.hr trina@irb.hr We studied complexity of several classes of molecular graphs [1]: linear and branch trees, (poly)cycles and general graphs. Trees and (poly)cycles are simple graphs that are graphs without multiple edges and loops. General graphs are graphs with multiple edges and loops. A loop is an edge with both of its vertices identical. We used trees [2] to represent alkanes, cycles to represent cycloalkanes, various polycyclic graphs to represent cage-structures and general graphs to represent heterosystems. We employed in our study the following complexity indices: Bonchev's indices [3], Zagreb complexity indices [4], spanning trees [2] and total walk counts [5]. We considered the following structural features: a graph (molecule) size in terms of number of vertices and edges, branching, cyclicity, the number of loops and multiple edges and symmetry. Bonchev proposed the topological complexity index TC to account for a complexity of the molecular graphs [3]:  EMBED Equation.3  (1) The first sum in the formula is over all connected subgraphs of a graph G, the second sum is over all vertices in the subgraph s and di is the vertex degree. The vertex degrees in subgraphs are taken as they are in G. If the vertex degrees are taken as they are in the respective isolated subgraphs s, than we have another Bonchev's complexity index denoted by TC1. Zagreb complexity indices TM1, TM1*, TM2, TM2* are based on the original Zagreb indices M1 and M2 and the above Bonchev's idea of using subgraphs. M1 and M2 indices are defined as:  EMBED Equation.3  (2)  EMBED Equation.3  (3) TM1 and TM2 are defined as:  EMBED Equation.3  (4)  EMBED Equation.3  (5) Vertex degrees entering TM1 and TM2 for a given subgraph s are taken as in a graph G. If vertex degrees are used as appearing in a subgraph s, than above formulas give TM1* and TM2* indices. A spanning tree of a graph G, t(G), is a connected acyclic subgraph containing all vertices in G. In the case of trees (alkanes), the spanning tree is identical to the tree itself: t(tree)=1 (6) In the case of monocycles (cycloalkanes) the number of spanning trees is equal to the cycle size: t(cycle)=V (7) where V is the number of the vertices in the cycle. There are a number of methods available to compute the number of spanning trees [8]. The total walk count twc is given as a sum of the molecular walk count mwc [5-7]:  EMBED Equation.3  (8) A walk in a (molecular) graph is an alternating sequence of vertices and edges. The length of the walk is the number of edges in it. The molecular walk count of length ! mwc! is given as a sum of all atomic walks of length !  EMBED Equation.3  (9) where awc!(i) is the atomic walk count of length ! of atom i. Formulas (8) and (9) apply equally to simple and general graphs [9]. Our analysis shows: (i) all considered indices increased with the size and branching of alkanes; (ii) all considered indices also increase with the size of the cycloalkanes (note that M1=M2 in the case of monocycles); (3) general graphs were studied only by twc. We found that increase in the number of loops and multiple edges considerable increases the value of twc; (4) the increase in symmetry lowers the values of considered indices (twc index is not considered because it is symmetry independent). Additionally it should be emphasize that TC, TC1, TM1, TM1*, TM2, and TM2* indices depend on knowledge of all connected subgraphs. The number of subgraphs often enormously increases with the graph size. M1 and M2 are highly degenerate indices, so they cannot discriminate between many isomers. Spanning trees are useless in the case of acyclic structures. So our final conclusion is that all of the considered indices are useful to study some aspects of molecular complexity but we cannot say for any of them to be the best complexity index to use. References Trinajsti N., Chemical Graph Theory, 2nd revised edn. CRC Press, Boca Raton, FL, 1992. Harary F., Graph Theory, second printing. Addison-Wesley, Reading, MA, 1972. Bonchev D., Novel indices for the topological complexity of molecules. SAR&QSAR Environ. Res. 7 (1997) pp. 23-43. Nikoli S., Trinajsti N., Toli I.M., Rcker G. and Rcker C., On molecular complexity indices. In: Complexity in chemistry, Introduction and fundamentals; Bonchev D. and Rouvray D.H., (eds.); Mathematical chemistry series, Taylor&Francis, London, 2003. Rcker G. and Rcker C., Counts of all walks as atomic and molecular descriptors. J. Chem. Inf. Comput. Sci. 33 (1993) pp. 683-695. Rcker G. and Rcker C., Walk counts, labyrinthicity and complexity of acyclic and cyclic graphs and molecules. J. Chem. Inf. Comput. Sci. 40 (2000) pp. 99-106. Rcker G. and Rcker C., On topological indices, boiling points and cycloalkanes. J. Chem. Inf. Comput. Sci. 39 (1999) pp. 788-802. Nikoli S., Trinajsti N., Juri A., Mihali Z. and Krilov G., Complexity of some interesting (chemical) graphs. Croat. Chem. Acta 69 (1996) pp. 883-897. Lukovits I., Mili evi A., Nikoli S. and Trinajsti N., On walk counts and complexity of general graphs. Internet Electron. J. Mol. Des. 2002, 1(8), pp. 388-400; http://www.biochempress.com  FILENAME \* MERGEFORMAT Sonja abs templ submitted to World Scientific :  DATE 04/16/03 :  TIME 9:32 PM  PAGE 4/ NUMPAGES \* MERGEFORMAT 1 2LVvxz468RTXZ 67%'XZrt K L Q R V W X \ ] a b c    ! jCJEHUjŰ.B UVmHCJH*CJH*jrCJEHUj.B UVmH jCJUjU0J jU jU;CJD02xz4 4 . / K L l m !$$$$$ & F$$ & F02xz4 4 . / K L l m L xyjk`bdz|,.V W s x y | } ľ                         "! E! " # $ 1 2 9 : L M ` a b c m n 7 8 9 @ A B jklhjrt 0޴޴⬣⊁jCJEHUjļCw6pڂc7$ ,@! ~ Ay ]T g*K-LN-b`ZR Žxty;'>;0I34޹il4=Ĥ\Y\ f@%DdB  S A? 2ak "[k `!cak "[(` :1xcdd``ad``beV dX,XĐ )y A?dmvqfĒʂT`;a& Ma`ٯ F\?eX@JB5ïp ` o&HXC2sSRsa.63UZTZ1 i6AFPpi7+b"aLɲ3k"y}sCmGk}.czČZ~h,lE= H$MtpVbpGq}/ϗ~&Y׍ }JBZv\:;ZfIE:m<_iMϏzGyiVDd0B  S A? 2,&|gCJé `!,&|gCJé kbxRJAsC- b#66Frh3HrvV>E>̹3 ZeoE?C !J)clDvSv2EՖi}lIMgPZr,hs9&c.Nn%E7'2ecNQAo՘)i0JZv}/p緯A Lv,9~4wr|TŻCsIe'S2q'uμ:Н"{⦛⺺5n.?7o/33:ǽD/=+1%pҜ6CV?=?V BihFDdB  S A? 22ǂ~ `!2ǂ~ @`RxڅRJP=&զB8 u8g+6PuG?_pSp(uqNb}7ք{rX.>ټH)(JD*,*)Þo]jȧy,!"tk^-NfG0?%ε_jny_+<Г)F%uJdguM{tOz :fa8#IRJ]Y7wǓOu1=9v.VQfDXpڭ{'q.KޖΧ` "k0+VOP-7N-kHNDdlB  S A? 2[zn$tKuU1iz! `![zn$tKuU1iz @XhZxcdd``Ncd``beV dX,XĐ  !"#6&)*+-,./021354789:<=>?@ABCDEFGHRoot Entry( F^UO(@Data +WordDocument')6ObjectPool* 1OUO_1110355693F1O1OOle CompObjfObjInfo  #&),-/012345789:;<=>?@ABD FMicrosoft Equation 3.0 DS Equation Equation.39qQ|kIxvI TC=d i s() verices " s "Equation Native _1110356165 F1O1OOle CompObj f FMicrosoft Equation 3.0 DS Equation Equation.39qQ\kIxvI M 1 =d i2vertex " FMicrosoft Equation 3.0 DS Equation Equation.39qObjInfo Equation Native  x_1110356232F1O1OOle  CompObjfObjInfoEquation Native t_1110356392F`OOQXIlI M=d i d jedges " FMicrosoft Equation 3.0 DS Equation Equation.39qQ}II TM 1 =Ole CompObjfObjInfoEquation Native d i2 s() verices " s " FMicrosoft Equation 3.0 DS Equation Equation.39qQ IlI TM 2 = s " d i d je_1110356492FOOOle CompObjfObjInfoEquation Native _1110666118"F@O@OOle !CompObj "fdges " s() FMicrosoft Equation 3.0 DS Equation Equation.39qa`mIyI twc= mwc !!=1V-1 "ObjInfo!$Equation Native %|_1111229425$F@O@OOle 'CompObj#%(fObjInfo&*Equation Native +1Table; FMicrosoft Equation 3.0 DS Equation Equation.39qtII mwc ! = awc ! (i) i=1V " Oh+'0 $< T Ɂ A?dm zjx|K2B* RUf: P 27)? d.PHqd f)y է>F?g o P Lf,3d++&104bw/`]PP\&9n?F&\D$X *@*r*4~׊D\ai'Hqo sAS8=v0o(}cdbR ,.Iex7f:ʱiSummaryInformation().DocumentSummaryInformation86 CompObjCj` |   >Introducing Complete Graphs in Molecular Connectivity StudiescntrSonja Nikolicmponjonjws-p9-75x6-50mpSonja Nikolicmp4njMicrosoft Word 8.0e@@@ƌ @JN ՜.+,D՜.+,L px  .World Scientific PublishingJ% 1 >Introducing Complete Graphs in Molecular Connectivity Studies Title|(RZ _PID_GUID _PID_HLINKSAN{F4C08C02-69DC-11D7-9E6F-525405F92FEE}A J}mailto:trina@irb.hr!Fmailto:sonja@irb.hr;  FMicrosoft Word Document MSWordDocWord.Document.89q# [$@$NormalmH N@N Heading 1!$$ & F*$h@&5KHD@D Heading 2$ & Fhhx@&6FF Heading 3!$$ & F*$hx@&<< Heading 4$ & F<@&88 Heading 5 & F<@&@@ Heading 6 & F<@&6CJ88 Heading 7 & F<@&<< Heading 8 & F<@&6< < Heading 9 & F<@&CJ<A@<Default Paragraph Font"O"spara$ O Parah@>"@Title$$$$*$ 5;KH424Author$$$*$;CJ>B> Affiliation $<6CJ44Abstract $hhCJ2R2 Normal Indent1b List Numberk$ & Fh>Th.:r List Number 2h & F>Th)0 List Bulleth & Fh>Th6 List Bullet 2h & F>Th2D2 List Continueh2"2Caption $xxCJzazbibitemY>T:h. @@ NonumHead-1$h*$5, ,Footer  !,,Header  !(U@( Hyperlink>*B*2B@2 Body Text!$CJmH 2P@"2 Body Text 2"$CJ6! 0  ,  y !#L`bmk  n XX:::::::+MT]ahpry{} !AGHPQYio<@gkFMcoy)/5<;CJLy5;~1 = - 0 _ b 6 9 ( ) k r    [b>HpsU\akpuvz|  6DTZbh &V\^ay ")17{W@Gkr#km  y z  # 0 W Sonja Nikolic/E:\ICCMSE_03_Grcka\Abstracs\Basak abs templ.doc Sonja Nikolic/E:\ICCMSE_03_Grcka\Abstracs\Basak abs templ.doc Sonja Nikolic/E:\ICCMSE_03_Grcka\Abstracs\Basak abs templ.doc Sonja Nikolic8C:\WINDOWS\TEMP\AutoRecovery save of Basak abs templ.asd Sonja Nikolic/E:\ICCMSE_03_Grcka\Abstracs\Sonja abs templ.doc Sonja Nikolic8C:\WINDOWS\TEMP\AutoRecovery save of Sonja abs templ.asd Sonja Nikolic8C:\WINDOWS\TEMP\AutoRecovery save of Sonja abs templ.asd Sonja Nikolic/E:\ICCMSE_03_Grcka\Abstracs\Sonja abs templ.doc Sonja Nikolic/E:\ICCMSE_03_Grcka\Abstracs\Sonja abs templ.doc Sonja Nikolic/E:\ICCMSE_03_Grcka\Abstracs\Sonja abs templ.doc N9:0c@hh@.@x..@...@  ....@  .....@  ......@ .......@ ........0^`0o(.N9:@<<<<<d PP @PP$@PPPP@@G:Times New Roman5Symbol3& :Arial5& :Tahoma;"Helvetica3Times"qhEtFatf %20rV!C:\WINDOWS\TEMP\ws-p9-75x6-50.dot=Introducing Complete Graphs in Molecular Connectivity Studies Sonja Nikolic Sonja Nikolic