Warning: include(/home/www/data/lejpthead.php): failed to open stream: No such file or directory in /home/www/data/lejpt/gettext.php on line 4

Warning: include(): Failed opening '/home/www/data/lejpthead.php' for inclusion (include_path='.:/usr/pkg/lib/php') in /home/www/data/lejpt/gettext.php on line 4
LEJPT - Leonardo Electronic Journal of Practices and Technologies - light html archive A01
Warning: include(/home/www/data/lejptbody.php): failed to open stream: No such file or directory in /home/www/data/lejpt/gettext.php on line 6

Warning: include(): Failed opening '/home/www/data/lejptbody.php' for inclusion (include_path='.:/usr/pkg/lib/php') in /home/www/data/lejpt/gettext.php on line 6
Leonardo Electronic Journal of Practices and Technologies
Issue 01, p. 01-18
Topological Substituent Descriptors
Mircea V. DIUDEA1*, Lorentz JNTSCHI2, Ljupčo PEJOV3
1"Babeş-Bolyai" University Cluj-Napoca, Romania
2 Technical University Cluj-Napoca, Romania
3"Sv. Kiril i Metodij" University Skopje, Macedonia
*corresponding author, diudea@chem.ubbcluj.ro

Abstract
Motivation. Substituted 1,3,5-triazines are known as useful herbicidal substances. In view of reducing the cost of biological screening, computational methods are carried out for evaluating the biological activity of organic compounds. Often a class of bioactives differs only in the substituent attached to a basic skeleton. In such cases substituent descriptors will give the same prospecting results as in case of using the whole molecule description, but with significantly reduced computational time. Such descriptors are useful in describing steric effects involved in chemical reactions.
Method. Molecular topology is the method used for substituent description and multi linear regression analysis as a statistical tool.
Results. Novel topological descriptors, XLDS and Ws, based on the layer matrix of distance sums and walks in molecular graphs, respectively, are proposed for describing the topology of substituents linked on a chemical skeleton. They are tested for modeling the esterification reaction in the class of benzoic acids and herbicidal activity of 2-difluoromethylthio-4,6-bis(monoalkylamino)-1,3,5-triazines.
Conclusions. Ws substituent descriptor, based on walks in graph, satisfactorily describes the steric effect of alkyl substituents behaving in esterification reaction, with good correlations to the Taft and Charton steric parameters, respectively. Modeling the herbicidal activity of the seo of 1,3,5-triazines exceeded the models reported in literature, so far.
Keywords
Steric effect, Substituent descriptors, Molecular topology, Herbicidal activity. Abbreviations and notations MLR, multi linear regression; SVTI, substituent volume topological index; Es, Tafts steric parameter; n, Chartons steric parameter.

1. Introduction
In the field of chemical reactivity, the first proposal of a substituent steric parameter is due to Taft [1, 2]. He tried to quantify the steric influence of a substituent located on the hydrocarbon part of organic esters in the acid-catalysed hydrolysis of aliphatic carboxylic esters, RCOOR. His Es steric parameter is defined as:
(1)
where is the ratio of acid-catalysed hydrolysis rate constant of RCOOR to that of MeCOOR. By definition, .
The Es parameter has been defined empirically [3]. Taft himself pointed out that Es varies parallel to the atom group radius. Charton also found that Es is linearly dependent on the van der Waals radius of the substituent, thus defining a new steric parameter, n [4-8]. Murray [9] found correlations between the Taft parameter and the Randić [10] topological index, for a series of substituted alkyls. In this respect, Ivanciuc and Balaban [3] have proposed a topological descriptor, SVTI, which encodes the topological distances (i.e., the number of bonds/edges, Dij, joining the atoms/vertices i and j on the shortest path) in a molecular graph, G. It is defined on the fragment F (i.e. an alkyl group) attached to the vertex i of G, as:
(2)
The summation runs over all NF vertices of F and the distance Dij is limited to 3, in agreement to the Chartons conclusion about the limit of the influence of the steric effect beyond the gamma carbon [5-8]. The calculation of SVTI is exemplified for the sec-butyl group (R = H) or higher homologues (R H):
SVTI (s-Bu) = 1+ 2 + 2 + 3 = 8
The above authors have tested their descriptors in describing the reaction rates of acid-catalysed hydrolysis of RCOOR' (the Taft's set). In the present work, two novel descriptors for substituents are proposed. They are now tested in modeling the effector-receptor interaction in the herbicidal activity of 2-difluoromethylthio-4,6-bis(monoalkylamino)-1,3,5-triazines.

2. Substituent Topological Descriptors, XLDS and Ws
The substituent descriptors XLDS and Ws herein proposed are constructed with the aid of layer matrices. Before defining our descriptors, lets recall some knowledges about the layer matrices [11-17]. A partition G(i) with respect to the vertex i, in a graph, is defined [11, 14, 15] as:
(3)
where Diu is the topological distance (see above) and ecci is the eccentricity of i (i.e. the largest distance between i and any vertex in G). Figure 1 illustrates the relative partitions for the graph G1. Let be the layer j of the vertices u located at distance j, in the relative partition G(i): (4) The entries in a layer matrix, LM, collect the topological property Pu for all vertices u belonging to the layer :
(5)
G1 G1(1,5) G1(2) G1(3) G1(4)
G1(1) = {{1},{2},{3,5},{4}}; G1(2) = {{2},{1,3,5},{4}}; G1(3) = {{3},{2,4},{1,5}}; G1(4) = {{4},{3},{2},{1,5}}; G1(5) = {{5},{2},{1,3},{4}}. Figure 1. Partitions of G1 with respect to each of its vertices
The matrix LM can be written as:
(6) LM(G)=
where V(G) is the set of vertices in graph and d(G) is the diameter (i.e., the largest distance) of G. The dimensions of such a matrix are N (d(G)+1). Figure 2 illustrates the layer matrix of distance sums, LDS [13], the topological property M which collects being the sum of distances joining a vertex i with all the remainder vertices in G. Note that the first column contains just the vertex topological property. (in this case, , marked in the weighted graph, G2{DSi}).

G2
i\j:01234
(1)1510242617
(2)103926170
(3)9364700
(4)122624300
(5)171292430
(6)1510242617
(7)14922470
LDS(G2)
Figure 2. Matrix LDS for the graph G2
This matrix and the invariants calculated on (e.g., the well-known Wiener index [18], counting all distances in G) are useful tools in topological description of molecular graphs [13, 14]. Another interesting matrix is the layer matrix of walk degrees [15], LeW. A walk, W, is defined [19] as a continuous sequence of vertices, v1, v2, ..., vm; it is allowed edges and vertices to be revisited. If the two terminal vertices coincide (v1 = vm ), the walk is called a closed (or self returning) walk, otherwise it is an open walk. If its vertices are distinct, the walk is called a path. The number e of edges traversed is called the length of walk. Walks of length e, starting at the vertex i, eW(i), can be counted by summing the entries in the row i of the eth power of the adjacency matrix A (whose nondiagonal entries are 1 if two atoms are adjacent and zero otherwise):
(7)
where eW(i) is called the walk degree (of rank e) of vertex i (or atomic walk count [15, 20] ). Walk degrees, eW(i), can be also calculated by summing the first neighbours degrees of lower rank, according to an additive algorithm11 illustrated in figures 3 and 4. Local and global invariants based on walks in graph were considered for correlating with physico-chemical properties [15, 20]. Figure 3 illustrates the layer matrix of walk degrees, LeW, e = 1-4, for G2. Note that the first column in L1W is just the vertex degree or the vertex valency. Note that the matrix LeW was re-invented by Randic in 2001, for e = 1, under the name "valence shells" [21]. The substituent descriptor XLDS is the local "centrocomplexity index", XLM [14], defined on the LDS matrix:
(8)
where i is the attachment point of the substituent to a given chemical structure (see figure 4) and z denotes the number of bits of max[LDS]ij in G. Calculation of XLDS is exemplified in figure 4.
G2 {1Wi } G2 {2Wi } G2 {3Wi} G2 {4Wi }
L1W L2W L3W L4W
i\j 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4
1 1 3 4 3 1 3 5 9 7 2 5 12 17 14 4 12 22 38 28 8
2 3 5 3 1 0 5 12 7 2 0 12 22 14 4 0 22 50 28 8 0
3 3 6 3 0 0 6 12 8 0 0 12 26 14 0 0 26 50 32 0 0
4 2 4 4 2 0 4 8 8 6 2 8 16 18 10 0 16 34 34 24 0
5 1 2 3 4 2 2 4 6 8 6 4 8 12 18 10 8 16 26 34 24
6 1 3 4 3 1 3 5 9 7 2 5 12 17 14 4 12 22 38 28 8
7 1 3 5 3 0 3 6 9 8 0 6 12 20 14 0 12 26 38 32 0
Figure 3. Layer matrix of walk degrees, LeW for the graph G2 (calculated by summing the first neighbor degrees of lower rank)
{1W} {2W} {3W} {DS} (a)
Ws (i) = 7+7/2+11/3+8/4 ≈ 16.167;
XLDS(i) = 14∙100+10∙10-2+8∙10-4+8∙10-6+12∙10-8+12∙10-10 = 14.1008081212 ≈ 14.101;
(b)
Figure 4. (a) Walk degrees, eW, (calculated by summing the first neighbors degrees of lower rank) and distance sums, DS; (b) Evaluation of Ws and XLDS descriptors
Ws is based on the walks in a connected molecular graph. It is calculated from the layer matrix L3W by:
(9)
where 3W is the walk number, of length 3. We limited here to elongation 3 by following the Chartons suggestion about the limit of the influence of steric effect (see above). The calculation of the parameter Ws is exemplified in figure 4. The XLDS descriptor is similar to the SVTI parameter, both of them counting distances in the substituent. Ws describes the branching in the vicinity of the attachment point i. All these parameters suggest the steric influence of a substituent in the interaction of the skeleton (or a situs of it) with a partner (e.g., a reactant [3, 22] or a biological receptor). They are free of electronic contributions, at least in the variant in which the heteroatom is not considered.

3. Correlating Test
The utility of the substituent descriptors, XLDS and Ws, was proven on a set of thirty aminoalkyl fragments (table 1) involved in the inhibition of Hill reaction of triazines [23] (figure 5). In this respect, the fragmental volumes, V, (in cm3/mol) for the considered substituents have been calculated as described below. Other parameter herein considered was the number of atoms different from hydrogen, N. All these descriptors have been calculated separately for the two sites, A and B (see figure 5).

Figure 5. Herbicidal bioactive triazines
Table 1. Topological descriptors and biological activity pI50 for the triazines in figure 5
NoABNANBWs,AWs,BXA*XBVA**VBpI50
1NH2NH211111.11.118.76318.7633.82
2NH2NHCH312151.13.2318.76332.6365.20
3NH2NHC2H51318.51.16.44618.76347.9085.34
4NH2NH-i-C3H714113.661.19.06118.76360.7665.83
5NHCH3NHCH322553.233.2332.63632.6366.01
6NHCH3NHC2H52358.53.236.44632.63647.9086.39
7NHCH3NHC3H724511.753.2310.07132.63662.3936.75
8NHCH3NH-i-C3H724513.663.239.06132.63660.7666.76
9NHCH3NHC4H925513.933.2315.11132.63676.6386.74
10NHCH3NH-s-C4H925515.163.2313.09132.63675.0396.76
11NHCH3NH-t-C4H925520.503.2312.08132.63674.1066.78
12NHCH3NHC5H1126515.623.2321.16132.63688.2417.12
13NHC2H5NHC2H5338.58.56.4466.44647.90847.9086.82
14NHC2H5NHC3H7348.511.756.44610.07147.90862.3936.74
15NHC2H5NH-i-C3H7348.513.666.4469.06147.90860.7666.89
16NHC2H5NHC4H9358.513.936.44615.11147.90876.6386.95
17NHC2H5NH-i-C4H9358.516.166.44614.10147.90874.4977.01
18NHC2H5NH-s-C4H9358.515.166.44613.09147.90875.0396.87
19NHC2H5NH-t-C4H9358.520.506.44612.08147.90874.1066.97
20NHC2H5NHC5H11368.515.626.44621.16147.90888.2416.94
21NHC2H5NHC6H13378.517.006.44628.22247.908102.0327.21
22NHC2H5NHC7H15388.518.176.44636.29247.908116.6727.01
23NHC2H5NHC8H17398.519.186.44645.37347.908128.7706.81
24NHC3H7NHC3H74411.7511.7510.07110.07162.39362.3936.45
25NH-i-C3H7NHC3H74413.6611.759.06110.07160.76662.3936.75
26NH-i-C3H7NH-i-C3H74413.6613.669.0619.06160.76660.7666.75
27NH-i-C3H7NHC4H94513.6613.939.06115.11160.76676.6386.71
28NH-i-C3H7NH-s-C4H94513.6615.169.06113.09160.76675.0396.88
29NH-i-C3H7NH-t-C4H94513.6620.509.06112.08160.76674.1066.70
30NH-i-C3H7NHC5H114613.6615.629.06121.16160.76688.2416.69
* The symbol X stands for XLDS (see text);
** Volume, [cm3/mol].
Table 2. Statistics of multivariable regression (distinct variables on branches A and B)
No.XIbiArsv(%)F
11/N,B-3.7867.5490.89870.3114.752117.587
21/Ws,B-3.3726.9330.82980.3966.04761.899
31/XB-3.8067.0380.88350.3335.07699.598
41/VB-72.2767.7600.89750.3134.779115.936
51/NA1/NB-1.234-2.6787.8100.95770.2083.175149.557
61/Ws,A1/Ws,B-1.335-2.0777.1180.96150.1993.030165.554
71/XA1/XB-1.317-2.5267.2520.96620.1862.844189.755
81/VA1/VB-22.999-52.5148.0480.94780.2313.519119.237
91/Ws,A1/VB-1.114-47.1947.6180.97140.1722.619226.162
101/Ws,A1/XB-1.180-2.4587.1590.97290.1672.550239.280
111/Ws,A1/NB-1.120-2.4847.4840.97460.1622.472255.491
12NA1/NA1/NB-0.385-2.777-2.4449.4770.98340.1342.039254.937
13Ws,A1/Ws,A1/Ws,B-0.025-1.594-2.0567.3720.96610.1902.903121.327
14XA1/XA1/XB-0.078-2.047-2.4137.8760.98180.1402.132232.401
15VA1/VA1/VB-0.036-65.998-45.36710.6490.98080.1442.193219.227
16XA1/VA1/VB-0.155-59.011-46.2449.7620.98150.1412.152228.039
17XA1/VA1/XB-0.154-60.818-2.3999.3370.98360.1332.029257.426
18XA1/VA1/NB-0.153-58.888-2.4309.6140.98460.1291.968274.318
In table 2 A and bi values are the coefficients of:
(10)
and leave one out procedure (loo) has the results:
(11) loo(12): r = 0.9768; s = 0.153; v(%) = 2.332; loo(18): r = 0.9778; s = 0.149; v(%) = 2.271.
The inhibitory activities of triazines on Chlorella have been taken from the study of Morita et al [24]. They are expressed as pI50, which represents the negative logarithm of concentration required for 50% inhibition of Hill reaction. The correlating results are listed in table 2. 4. Results and Discussion In single variable regression, the descriptors for the substituents in branch B (table 2) are not satisfactory to model the inhibitory activity of triazines; the correlation coefficient, r, is lower than 0.9 (for those in A, r is still lower) and the coefficient of variance, v, is about 5 %. Note that all these "steric" descriptors are taken as reciprocal values, suggesting that the triazine ring fits at the biological receptor as better as the substituent is less sterically involved. In two variables regression, by adding the descriptors for the branch A the correlation is improved, as indicates the higher values for r and F (the Fisher ratio) and the drop in the dispersion, s, and v(%) values (entries 5-8, table 2). When the descriptors for the two branches are heterogeneous, the result is still better (entries 9-11). In three variables regression, the correlation is once more improved. Again the heterogeneous descriptors model the inhibition reaction better that the homogeneous ones (compare entries 16-18 with 12-15, Table 2). The best model found (see also entry 18) was:
(12) pI50 = 9.614 0.153∙XA 58.888∙1/VA 2.430∙1/NB; n = 30; r2 = 0.9694; s = 0.129; v(%) = 1.968; F = 274.3;
The cross validation (leave-one-out, "loo", procedure) test for the equations in entries 12 and 18 are given in the bottom of table 2. Despite the excellent model offered by equation (10), a brief inspection on the general structure of these triazines showed a rather surprising error: the molecule is symmetric, so that the two branches A and B are interchangeable! In consequence, the two columns of descriptors have no meaning if they are taken as distinct descriptors. Thus, the contribution of the substituents in A and B in modeling the global biological activity must somehow be mixed! The simple summation (or simple arithmetic mean) of contributions of the two branches, A and B, did not provide satisfactory results. More reliable appeared in other kinds of average: geometric ("geo") and harmonic ("har"). The best correlating results are included in table 3. The cross validation test, loo, is given for each entry. From table 3 it appears that, in single variable regression, the descriptor 1/X(LDS)geo provides a rather good (r> 0.95) description of the activity, both in estimation and prediction, "loo" (entry 2). The best prediction is offered by the three variables equation, in entry 6 (r >0.975), all of them as harmonic average of the descriptors of A and B branches:
(13) pI50 = 10.292 119.503∙1/Vhar 0.097∙Xhar 0.047∙Ws,har; n = 30; r = 0.9807; s = 0.144; v(%) = 2.198; F = 218.158;
The corresponding arithmetic averaged descriptors used in (11) supplied a correlation of r = 0.955 which is, of course, unsatisfactory. This equation was chosen for a tempting prediction in the past. The experimental data for the compounds no. 3, 12, 21 and 24 (showing residuals, ycalc-yexp, about two times or larger than the value of standard error of estimate: s = +0.144; -0.254; +0.236; +0.301 and -0.398, respectively were changed by the values: 5.6209; 6.8778; 6.9073 and 6.8471, respectively calculated by equations:
(14) pI50 = 10.292 119.503 1/Vhar 0.097 Xhar 0.047 Ws,har n = 26; r = 0.9932; s = 0.086; v(%) = 1.309; F = 530.484
The correlating data, obtained by using the new column of activities, ycor, are included in table 3 as the rows "ycor". The improvement in the statistical parameters of the regression equations is obvious for all data of table 3 (where * means "leave one out" cross validation procedure; and ** are yi corrected for i = 3, 12, 21 and 24):
Table 3. Statistics of multivariable regression, Ycalc = a + Σi biXi (averaged variables)
No.Xibiarsv(%)F
11/Ws,harloo*ycor**-3.1517.1210.9553 0.9467 0.96660.210 0.229 0.1753.204 3.489 2.669292.215 398.721
21/Xgeolooycor-3.8917.2530.9621 0.9558 0.97930.194 0.209 0.1382.956 3.183 2.108348.097 655.776
31/VharNharlooycor-126.800 -0.54111.0910.9763 0.9721 0.99240.156 0.167 0.0862.387 2.543 1.307275.063 875.466
41/VharXharlooycor-113.340 -0.13710.0100.9777 0.9735 0.99070.152 0.163 0.0952.318 2.480 1.446292.278 713.286
51/NharXharWs,harlooycor-5.614 -0.056 -0.0579.4910.9798 0.9742 0.99180.147 0.160 0.0912.247 2.446 1.380208.342 523.336
61/VharXharWs,harlooycor-119.503 -0.097 -0.04710.2920.9807 0.9752 0.99380.144 0.157 0.0792.198 2.397 1.204218.158 690.328
71/VharXharWs,harNharlooycor-105.131 -0.232 -0.081 0.6739.0580.9824 0.9742 0.99380.141 0.160 0.0802.144 2.444 1.226172.608 499.253
81/NharXharWs,harVharlooycor-4.724 -0.228 -0.070 0.0527.8580.9825 0.9751 0.99240.140 0.157 0.0892.139 2.401 1.358173.400 405.773
More over, among the 24 descriptors (N, V, Ws, XLDS, 1/N, 1/V, 1/Ws, 1/XLDS, taken as "ari", "har" and "geo" average) used in single variable regression, in 20 of them an improvement of the statistics was recorded. Again the equation in entry 6 was the best model. This test suggested that the experimental data for the compounds, above mentioned, are "in error". From eq 11 and table 3, it comes out that the inhibitory activity of triazines is controlled by the possibility of the triazine ring (i.e., the pharmacophor) to accommodate at the receptor situs. This opinion is supported by the reciprocal values and the negative regression coefficient, and negative partial correlation index of these "steric" descriptors involved in an eq. of type 11. It suggests that the triazine ring fits at the biological receptor as better as the substituent is less sterically involved. A plot of the observed vs. calculated (by eq 11) pI50 values is given in figure 6. For comparison, the plot for the same descriptors and "ycor" is given in Figure 7.

Figure 6. Plot of experimental biological activity (VAR1) vs. ycalc. (cf. eq 11) values

Figure 7. Plot of experimental biological activity (VAR1) vs. ycor values

4. Computation of Fragmental Volumes
The geometries of the hydrocarbon fragments (in fact, the corresponding radicals) were fully optimized at the Unrestricted Hartree-Fock (UHF) level of theory, using the 6-31G** basis set (of DZP quality), which contains a single set of d polarization functions on carbons, and a single set of p polarization functions on hydrogens for better description of the radical wavefunctions. The Berny's optimization algorithm was used (the energy derivatives with respect to nuclear coordinates were computed analytically [25]), along with the initial guess of the second derivative matrix. Standard harmonic vibrational analysis was applied to test the character of the optimized geometries (stationary points at the potential energy hypersurfaces - PES). All stationary points corresponded to real minima on the explored PES. Molecular volume calculations were performed for the optimized structures, by the Monte-Carlo method. Since Monte-Carlo method for calculating molecular volume (defined as the volume inside a contour of 0.001 electrons/Bohr3 density) is stochastically based algorithm, it often leads to results accurate up to several percents. Therefore, 11 volume calculations per fragment were performed for each fragment, and the arithmetic average value was taken as the closest approximation to the real one (at the level of theory employed). In order to increase the density of points for a more accurate integration, the "Tight" option of the Gaussian "Volume" keyword was used. All calculations were performed with Gaussian 94 suite of programs [26].

5. Conclusions
The Ws descriptor, based on the walks in graph, satisfactorily describes the steric effect of alkyl substituents in the esterification reaction. It is a pure steric parameter, not affected by the electronic effects. Ws correlate well to the fragmental volumes (over 0.92) and show a lower degeneracy in comparison to the SVTI, n and Nc parameters. It is also well correlated [18] to the Taft, Es, (0.9637), and Charton, n, (0.9587), parameters, which makes from Ws a promising alternative in describing the steric effect of alkyl substituents.

6. Acknowledgment
The work was supported in part by the Romanian GRANT CNCSIS 2002.

References
[1] R. W. Taft, Linear free energy relationships from rates of esterification and hydrolysis of aliphatic and ortho-substituted benzoate esters. J. Am. Chem. Soc. 1952, 74, 2729-2732.
[2] R. W. Taft, Polar and steric substituent constants for aliphatic and o-benzoate groups from rates of esterification and hydrolysis of esters. J. Am. Chem. Soc. 1952, 74, 3120-3128.
[3] O. Ivanciuc and A. T. Balaban, A new topological parameter for the steric effect of alkyl substituents. Croat. Chem. Acta, 1996, 69, 75-83.
[4] M. Charton, The nature of the ortho effect. II. Composition of the Taft steric parameters. J. Am. Chem. Soc. 1969, 91, 615-618.
[5] M. Charton, Steric effects. I. Esterification and acid-catalyzed hydrolysis of esters. J. Am. Chem. Soc. 1975, 97, 1552-1556.
[6] M. Charton, Steric effects. II. Base-catalyzed ester hydrolysis. J. Am. Chem. Soc. 1975, 97, 3691-3693.
[7] M. Charton, Steric effects. III. Bimolecular nucleophilic substitution. J. Am. Chem. Soc. 1975, 97, 3694-3697.
[8] M. Charton, Steric effects. IV. E1 and E2 eliminations. J. Am. Chem. Soc. 1975, 97, 6159-6161.
[9] W. J. Murray, J. Pharm. Sci. 1977, 66, 1352.
[10] M. Randić, On characterization of molecular branching. J. Am. Chem. Soc. 97 (1975) 6609-6615.
[11] V. A. Skorobogatov and A. A. Dobrynin, Metric analysis of graphs. Commun. Math. Comput. Chem (MATCH) 1988, 23, 105-151.
[12] M. V. Diudea, O. M. Minaliuc and A. T. Balaban, Regressive Vertex Degrees (New Graph Invariants) and Derived Topological Indices. J. Comput. Chem., 1991, 12, 527-535.
[13] T. Balaban and M. V. Diudea, Real Number Vertex Invariants: Regressive Distance Sums and Related Topological Indices. J. Chem. Inf. Comput. Sci., 1993, 33, 421-428.
[14] M. V. Diudea, Layer Matrices in Molecular Graphs. J. Chem. Inf. Comput. Sci. 1994, 34, 1064-1071.
[15] M. V. Diudea, M. I. Topan and A. Graovac, Layer Matrices of Walk Degrees. J. Chem. Inf. Comput. Sci.1994, 34, 1072-1078.
[16] C. Y. Hu, L. Xu, A new algorithm for computer perception of topological symmetry. Anal. Chim. Acta 1994, 295, 127-134.
[17] Ch. Y. Hu, L. Xu, On highly discriminating molecular topological index. J. Chem. Inf. Comput. Sci. 1996, 36, 82-90.
[18] H. Wiener, Structural determination of parafin boiling point. J. Am. Chem. Soc., 1947, 69, 17-20.
[19] N. Trinajstić, Chemical Graph Theory; CRC Press, Inc.; Boca Raton, FL, 1983.
[20] G. Rcker, C. Rcker, Counts of all walks as atomic and molecular descriptors. J. Chem. Inf. Comput. Sci. 1993, 33, 683-695.
[21] M. Randić, Graph valence shells as molecular descriptors. J. Chem. Inf. Comput. Sci. 2001, 41, 627-630.
[22] C. M. Pop, M. V. Diudea and L. Pejov, Taft Revisited, Studia Univ."Babes-Bolyai", 1997, 42, 131-138.
[23] M. okić, D. Plavić, N. Trinajstić, 2-Difluoromethylthio-4,6-bis(monoalkylamino)-1,3,5-triazines as inhibitors of Hill reaction: a QSAR study with orthogonalized descriptors. J. Chem. Inf. Comput. Sci. 1996, 36, 146-150.
[24] K. Morita, T. Nagare, Y. Hayashi, Quantitative structure-activity relationships for herbicidal 2-Difluoromethylthio-4,6-bis(monoalkylamino)-1,3,5-triazines Agric. Biol. Chem., 1987, 51, 1955-1957.
[25] H. B. Schlegel, Optimization of Equilibrium Geometries and Transition Structures, J. Comp. Chem., 1982, 3, 214-220.
[26] M. J. Frisch, G. W. Trucks, H. B. Schlegel, P. M. W. Gill, B. G. Johnson, M. A. Robb, J. R. Cheeseman, T. A. Keith, G. A. Petersson, J. A. Montgomery, K. Raghavachari, M. A. Al-Laham, V. G. Zakrzewski, J. V. Ortiz, J. B. Foresman, C. Y. Peng, P. Y. Ayala, M. W. Wong, J. L. Andres, E. S. Replogle, R. Gomperts, R. L. Martin, D. J. Fox, J. S. Binkley, D. J. Defrees, J. Baker, J. P. Stewart, M. Head-Gordon, C. Gonzalez, and J. A. Pople, Gaussian 94 (Revision B.3), Gaussian Inc., Pittsburgh PA, 1995.
Issue 01, p. 19-36
Graph Theory. 1. Fragmentation of Structural Graphs
Lorentz JNTSCHI
Technical University Cluj-Napoca
http://lori.academicdirect.ro

Abstract
The investigation of structural graphs has many fields of applications in engineering, especially in applied sciences like as applied chemistry and physics, computer sciences and automation, electronics and telecommunication. The main subject of the paper is to express fragmentation criteria in graph using a new method of investigation: terminal paths. Using terminal paths are defined most of the fragmentation criteria that are in use in molecular topology, but the fields of applications are more generally than that, as I mentioned before. Graphical examples of fragmentation are given for every fragmentation criteria. Note that all fragmentation is made with a computer program that implements a routine for every criterion.[1] A web routine for tracing all terminal paths in graph can be found at the address: http://vl.academicdirect.ro/molecular_topology/tpaths/.
Keywords
Graph theory, Graph fragmentation, Vertex descriptors, Molecular topology, Graph coloring, Graph partitioning.

1. Introduction
The fragmentation of structural graphs has various applications, starting from electric circuits and internet routing and ending with computational chemistry and molecular topology. Partitioning of graph in classes of vertices may be done in different ways [2],[3]. The most frequently used discriminating criteria are well-known square matrices that collect contributions of pairs of vertices from the graph. The adjacency matrix is the simplest matrix of this type. Some authors use characteristic polynomial and its eigenvalue to characterize a given graph [4]. The sequence of eigenvalues forms the graph spectrum [5]. A basic result in spectral geometry is the theorem of Cheng [6]. Let us consider a sequence matrix. It is of dimension n(n-1), where n is the number of vertices. Such a matrix can be used to compare different graphs (interstructural similarity), when analyzing the columns of sequence matrices, the sums by columns or global sums (generic indices) [7]. It is also possible to compare the vertices of a graph (intrastructural similarity), when analyzing the rows of sequence matrices and the sums by rows [8],[9]. With this observation, a sequence matrix is an elegant method to investigate graphs [10]. Note that the ordering of graph vertices by using sequence matrices is of a partially ordered type [11],[12]. Prior, Dobrynin reported the degeneracy of some sequence matrices [13],[14]. Decomposition of graphs into congruent factors has interesting chemical implications [15],[16]. Dobrynin [17] and Diudea [18],[19] reported distance degree sequences (DPS in our notation) and their chemical applications. The path sequence matrix (APS in our notation) is calculated in order to study molecular similarity [20].

2. Terminal Paths
Let G = (V, E) be an un-oriented graph. We are note the set of all paths in G with P(G). The distance from i to j in G is d(G)i,j and detour is δ(G)i,j. For p P(G), l(p) denotes the length of path p.
(1) t = (vi)1≤i≤n is named terminal path if: vi V, t P(G) and " v V s. th. (vn, v) E then t (vn, v) P(G)
The set of terminal paths in G is T(G) = (T(G)v)v V where T(G)i is:
(2) T(G)i = {t = (vi)1≤i≤n s. th. v1 = i and t terminal path}
Note that if G = (V, E) is a connected graph, then " v V, " e E $ t T(G)v s. th. e t. Thus, any connected graph can be reconstructed from the terminal path list starting from an arbitrary vertex. Also, " i, j V, T(G)j can be constructed from T(G)i. Consequently, the sets of terminal paths T(G)v, v V are equivalent by construction. For exemplification of terminal paths, let us consider the graph G from fig. 1:

Fig. 1. Graph G G = (V, E); V = {1, ..., 8}; E = {(1, 2), (1, 3), (2, 4), (3, 5), (3, 6), (4, 5), (4, 7), (6, 7), (7,8)}
All terminal paths starting from vertex 1 are computed using graph G from figure 1 and definitions (1) and (2). The solution is:
(3) T(G)1 = {

}

{1, 2, 4, 5, 3, 6, 7, 8}, {1, 2, 4, 7, 8}, {1, 2, 4, 7, 6, 3, 5}, {1, 3, 6, 7, 8}, {1, 3, 6, 7, 4, 2}, {1, 3, 6, 7, 4, 5}, {1, 3, 5, 4, 7, 6}, {1, 3, 5, 4, 7, 8}, {1, 3, 5, 4, 2}
Note that according to definition (1) and (2), T(G) P(G) for any graph G.

3. Graph Partitioning in Sets
Let G = (V, E) be a connected graph and i, j V two vertices. Let p P(G)i,j a path from i to j in G.
(4) CJi,j,p = {k : k V} is named CJ set of i vs. j and p if: d(G)k,i < d(G)k,j $ q Pk,i s. th. p q = {i}
The set of sets of vertices CJSi,j = {CJi,j,p : p P(G)i,j} are named set of CJ sets of i vs. j.
(5) CJDii,j,p = {k : k V} is named CJDi set of i vs. j and p if: CJDii,j,p CJSi,j l(p) = d(G)i,j
The set of sets of vertices CJDiSi,j = {CJDii,j,p : p P(G)i,j} are named set of CJDi sets of i vs. j.
(6) CJDei,j,p = {k | k V} is named CJDe set of i vs. j and p if: CJDii,j,p CJSi,j l(p) = δ(G)i,j
The set of sets of vertices CJDeSi,j = {CJDei,j,p | p P(G)i,j} are named set of CJDe sets of i vs. j. CJDiMi,j = {s : s CJDiSi,j} is named CJDiM set of i vs. j if l(s) = max{ |cjdi| : cjdi CJDiSi,j}. CJDeMi,j = {s : s CJDeSi,j} is named CJDeM set of i vs. j if l(s) = max{ |cjde| : cjde CJDeSi,j}. The sets CJDi can be constructed as follows:
(7) CJDii,j,p = ; CJDij,i,p = ;
For (v = 1; v ≤ |V|; v++)
    If (d(G)v,i < d(G)v,j) and ($p' P(G)v,i s.th. p' p == {i}) then
      CJDii,j,p = CJDii,j,p {v};
    EndIf;
    If (d(G)v,j < d(G)v,i) and ($p' P(G)v,j s.th. p' p == {j}) then
      CJDij,i,p = CJDij,i,p {v};
    EndIf;
EndFor;
Note that the algorithm (7) can be applied for any distance operator in place of d(∙), such as detour operator δ(∙). Through CJ sets there exist inclusions relations:
(8) CJDiSMi,j CJDiSi,j CJSi,j and CJDeSMi,j CJDeSi,j CJSi,j
that are obviously from the definitions (4)-(6). Figurative, inclusions are:

Fig. 2. Inclusions relations in CJ sets
Note that in generally the sets CJDiSMi,j, CJDiSi,j, CJSi,j, CJDeSi,j, CJDeSMi,j are not distinct; more, in trees the sets are equals. To prove that the sets CJDiSMi,j, CJDiSi,j, CJSi,j, CJDeSi,j, CJDeSMi,j are not banal, lets apply the algorithm (7) to construct sets for graph G from fig. 1. Following example shows that sets CJDiSM and CJDeSM are not identically: CJDiSM1,2 = {CJ1,2,[1,2]}; CJ1,2,[1,2] = {1, 3, 6, 8} CJDiSM2,1 = {CJ2,1,[2,1]}; CJ2,1,[2,1] = {2, 4, 7} CJDeSM1,2 = {CJ1,2,[1,3,6,7,4,2]}; CJ1,2,[1,3,6,7,4,2] = {1} CJDeSM1,2 = {CJ2,1,[2,4,7,6,3,1]}; CJ2,1,[2,4,7,6,3,1] = {2} and graphical representation of them are in fig. 3:

Fig. 3. CJDi and CJDe sets for vertices 1 and 2 and graph G from fig. 1
The following example shows that CJDe sets are not included in CJDi sets: CJDiSM4,8 = {CJ4,8,[4,7,6,8]}; CJ4,8,[4,7,6,8] = {1, 2, 4, 5} CJDiSM8,4 = {CJ8,4,[8,6,7,4]}; CJ8,4,[8,6,7,4] = {8} CJDeSM4,8 = {CJ4,8,[4,2,1,3,6,8]}; CJ4,8,[4,2,1,3,6,8] = {4, 5, 7} CJDeSM8,4 = {CJ8,4,[8,6,3,1,2,4]}; CJ8,4,[8,6,3,1,2,4] = {8} and graphical representation of them are in fig. 4:

Fig. 4. CJDi4,8,[4,7,6,8] and CJDe4,8,[4,2,1,3,6,8] sets for graph G from fig. 1
The following example shows that sets CJDiSM can contain more than one set: CJDiSM2,8 = {CJ2,8,[2,4,7,6,8] = {1, 2, 5}, CJ2,8,[2,1,3,6,8] = {4, 2, 5}}; CJDiSM8,2 = {CJ8,2,[8,6,3,1,2] , CJ8,2,[8,6,3,1,2]}; CJ8,2,[8,6,3,1,2] = CJ8,2,[8,6,7,4,2] = {8}; and graphical representation of them are in fig. 5:

Fig. 5. CJDi2,8,[24768] and CJDi2,8,[21368] sets of graph G from fig. 1

4. Gp Subgraph
Let p = (i = v1, ..., vl(p) = j) P(G) a path starting from vertex i and ending in vertex j. The Gp subgraph of graph G and path p is defined by:
(9) Gp = (Vp, Ep), Vp = {v V : v p\{i, j}}, Ep = {e = (ea, eb) E : ea, eb p\{i, j}}
Note that Gp subgraph associated of graph G and path p is not necessary a connected subgraf, even if G is a connected graph. More, if G is a tree, Gp has at least two connected components. For path p = [1, 3, 5, 4, 7] and graph G from fig. 1 the graph G[1, 3, 5, 4, 7] = G\[1, 3, 5, 4, 7] is not a connected graph. Gp has two connected components: [1, 2] and [7, 6, 8]. Also, from original graph G, p\{1,7} is also a connected component. Using comparison operator ≤ between graphs is obviously that Gp p ≤ G. In fig. 6 are graphically represented the components of G by path p:

Fig. 6. Graph G, path p = [1, 3, 5, 4, 7], path p\{1, 7} = [3, 5, 4] and subgraph Gp Gp = (Vp, Ep), Vp = {1, 2, 6, 7, 8}, Ep = {(1,2), (6, 7), (6, 8)}
Note that G = Gp p [2, 4] [3, 6].

3. Graph Partitioning in Fragments
Let G = (V, E) be a connected graph and i, j V two vertices. Let p P(G)i,j a path from i to j in G.
(10) CFi,j,p = {k : k V} is named CF fragment of i vs. j and p if: d(Gp)k,i < d(Gp)k,j
where subgraph Gp is obtained from graph G and path p according to definition (9). Note that in definition (10) is used term of fragment for CFi,j,p. Indeed, CFi,j,p is an fragment, a connected set of vertices from graph G. The set of sets of vertices CFSi,j = {CFi,j,p : p P(G)i,j} are named set of CF sets of i vs. j. More, in CFSi,j,p fragment, there exist the relation:
(11) " k CFSi,j,p, $ q P(Gp)k.i path from k to i in Gp s. th. q p = {i}
Similar to definitions (5) and (6), CFDi and CFDe fragments are defined:
(12) CFDii,j,p={k : k V} is named CFDi fragment of i vs. j and p if: CFDii,j,p CFSi,j l(p) = d(Gp)i,j
The fragments set CFDiSi,j = {CFDii,j,p : p P(G)i,j} are named set of CFDi fragments of i vs. j.
(13) CFDei,j,p={k : k V} is named CFDe fragment of i vs. j and p if: CFDei,j,p CFSi,j l(p) = δ(Gp)i,j
The fragments set CFDeSi,j = {CFDei,j,p : p P(G)i,j} are named set of CFDe fragments of i vs. j. CFDiMi,j = {f : f CFDiSi,j} is named CFDiM fragment of i vs. j if l(f) = max{ |cfdi| : cfdi CFDiSi,j}. CFDeMi,j = {f : f CFDeSi,j} is named CFDeM set of i vs. j if l(f) = max{ |cfde| : cfde CFDeSi,j}. The sets CFDi can be constructed as follows:
(14) CFDii,j,p = ; CFDij,i,p = ;
For (v = 1; v ≤ |V|; v++)
    If (d(Gp)v,i < d(Gp)v,j) then
      CFDii,j,p = {v};
    EndIf;
    If (d(Gp)v,j < d(Gp)v,i) then
      CFDij,i,p = {v};
    EndIf;
EndFor;
Note that the algorithm (14) can be applied for any distance operator in place of d(∙), such as detour operator δ(∙). Based on construction (14) the sets CFDi are always fragments. Through CF sets it exist inclusions relations:
(15) CFDiSMi,j CFDiSi,j CFSi,j and CFDeSMi,j CFDeSi,j CFSi,j
that are obviously from the definitions (11)-(13). Figurative, inclusions are:

Fig. 7. Inclusions relations for CF sets
Note that in generally the sets CF are not distinct. In trees are even equals. To prove that the sets CFDiSMi,j, CFDiSi,j, CFSi,j, CFDeSi,j, CFDeSMi,j are not banal, lets apply the algorithm (14) to construct sets for graph G from fig. 1. Following example shows that sets CFDiSM and CFDeSM are not identically: CFDiSM1,2 = {CF1,2,[1,2]}; CF1,2,[1,2] = {1, 3, 6, 8} CFDiSM2,1 = {CF2,1,[2,1]}; CF2,1,[2,1] = {2, 4, 7} CFDeSM1,2 = {CF1,2,[1,3,6,7,4,2]}; CF1,2,[1,3,6,7,4,2] = {1} CFDeSM1,2 = {CF2,1,[2,4,7,6,3,1]}; CF2,1,[2,4,7,6,3,1] = {2} and graphical representation of them are in fig. 3:

Fig. 8. CFDi1,2,[1,2] and CFDi1,2,[1,2,6,7,4,2] fragments of graph G from fig. 1
The following example shows that CFDe sets are not included in CFDi sets: CFDiSM4,8 = {CF4,8,[4,7,6,8]}; CF4,8,[4,7,6,8] = {1, 2, 3, 4, 5}; CFDeSM4,8 = {CF4,8,[4,2,1,3,6,8]}; CF4,8,[4,2,1,3,6,8] = {4, 5, 7}; CFDiSM8,4 = {CF8,4,[8,6,7,4]} = {{8}} = {CF8,4,[8,6,3,1,2,4]} = CFDeSM8,4 and fragments are depicted in fig. 9:

Fig. 9. CFDi4,8,[4,7,6,8] and CFDe4,8,[4,2,1,3,6,8] fragments of graph G from fig. 1
The following example shows that sets CFDiSM can contain more than one fragment: CFDiSM7,1 = {CF7,1,[7,4,2,1] , CF7,1,[7,6,3,1]}; CF7,1,[7,4,2,1] = {6, 7, 8}; CF7,1,[7,6,3,1] = {4, 5, 7} and graphical representation of them are in fig. 10:

Fig. 10. CFDi7,1,[7,4,2,1] and CFDi7,1,[7,6,3,1] fragments of graph G from fig. 1 The Szeged (SzDi) fragments are defined by:
(16) SzDii,j = {k : k V} is named SzDi fragment of i vs. j if: d(G)k,i < d(G)k,j
The SzDi sets are connected subgraphs (fragments). Looking at (5) and (16) definitions, is easy to observe that:
(17) CJDi SzDi,
and also:
(18) CFDi SzDi,
The following construction collects the fragments SzDi for all i and j pairs of vertices:
(19) For (i = 1; i < |X|; i++)
    For (j = i + 1; j ≤ |X|; j++)
      SzDii,j := ; SzDij,i := ;
      For (v = 1; v ≤ |X|; v++)
        dvi = maxint; dvj = maxint;
        For (ct T(G)v)
          For (k = 1; k ≤ ct[0]; k++)
            If (ct[k] == i)and(dvi > k) then
              dvi = k;
            EndIf;
            If (ct[k] == j)and(dvj > k) then
              dvj = k;
            EndIf;
          EndFor;
        EndFor;
        If dvi > dvj then
          SzDii,j = {v};
        EndIf;
        If dvi > dvj then
          SzDij,i = {v};
        EndIf;
      EndFor;
    EndFor;
EndFor;
A graphical example of SzDi fragments for vertices 2 and 6 and graph G from fig. 1 is depicted in fig. 11:

Fig. 11. SzDi2,6 and SzDi6,2 fragments of graph G from fig. 1
Like CJ and CF, SzDe sets can be defined as:
(20) SzDii,j = {k : k V} is named SzDe set of i vs. j if: δ(G)k,i < δ(G)k,j
SzDe sets are not fragments (connected subgraphs). An example is depicted in fig. 12:

Fig. 12. SzDe2,6 = {2,3} and SzDe6,2 = {4, 6, 8} sets for graph G from fig. 1

4. A Comparison between Graph Partitioning Methods
Let us to consider the graph from fig. 13. If CFDi, CJDi and SzDi partitioning methods are applied for graph G from fig. 13 and (1,4) pair of vertices, we have: CFDi1,4,[1,2,3,4] = {1, 8, 9, 10}; CFDi4,1,[4,3,2,1] = {4, 5, 6, 7}; CJDi1,4,[1,2,3,4] = {1, 9, 10}; CJDi4,1,[4,3,2,1] = {4, 5, 6, 7, 8}; SzDi1,4 = {1, 2, 9, 10}, SzDi4,1 = {3, 4, 5, 6, 7, 8}.

Fig. 13. Graph G = (V, E); V = {1, ..., 10}; E = {(i, i+1) : 1 ≤ i ≤ 10} {(10, 1), (8, 3)} and CFDi1,4,[1,2,3,4], CFDi4,1,[4,3,2,1], CJDi1,4,[1,2,3,4], CJDi4,1,[4,3,2,1], SzDi1,4, SzDi4,1 sets
From fig. 13, some conclusions are immediate:
  • The sets CFDi and CJDi are distinct: CF4,1,[4,3,2,1] CJ4,1,[4,3,2,1] and CF1,4,[1,2,3,4] CJ1,4,[1,2,3,4];
  • The sets SzDi and CJDi are distinct: CJ4,1,[4,3,2,1] Sz4,1 and CJ1,4,[1,2,3,4] Sz1,4;
  • The sets SzDi and CFDi are distinct: CF4,1,[4,3,2,1] Sz4,1 and CF1,4,[1,2,3,4] Sz1,4;
  • The sets CFDi are not contained in sets SzDi: CF4,1,[4,3,2,1] Sz4,1 and CF1,4,[1,2,3,4] Sz1,4;
  • The CJDi sets are contained in SzDi sets: CJ4,1,[4,3,2,1] Sz4,1 and CJ1,4,[1,2,3,4] Sz1,4;
    Let us consider another two fragmentation methods, the minimal set that contain i vertex and not contain j vertex MIi,j:
    (21) MIi,j = {i}
    and maximal set that contain i vertex and not contain j vertex:
    (22) MAi,j = G\{j}
    Some interesting properties are also available now:
  • MIi,j is a set that is contained in all sets generated for (i,j) pair of vertices:
    (23) MIi,j CJi,j,p; MIi,j CFi,j,p; MIi,j Szi,j
  • MAi,j it contain all fragments generated for (i,j) pair of vertices:
    (24) CJi,j,p MAi,j; CFi,j,p MAi,j; Szi,j MAi,j
    The inclusions and intersections of sets are depicted in fig. 14:

    Fig. 14. Inclusions between MI, CJ, CF, SZ and MA sets

    5. Graph Edges Coloring
    The edges of a graph can be colored depending on which fragment are included. To apply the coloring process, is necessary to decompose the graph into connected fragments. From presented methods, connected subgraphs are obtained for CFDi, CFDe and SzDi criteria. The CFDi criterion partition a graph G for a pair of vertices (i, j) into four regions:
  • region of is belonging versus j, that is CFDii,j,p;
  • region of js belonging versus i, that is CFDij,i,p;
  • the path p\{i, j};
  • indifferent region G\{p\{i, j} CFDii,j,p CFDij,i,p}
    An important observation is that first three regions are connected sets of vertices (fragments) and last one (indifferent region) it can be a disconnected subgraph. In fig. 15 are depicted partitioning of graph G from fig. 1 into four regions:

    Fig. 15. Graph G from fig. 1 edges coloring in two cases: (3, 6) and (3,4) pairs of vertices yellow: CFDii,j; turquoise: CFDij,i; pink: p\{i, j}; red: rest;
    The fragments from fig. 15 are: CFDi3,6,[3,6] = [1,2,3,5]; CFDi6,3,[6,3] = [6,7,8]; CFDi3,4,[3,5,4] = [1,3,6,8]; CFDi4,3,[4,5,3] = [2,4,7]; Note that for (3,4) pair of vertices, the remaining zone of graph, {(1, 2, 6, 7), (1, 2), (6, 7)} are not connected one. With a similar deduction, The CFDe criterion partition a graph G for a pair of vertices (i, j) into four regions:
  • region of is belonging versus j, that is CFDei,j,p;
  • region of js belonging versus i, that is CFDej,i,p;
  • the path p\{i, j};
  • indifferent region G\{p\{i, j} CFDei,j,p CFDej,i,p}
    An important observation is that first three regions are connected sets of vertices (fragments) and last one (indifferent region) it can be a disconnected subgraph. In fig. 16 are depicted partitioning of graph G from fig. 1 into four regions:

    Fig. 16. Graph G from fig. 1 edges coloring in two cases: (3, 6) and (3,4) pairs of vertices yellow: CFDei,j; turquoise: CFDej,i; pink: p\{i, j}; red: rest;
    The fragments from fig. 16 are: CFDi3,6,[3,1,2,4,7,6] = [3,5]; CFDi6,3,[6,7,4,2,1,3] = [6,8]; CFDi3,4,[3,1,2,4] = [3,6,8]; CFDi4,3,[4,2,1,3] = [4,7]; Note that for (3,4) pair of vertices, the remaining zone of graph, {(1, 2, 6, 7), (1, 2), (6, 7)} are not connected one. With a similar deduction, The SzDi criterion partition a graph G for a pair of vertices (i, j) into three regions:
  • region of is belonging versus j, that is CFDei,j,p;
  • region of js belonging versus i, that is CFDej,i,p;
  • the equidistant region {k : d(k,i) = d(k,j)}.
    An important observation is that first two regions are connected sets of vertices (fragments) and last one (equidistant region) it can be a disconnected subgraph. In fig. 17 are depicted partitioning of graph G from fig. 1 into three regions:

    Fig. 17. Graph G from fig. 1 edges coloring in two cases: (3, 6) and (3,4) pairs of vertices yellow: CFDei,j; turquoise: CFDej,i; red: equidistant region {k : d(k,i) = d(k,j)};
    The fragments from fig. 17 are: SzDi3,6 = [1,2,3,5]; SzDi6,3 = [6,7,8]; SzDi3,4 = [1,3,6,8]; SzDi4,3 = [2,4,7];

    6. Theoretical Results (Theorems)
    Theorem 1. CF is a fragment.
    " i, j V,  p P(G)i,j path in G from i to j then Fi,j,p fragment
    Demonstration:

    Fig. 18. Auxiliary construction for theorem 1 demonstration
    Let v CFi,j,p. Then:
    (Case 1) d(Gp)v,i < , d(Gp)v,j = and respectively
    (Case2) d(Gp)v,i < , d(Gp)v,j < , d(Gp)v,i < d(Gp)v,j
    (Case 1, demonstration):
    d(Gp)v,i < $ pv,i P(Gp)v,i (P(Gp)k,i ). Let k pv,i $ pk,i P(Gp)k,i (pk,i pv,i)
    (25) d(Gp)k,i < $ pv,k P(Gp)v,k (pv,k pv,i)
    If d(Gp)k,j < $ pk,j P(Gp)k,j (P(Gp)k,j ). Let wv,j = pv,k pk,j; wv,j W(Gp)v,j (W(Gp)v,j ) d(Gp)v,j l(pv,k) + l(pk,j) < contradiction with d(Gp)v,j =
    (26) d(Gp)k,j =
    From (25) and (26) k CFi,j,p pv,i CFi,j,p v connected with i in CFi,j,p
    (27) CFi,j,p connected
    (Case 2, demonstration):
    d(Gp)v,i < $ pv,i P(Gp)v,i s. th. l(pv,i) = min{l(q), q P(Gp)v,i} (P(Gp)v,i ; l(pv,i) = d(Gp)v,i). Let k pv,i
    (28) $ pk,i P(Gp)k,i (pk,i pv,i) , $ pv,k P(Gp)v,k (pv,k pv,i)
    Because a geodesic path can contain only geodesic paths, from (28) it results: l(pk,i) = d(Gp)k,i , l(pv,k) = d(Gp)v,k , l(pv,i) = l(pv,k) + l(pk,i) d(Gp)v,i = d(Gp)v,k + d(Gp)k,i d(Gp)v,j d(Gp)v,k + d(Gp)k,j (d(Gp) a metric); (28) d(Gp)v,j -d(Gp)v,i d(Gp)k,j - d(Gp)k,i From d(Gp)v,i < d(Gp)v,j 0 <d(Gp)v,j - d(Gp)v,i d(Gp)k,j-d(Gp)k,i and then: d(Gp)k,i < d(Gp)k,j k CFi,j,p pv,i CFi,j,p
    (29) v connected with i in CFi,j,p CFi,j,p connected
    From (27) and (29) it result that CFi,j,p is a connected subgraph (q.e.d.).
    Theorem 2. SzDi is a fragment.
    " i, j V then SZDii,j fragment
    Demonstration:
    Let v SZDii,j. Then d(G)v,i < , d(G)v,j < , d(G)v,i < d(G)v,j (G connected graph). From d(G)v,i < $ pv,i P(G)v,i s. th. l(pv,i) = min{l(q), q P(G)v,i} (P(G)v,i ; l(pv,i) = d(G)v,i). Let k pv,i
    (30) $ pk,i P(G)k,i (pk,i pv,i) , $ pv,k P(G)v,k (pv,k pv,i)
    Because a geodesic path can contain only geodesic paths, from (28) it results: l(pk,i) = d(G)k,i , l(pv,k) = d(G)v,k , l(pv,i) = l(pv,k) + l(pk,i) d(G)v,i = d(G)v,k + d(G)k,i d(G)v,j d(G)v,k + d(G)k,j (d(G) a metric); (30) d(G)v,j - d(G)v,i d(G)k,j - d(G)k,i Because d(G)v,i < d(G)v,j 0 < d(G)v,j-d(G)v,i d(G)k,j-d(G)k,i and then d(G)k,i < d(G)k,j k SzDii,j pv,i SzDii,j v connected with i in SzDii,j SzDii,j connected subgraph (q.e.d.).
    Theorem 3. CJDi sets are contained in SzDi fragments.
    CJDii,j,p SzDii,j
    Demonstration:
    Let v CJDii,j,p. According to definition of CJDi set,
    d(G)v,i < d(G)v,j (31)
    This is (according to the definition of SzDi fragment) a necessary and enough such that v SzDii,j,p. From here, it result immediately that CJDii,j,p SzDii,j (q.e.d.).

    References
    [1] M. V. Diudea, I. Gutman, L. Jntschi, 'Molecular Topology', Nova Science, Commack, New York, 2002.
    [2] X. Liu, K. Balasubramanian, E. M. Munk, 'Computational Techniques for Vertex Partitioning of Graphs', J. Chem. Comput. Sci., 30 (1990), 263-269.
    [3] A. V. Skorobogatov, A. A. Dobrynin, 'Metric Analysis of Graphs', Commun. Math. Comput. Chem., 23 (1988), 105-151.
    [4] T. Quenell, 'Eigenvalue comparisons in Graph Theory', Pacific J. of Math., 176-2 (1996), 443-461.
    [5] F. Harary, A. J. Schwenk, 'The Spectral Approach to Determining the Number of Walks in a Graph', Pacific J. of Math., 80-2 (1979), 443-449.
    [6] S.-Y. Cheng, 'Eigenvalue Comparison Theorems and Its Geometric Applications', Math. Z., 143 (1975), 289-297.
    [7] C. S. Basak, R. V. Magnusson, G. Niemi, R. Regal, 'Determining Structural Similarity of Chemicals Using Graph-Theoretic Indices', Discr. Appl. Math., 19 (1988), 17-44.
    [8] X. Liu, K. Balasubramanian, E. M. Munk, 'Computational Techniques for Vertex Partitioning of Graphs', J. Chem. Inf. Comput. Sci., 30 (1990), 263-269.
    [9] M. Bersohn, 'A Matrix Method for Partitioning the Atoms of a Molecule Into Equivalence Classes', Comput. Chem., 11 (1987), 67-72.
    [10] A. T. Balaban, 'Local versus Global (i.e. Atomic versus Molecular) Numerical Modelling of Molecular Graphs', J. Chem. Inf. Comput. Sci., 34 (1994), 398-402.
    [11] M. Lerman, I. R. Soare, 'd-Simple Sets, Small Sets and Degree Classes', Pacific J. of Math., 87-1 (1980), 135-155.
    [12] D. Dhar, 'Asymptotic Enumeration of Partially Ordered Sets', Pacific J. of Math., 90-2 (1980), 299-306.
    [13] A. A. Dobrynin, 'Degeneracy of Some Matrix Graph Invariants', J. of Math. Chem., 14 (1993) 175-184.
    [14] A. A. Dobrynin, 'Cubic Graphs with 62 Vertices Having the Same Path Layer Matrix', J. Graph Theory, 17 (1993), 1-4.
    [15] A. T. Balaban, 'Applications of Graph Theory in Chemistry', J. Chem. Inf. Comput. Sci., 25 (1985), 334-343.
    [16] A. T. Balaban, 'Solved and Unsolved Problems in Chemical Graph Theory', Annals of Discr. Math., 55 (1993), 109-126.
    [17] A. A. Dobrynin, A. A. Kochetova, 'Degree Distance of a Graph: A Degree Analogue of the Wiener Index', J. Chem. Inf. Comput. Sci., 36 (1996), 1082-1086.
    [18] M. V. Diudea, 'Layer Matrices in Molecular Graphs', J. Chem. Inf. Comput. Sci., 34 (1994), 1064-1071.
    [19] M. V. Diudea, M. Topan, A. Graovac, 'Layer Matrices of Walk Degrees', J. Chem. Inf. Comput. Sci., 34 (1994), 1072-1078.
    [20] M. Randić, 'Design of Molecules with Desired Properties (A Molecular Similarity Approach to Property Optimization),' in 'Concept and Applications of Molecular Similarity', Ed. A. M. Johnson, G. M. Maggiora, John Wiley & Sons, 5 (1990), 77-145.
    Issue 01, p. 37-52

    Graph Theory. 2. Vertex Descriptors and Graph Coloring
    Lorentz JNTSCHI
    Technical University of Cluj-Napoca
    http://lori.academicdirect.ro

    Abstract
    This original work presents the construction of a set of ten sequence matrices and their applications for ordering vertices in graphs. For every sequence matrix three ordering criteria are applied: lexicographic ordering, based on strings of numbers, corresponding to every vertex, extracted as rows from sequence matrices; ordering by the sum of path lengths from a given vertex; and ordering by the sum of paths, starting from a given vertex. We also examine a graph that has different orderings for the above criteria. We then proceed to demonstrate that every criterion induced its own partition of graph vertex. We propose the following theoretical result: both LAVS and LVDS criteria generate identical partitioning of vertices in any graph. Finally, a coloring of graph vertices according to introduced ordering criteria was proposed.
    Keywords
    Graph theory, Vertex descriptors, Matrix based descriptors, Invariants, Graph coloring, Graph partitioning.

    1. Introduction
    The problem of vertex partitioning in graphs can be solved in different ways [1],[2]. The most frequently used discriminating criteria are well-known square matrices that collect contributions of pairs of vertices from the graph. The adjacency matrix is the simplest matrix of this type. Some authors use characteristic polynomial and its eigenvalue to characterize a given graph [3]. The sequence of eigenvalues forms the graph spectrum [4]. A basic result in spectral geometry is the theorem of Cheng [5]. Let us consider a sequence matrix. It is of dimension n(n-1), where n is the number of vertices. Such a matrix can be used to compare different graphs (interstructural similarity), when analyzing the columns of sequence matrices, the sums by columns or global sums (generic indices) [6]. It is also possible to compare the vertices of a graph (intrastructural similarity), when analyzing the rows of sequence matrices and the sums by rows [7],[8]. With this observation, a sequence matrix is an elegant method to investigate graphs [9]. Note that the ordering of graph vertices by using sequence matrices is of a partially ordered type [10],[11]. Prior, Dobrynin reported the degeneracy of some sequence matrices [12],[13]. Decomposition of graphs into congruent factors has interesting chemical implications [14],[15]. Dobrynin [16] and Diudea [17],[18] reported distance degree sequences (DPS in our notation) and their chemical applications. The path sequence matrix (APS in our notation) is calculated in order to study molecular similarity [19].

    2. Theoretical Considerations
    Some definitions are required. Let G = (V, E) be an un-oriented graph. We are note the set of all path in G with P(G). The distance from i to j in G is d(G)i,j and detour is δ(G)i,j. For p P(G), l(p) denotes the length of path p. t = (vi)1≤i≤n is a terminal path if: (1) t P(G) and (2) " v V s. th. (vn, v) E then t (vn, v) P(G). The set of terminal paths starting with i in G is T(G)i = {t = (vi)1≤i≤n s. th. v1 = i and t terminal path}. The set of terminal paths in G is T(G) = (T(G)v)v V. The set of distance paths from i to j in G is DP(G)i,j = {p=(xi)1 i n s. th. p P(G), x1=i, xn=j & l(p)=d(G)i,j}. The set of distance path in G is DP(G) = {p = (xi)1 i n s. th. p P(G) and l(p) = }. The set of detour paths from i to j in G is ΔP(G)i,j = {p=(xi)1 i n s. th. p P(G), x1=i, xn=j & l(p)=δ(G)i,j}. The set of detour path in G is ΔP(G) = {p = (xi)1 i n s. th. p P(G) and l(p) =
    }. The set of distance terminal paths from i to j in G is DT(G)i,j = {t=(xi)1 i n s. th. t T(G), x1=i, xn=j & l(t)=d(G)i,j}. The set of distance terminal path in G is DT(G) = {t = (xi)1 i n s. th. t T(G) and l(t) = }. The set of detour terminal paths from i to j in G is ΔT(G)i,j = {t=(xi)1 i n s. th. t T(G), x1=i, xn=j & l(t)= δ(G)i,j}. The set of detour terminal path in G is ΔT(G) = {t = (xi)1 i n s. th. t T(G) and l(t) =
    }. Note that if G = (V, E) is a connected graph, then " v V, " e E $ t T(G)v s. th. e t. Thus, any connected graph can be reconstructed from the terminal path list starting from an arbitrary vertex. Also, " i, j V, T(G)j can be constructed from T(G)i. Consequently, the sets of terminal paths T(G)v, v V are equivalent by construction. In order to generate sequence matrices, we compute terminal paths. Let G = (V, E), V = {1, , 8}, E = {(1, 2), (1, 3), (2, 4), (3, 5), (3, 6), (4, 5), (4, 7), (6, 7), (7,8)} shown in figure 1:

    Fig. 1. Graph G (see above)
    We have devised a 16-bit windows original computer program to list all terminal paths. For the graph in figure 1, we have obtained the following set of terminal paths for vertex 1:
    T(G)1
    1 2 4 5 3 6 7 8
    1 2 4 7 8
    1 2 4 7 6 3 5
    1 3 6 7 8
    1 3 6 7 4 2
    1 3 6 7 4 5
    1 3 5 4 7 6
    1 3 5 4 7 8
    1 3 5 4 2
    
    Fig. 2. Terminal paths of graph G from fig. 1 starting from vertex 1

    3. The Construction of Sequence Matrices of Numbering
    We extend the concept used for the distance degree sequence matrix [16] and layer path (path degree sequence) [19] matrix to construct a set of 10 sequence matrices. A sequence matrix is a matrix that collects vertex contribution in each row and elongation of paths in each column. The elements of the matrix cumulate a value of vertex property for a given elongation. Sequence matrices are of dimension n(n-1) and are given by following definitions: SMN (sequence matrix of numbering) of paths (P) which starts with i and has length j is APS(G)i,j = |{p P(G), s. th. p1 = i, l(p) = j}|, where p1 is the first vertex from path p and operator |∙| is the cardinal operator. SMN of distance P that starts with i and has length j is DPS(G)i,j = |{p APS(G)i,j, s. th. p DP(G)}|. SMN of detour P that starts with i and has length j is ΔPS(G)i,j = |{p APS(G)i,j, s. th. p ΔP(G)}|. SMN of terminal paths (T) which starts with i and has length j is ATS(G)i,j = |{t T(G), s. th. t1 = i, l(t) = j}}|. SMN of distance T that starts with i and has length j is DTS(G)i,j = |{p ATS(G)i,j, s. th. p DT(G)}|. SMN of detour T that starts with i and has length j is ΔTS(G)i,j = |{p ATS(G)i,j, s. th. p ΔT(G)}|. SMN of the vertex situated at the end of paths that starts with i and has j edges is AVS(G)i,j = |{v V, s. th. $ p P(G), p1 = i, pj+1 = v, l(p) = j}|. SMN of the vertex situated at the end of distance paths that starts with i and has j edges is DVS(G)i,j = |{v V, s. th. $ p DP(G), p1 = i, pj+1 = v, l(p)=j}|. SMN of the vertex situated at the end of detour paths that starts with i and has j edges is ΔVS(G)i,j = |{v V, s. th. $ p ΔP(G), p1 = i, pj+1 = v, l(p)=j}|. SMN of the cycles that contain vertex i and has j edges is ACS(G)i,j = |{p P(G), s. th. l(p) = j-1 and (pj,p1) E}|. If an lexicographically ordering are applied to the sequence matrices of numbering (SMN), through permutation of one line with another, and the new matrix obtained can be used to make interstructural comparisons (with any other graph) because a lexicographically ordered matrix is independent with respect to labeling. When two vertices are compared, lexicographic ordering is also useful from the point of view of the selected criterion. The results of lexicographic ordering can be used to index the graph, by permuting the old indexing. The computer program used in lexicographic ordering (quicksort method), gives permutation of partial ordering (σ in what follows). Ten sequence matrices, ten lexicographically associated matrices and ten permutations σ are computed. Two vertex indices in every case (from ten cases) are calculated. The first is sum of elements from the row (the number of total paths), the second is the weighted sum of elements from the row (the length of total paths). For the graph G from figure 1 we obtain a set of ten tables with three different ordering criteria (table 1-10).
    Table 1. APS and LAPS numbered sequences
    APS 1 2 3 4 5 6 7 ΣiSi,j ΣiSi,j∙i LAPS 1 2 3 4 5 6 7 ΣiSi,j ΣiSi,j∙i
    1 2 3 4 7 6 2 1 25 97 1=σ(8) 1 2 3 4 5 5 2 22 99
    2 2 3 5 5 6 4 0 25 97 2=σ(1) 2 3 4 7 6 2 1 25 97
    3 3 3 5 7 3 0 0 21 67 3=σ(2) 2 3 5 5 6 4 0 25 97
    4 3 4 4 6 3 1 0 21 68 4=σ(6) 2 4 4 5 6 3 0 24 90
    5 2 4 5 5 4 5 1 26 102 5=σ(5) 2 4 5 5 4 5 1 26 102
    6 2 4 4 5 6 3 0 24 90 6=σ(7) 3 3 4 5 5 2 0 22 78
    7 3 3 4 5 5 2 0 22 78 7=σ(3) 3 3 5 7 3 0 0 21 67
    8 1 2 3 4 5 5 2 22 99 8=σ(4) 3 4 4 6 3 1 0 21 68

    Table 2. DPS and LDPS numbered sequences
    DPS 1 2 3 4 5 6 7 ΣiSi,j ΣiSi,j∙i LDPS 1 2 3 4 5 6 7 ΣiSi,j ΣiSi,j∙i
    1 2 3 2 2 0 0 0 9 22 1=σ(8) 1 2 3 2 0 0 0 8 22
    2 2 3 3 0 0 0 0 8 17 2=σ(1) 2 3 2 2 0 0 0 9 22
    3 3 3 1 0 0 0 0 7 12 3=σ(2) 2 3 3 0 0 0 0 8 17
    4 3 4 0 0 0 0 0 7 11 4=σ(5) 2 4 1 0 0 0 0 7 13
    5 2 4 1 0 0 0 0 7 13 5=σ(6) 2 4 2 0 0 0 0 8 16
    6 2 4 2 0 0 0 0 8 16 6=σ(3) 3 3 1 0 0 0 0 7 12
    7 3 3 2 0 0 0 0 8 15 7=σ(7) 3 3 2 0 0 0 0 8 15
    8 1 2 3 2 0 0 0 8 22 8=σ(4) 3 4 0 0 0 0 0 7 11

    Table 3. ΔPS and LΔPS numbered sequences
    ΔPS 1 2 3 4 5 6 7 ΣiSi,j ΣiSi,j∙i LΔPS 1 2 3 4 5 6 7 ΣiSi,j ΣiSi,j∙i
    1 0 0 0 1 4 2 1 8 43 1=σ(1) 0 0 0 1 4 2 1 8 43
    2 0 0 0 1 4 4 0 9 48 2=σ(6) 0 0 0 1 4 3 0 8 42
    3 0 0 2 4 3 0 0 9 37 3=σ(2) 0 0 0 1 4 4 0 9 48
    4 0 0 2 4 2 1 0 9 38 4=σ(5) 0 0 0 4 0 4 1 9 47
    5 0 0 0 4 0 4 1 9 47 5=σ(4) 0 0 2 4 2 1 0 9 38
    6 0 0 0 1 4 3 0 8 42 6=σ(3) 0 0 2 4 3 0 0 9 37
    7 1 0 0 1 4 2 0 8 37 7=σ(8) 1 0 0 0 1 4 2 8 44
    8 1 0 0 0 1 4 2 8 44 8=σ(7) 1 0 0 1 4 2 0 8 37

    Table 4. ATS and LATS numbered sequences
    ATS 1 2 3 4 5 6 7 ΣiSi,j ΣiSi,j∙i LATS 1 2 3 4 5 6 7 ΣiSi,j ΣiSi,j∙i
    1 0 0 0 3 4 1 1 9 45 1=σ(8) 0 0 0 0 1 3 2 6 37
    2 0 0 1 1 3 4 0 9 46 2=σ(1) 0 0 0 3 4 1 1 9 45
    3 0 0 1 5 3 0 0 9 38 3=σ(5) 0 0 1 1 0 4 1 7 38
    4 0 1 0 3 2 1 0 7 30 4=σ(2) 0 0 1 1 3 4 0 9 46
    5 0 0 1 1 0 4 1 7 38 5=σ(3) 0 0 1 5 3 0 0 9 38
    6 0 1 0 0 3 3 0 7 35 6=σ(6) 0 1 0 0 3 3 0 7 35
    7 1 0 0 1 3 2 0 7 32 7=σ(4) 0 1 0 3 2 1 0 7 30
    8 0 0 0 0 1 3 2 6 37 8=σ(7) 1 0 0 1 3 2 0 7 32

    Table 5. DTS and LDTS numbered sequences
    DTS 1 2 3 4 5 6 7 ΣiSi,j ΣiSi,j∙i LDTS 1 2 3 4 5 6 7 ΣiSi,j ΣiSi,j∙i
    1 0 0 0 2 0 0 0 2 8 1=σ(8) 0 0 0 0 0 0 0 0 0
    2 0 0 1 0 0 0 0 1 3 2=σ(1) 0 0 0 2 0 0 0 2 8
    3 0 0 1 0 0 0 0 1 3 3=σ(3) 0 0 1 0 0 0 0 1 3
    4 0 1 0 0 0 0 0 1 2 4=σ(5) 0 0 1 0 0 0 0 1 3
    5 0 0 1 0 0 0 0 1 3 5=σ(2) 0 0 1 0 0 0 0 1 3
    6 0 1 0 0 0 0 0 1 2 6=σ(4) 0 1 0 0 0 0 0 1 2
    7 1 0 0 0 0 0 0 1 1 7=σ(6) 0 1 0 0 0 0 0 1 2
    8 0 0 0 0 0 0 0 0 0 8=σ(7) 1 0 0 0 0 0 0 1 1

    Table 6. ΔTS and LΔTS numbered sequences
    ΔTS 1 2 3 4 5 6 7 ΣiSi,j ΣiSi,j∙i LΔTS 1 2 3 4 5 6 7 ΣiSi,j ΣiSi,j∙i
    1 0 0 0 0 2 1 1 4 23 1=σ(8) 0 0 0 0 0 2 2 4 26
    2 0 0 0 0 1 4 0 5 29 2=σ(5) 0 0 0 0 0 3 1 4 25
    3 0 0 0 2 3 0 0 5 23 3=σ(6) 0 0 0 0 1 3 0 4 23
    4 0 0 0 2 1 1 0 4 19 4=σ(2) 0 0 0 0 1 4 0 5 29
    5 0 0 0 0 0 3 1 4 25 5=σ(1) 0 0 0 0 2 1 1 4 23
    6 0 0 0 0 1 3 0 4 23 6=σ(4) 0 0 0 2 1 1 0 4 19
    7 1 0 0 0 2 2 0 5 23 7=σ(3) 0 0 0 2 3 0 0 5 23
    8 0 0 0 0 0 2 2 4 26 8=σ(7) 1 0 0 0 2 2 0 5 23

    Table 7. AVS and LAVS numbered sequences
    AVS 1 2 3 4 5 6 7 ΣiSi,j ΣiSi,j∙i LAVS 1 2 3 4 5 6 7 ΣiSi,j ΣiSi,j∙i
    1 3 6 7 8 8 8 8 48 212 1=σ(8) 2 4 7 8 8 8 8 45 207
    2 3 6 8 8 8 8 8 49 215 2=σ(1) 3 6 7 8 8 8 8 48 212
    3 4 7 8 8 8 8 8 51 218 3=σ(2) 3 6 8 8 8 8 8 49 215
    4 4 8 8 8 8 8 8 52 220 4=σ(5) 3 7 8 8 8 8 8 50 217
    5 3 7 8 8 8 8 8 50 217 5=σ(6) 3 7 8 8 8 8 8 50 217
    6 3 7 8 8 8 8 8 50 217 6=σ(3) 4 7 8 8 8 8 8 51 218
    7 4 7 8 8 8 8 8 51 218 7=σ(7) 4 7 8 8 8 8 8 51 218
    8 2 4 7 8 8 8 8 45 207 8=σ(4) 4 8 8 8 8 8 8 52 220

    Table 8. DVS and LDVS numbered sequences
    DVS 1 2 3 4 5 6 7 ΣiSi,j ΣiSi,j∙i LDVS 1 2 3 4 5 6 7 ΣiSi,j ΣiSi,j∙i
    1 2 3 1 1 0 0 0 7 15 1=σ(8) 1 2 3 1 0 0 0 7 18
    2 2 3 2 0 0 0 0 7 14 2=σ(1) 2 3 1 1 0 0 0 7 15
    3 3 3 1 0 0 0 0 7 12 3=σ(2) 2 3 2 0 0 0 0 7 14
    4 3 4 0 0 0 0 0 7 11 4=σ(5) 2 4 1 0 0 0 0 7 13
    5 2 4 1 0 0 0 0 7 13 5=σ(6) 2 4 1 0 0 0 0 7 13
    6 2 4 1 0 0 0 0 7 13 6=σ(3) 3 3 1 0 0 0 0 7 12
    7 3 3 1 0 0 0 0 7 12 7=σ(7) 3 3 1 0 0 0 0 7 12
    8 1 2 3 1 0 0 0 7 18 8=σ(4) 3 4 0 0 0 0 0 7 11

    Table 9. ΔVS and LΔVS numbered sequences
    ΔVS 1 2 3 4 5 6 7 ΣiSi,j ΣiSi,j∙i LΔVS 1 2 3 4 5 6 7 ΣiSi,j ΣiSi,j∙i
    1 0 0 0 1 3 2 1 7 38 1=σ(1) 0 0 0 1 3 2 1 7 38
    2 0 0 0 1 3 3 0 7 37 2=σ(2) 0 0 0 1 3 3 0 7 37
    3 0 0 1 3 3 0 0 7 30 3=σ(6) 0 0 0 1 3 3 0 7 37
    4 0 0 1 3 2 1 0 7 31 4=σ(5) 0 0 0 2 0 4 1 7 39
    5 0 0 0 2 0 4 1 7 39 5=σ(4) 0 0 1 3 2 1 0 7 31
    6 0 0 0 1 3 3 0 7 37 6=σ(3) 0 0 1 3 3 0 0 7 30
    7 1 0 0 1 3 2 0 7 32 7=σ(8) 1 0 0 0 1 3 2 7 38
    8 1 0 0 0 1 3 2 7 38 8=σ(7) 1 0 0 1 3 2 0 7 32

    Table 10. ACS and LACS numbered sequences
    ACS 1 2 3 4 5 6 7 ΣiSi,j ΣiSi,j∙i LACS 1 2 3 4 5 6 7 ΣiSi,j ΣiSi,j∙i
    1 0 0 0 1 1 0 0 2 11 1=σ(8) 0 0 0 0 0 0 0 0 0
    2 0 0 0 1 1 0 0 2 11 2=σ(1) 0 0 0 0 1 1 0 2 11
    3 0 0 0 2 1 0 0 3 16 3=σ(2) 0 0 0 0 1 1 0 2 11
    4 0 0 0 2 1 0 0 3 16 4=σ(6) 0 0 0 0 1 1 0 2 11
    5 0 0 0 2 0 0 0 2 10 5=σ(7) 0 0 0 0 1 1 0 2 11
    6 0 0 0 1 1 0 0 2 11 6=σ(5) 0 0 0 0 2 0 0 2 10
    7 0 0 0 1 1 0 0 2 11 7=σ(3) 0 0 0 0 2 1 0 3 16
    8 0 0 0 0 0 0 0 0 0 8=σ(4) 0 0 0 0 2 1 0 3 16


    4. Graph Partitioning
    Three operators on SMN matrices were applied for vertex comparison: LSMN (lexicographically ordered matrix of numbering), SMNΣpnp (sum of all path number that satisfy selected criteria) and SMNΣpnp∙l(p) (sum of all length of path that satisfy selected criteria).
    Every operator induces a partial ordering in V (the set of vertices form the graph), and partitions the vertices in classes of equivalence that it correspond to equal operator values. For example, 1 is equivalent with 2 by APSΣpnp, with 6,7 and 8 by ΔPSΣpnp, with 2, 6, 7 by ACS and ACSΣpnp∙l(p), with 2, 5, 6, 7 by ACSΣpnp, with 4, 5, 6 and 8 by ΔTSΣpnp.
    All vertices are equivalent by ΔVSΣpnp and DVSΣpnp. Vertex 1 is singulary according to APSΣpnp∙l(p), DPSΣpnp, ΔPSΣpnp∙l(p), ATSΣpnp∙l(p), LDTS, DTSΣpnp, DTSΣpnp∙l(p), LAVS, AVSΣpnp, AVSΣpnp∙l(p), LDVS, DVSΣpnp∙l(p) and LΔVS.
    This example demonstrates the flexibility of sequence matrix criteria in the characterization of various properties of vertices. Let us look at all partial orderings induced in the graph by every sequence matrix.
    LAPS discriminates all vertices for the graph in fig. 1.
    The values obtained by applying Σpnp and Σpnp∙l(p) operators are degenerate in the case of APS.
  • APSΣpnp partitioning V(G) in 5 classes of equivalence: P(V(G), APSΣpnp) = {(3,4), (7,8), (6), (1,2), (5)}.
  • APSΣpnp∙l(p) partitions V(G) in 7 classes of equivalence: P(V(G), APSΣpnp∙l(p)) = {(7), (8), (6), (4), (2,3), (1), (5)}.
    LDPS discriminates all vertices for the graph in fig. 1.
    The values for Σpnp and Σpnp∙l(p) operators are degenerate in the case of DPS.
  • DPSΣpnp partitions V(G) in 3 classes of equivalence: P(V(G), DPSΣpnp) = {(3,4,5), (2,6,7,8), (1)}.
  • DPSΣpnp∙l(p) partitions V(G) in 7 classes of equivalence: P(V(G), DPSΣpnp∙l(p)) = {(8), (6), (4), (7), (5), (3), (1,2)}.
    All vertices for the graph from fig. 1 are discriminated by LΔPS criterion.
    The values for Σpnp and Σpnp∙l(p) operators are degenerate according to ΔPS criterion.
  • ΔPSΣpnp partitions V(G) in 2 classes of equivalence: P(V(G), ΔPSΣpnp) = {(1,6,7,8), (2,3,4,5)}.
  • ΔPSΣpnp∙l(p) partitions V(G) in 7 classes of equivalence: P(V(G), ΔPSΣpnp∙l(p)) = {(3,7), (4), (6), (1), (8), (5), (2)}.
    LATS discriminates all vertices for the graph G.
    The values for Σpnp and Σpnp∙l(p) are degenerate according to ATS.
  • ATSΣpnp partitions V(G) in 3 classes of equivalence: P(V(G), ATSΣpnp) = {(8), (4,5,6,7), (1,2,3)}.
  • ATSΣpnp∙l(p) partitions V(G) in 7 classes of equivalence: P(V(G), ATSΣpnp∙l(p)) = {(4), (7), (6), (8), (3,5), (1), (2)}.
    LDTS partitions the vertices of G in 5 classes of equivalence: P(V(G), LDTS) = {(8), (1), (2,3,5), (4,6), (7)}.
    The values for Σpnp and Σpnp∙l(p) operators are degenerate according to DTS.
  • DTSΣpnp partitions V(G) in 3 classes of equivalence: P(V(G), DTSΣpnp) = {(8), (2,3,4,5,6,7), (1)}.
  • DTSΣpnp∙l(p) partitions V(G) in 5 classes of equivalence: P(V(G), DTSΣpnp∙l(p)) = {(8), (7), (4,6), (2,3,5), (1)}.
    LΔTS discriminates all vertices for the graph in fig. 1.
    The values for Σpnp and Σpnp∙l(p) operators are degenerate in ΔTS criteria.
  • ΔTSΣpnp partitions V(G) in 2 classes of equivalence: P(V(G), ΔTSΣpnp) = {(1,4,5,6,8), (2,3,7)}.
  • ΔTSΣpnp∙l(p) partitions V(G) in 5 classes of equivalence: P(V(G), ΔTSΣpnp∙l(p)) = {(4), (1,3,6,7), (5), (8), (2)}.
    LAVS partitions the vertices of G in 6 classes of equivalence: P(V(G), LAVS) = {(8), (1), (2), (5,6), (3,7), (4)}.
    The values for Σpnp and Σpnn∙l(p) are degenerate in AVS criteria.
  • AVSΣpnp partitions V(G) in 6 classes of equivalence: P(V(G), AVSΣpnp) = {(8), (1), (2), (5,6), (3,7), (4)}.
  • AVSΣpnp∙l(p) partitions V(G) in 6 classes of equivalence: P(V(G), AVSΣpnp∙l(p)) = {(8), (1), (2), (5,6), (3,7), (4)}.
    LDVS partitions the vertices of G in 6 classes of equivalence: P(V(G), LDVS) = {(8), (1), (2), (5,6), (3,7), (4)}.
    The values for Σpnp and Σpnp∙l(p) are degenerate in DVS criteria.
  • DVSΣpnp does not discriminate the vertices of G: P(V(G), DVSΣpnp) = {(1,2,3,4,5,6,7,8)}.
  • DVSΣpnp∙l(p) partitions V(G) in 6 classes of equivalence: P(V(G), DTSΣpnp∙l(p)) = {(4), (3,7), (5,6), (2), (1), (8)}.
    LΔVS partitions V(G) in 7 classes of equivalence: P(V(G), LΔVS) = {(1), (2,6), (5), (4), (3), (8), (7)}.
    The values for Σpnp and Σpnp∙l(p) operators are totally degenerate in ΔVS criteria.
  • ΔVSΣpnp partitions does not discriminate the vertices: P(V(G), ΔVSΣpnp) = {(1,2,3,4,5,6,7,8)}.
  • ΔVSΣpnp∙l(p) partitions V(G) in 6 classes of equivalence: P(V(G), ΔVSΣpnp∙l(p)) = {(3), (4), (7), (2,6), (1,8), (5)}.
    LACS partitions V(G) in 4 classes of equivalence: P(V(G), LACS) = {(8), (1,2,6,7), (5), (3,4)}.
    The values for Σpnp and Σpnp∙l(p) are degenerate in ACS.
  • ACSΣpnp partitions V(G) in 3 classes: P(V(G), ACSΣpnp) = {(8), (1,2,5,6,7), (3,4)}.
  • ACSΣpnp∙l(p) partitions V(G) in 4 classes of equivalence: P(V(G), ACSΣpnp∙l(p)) = {(8), (5), (1,2,6,7), (3,4)}.
    Note that the matrices LAVS and LDVS contain different values, but induce the same ordering " σ " for vertices:
    σLAVS = = σLDVS (σP)
    The property (σP) was verified by a set of various graphs, with different numbers of cycles, edges and vertices. In each case, the LAVS and LDVS criteria induce the same partial ordering for vertices.

    5. Vertices Coloring
    According to the partitions induced and presented in tables 1-10 a graph vertices coloring are making. In colorings, a code color was used. In increasing order of values for selected criteria, the colors used are red, gold, blue, lavender, lime, green and brown. For the partitions that discriminate all vertices no coloring was made.


    Fig. 3. Graph G vertices colorings from fig. 1; partitions: LAPS, APSΣpnp and APSΣpnp∙l(p)


    Fig. 4. Graph G vertices colorings from fig. 1; partitions: LDPS, DPSΣpnp and DPSΣpnp∙l(p)


    Fig. 5. Graph G vertices colorings from fig. 1; partitions: LΔPS, ΔPSΣpnp and ΔPSΣpnp∙l(p)


    Fig. 6. Graph G vertices colorings from fig. 1; partitions: LATS, ATSΣpnp and ATSΣpnp∙l(p)


    Fig. 7. Graph G vertices colorings from fig. 1; partitions: LDTS, DTSΣpnp and DTSΣpnp∙l(p)


    Fig. 8. Graph G vertices colorings from fig. 1; partitions: LΔTS, ΔTSΣpnp and ΔTSΣpnp∙l(p)


    Fig. 9. Graph G vertices colorings from fig. 1; partitions: LAVS, AVSΣpnp and AVSΣpnp∙l(p)


    Fig. 10. Graph G vertices colorings from fig. 1; partitions: LDVS, DVSΣpnp and DVSΣpnp∙l(p)


    Fig. 11. Graph G vertices colorings from fig. 1; partitions: LΔVS, ΔVSΣpnp and ΔVSΣpnp∙l(p)


    Fig. 12. Graph G vertices colorings from fig. 1; partitions: LACS, ACSΣpnp and ACSΣpnp∙l(p)

    6. Conclusions
    The analyzed matrix critters are capable to partitioning vertices in equivalence classes by different properties (i.e. number of paths, length of paths, et all). All criteria give a specific partitioning of vertices, excepting LAVS and LDVS ordering. For LAVS and LDVS criterion, an interesting property result: although the individual matrix values are different, comparison rules match, so that the two matrices induce identical partitioning. Testing on a large set of graphs, the partitioning rule LADS ≡ LVDS remain same. That is a subject for a new theorem that will be proved later. More, all AVS criterion (AVSΣpnp and AVSΣpnp∙l(p) and LAVS) make same partitioning of graph vertices for the given graph G from fig. 1. More, the ordering is the same (see fig. 9). Vertex partitioning can be applied in graph coloring [20], the theory of traffic (lights), distributed electric circuits, computer networks [21], and chemical graphs [22]. Edge partitioning is another problem that can be solved using terminal path structure. For more details about this subject, please consult [23].

    References
    [1]. Liu X., Balasubramanian K., Munk E. M., 'Computational Techniques for Vertex Partitioning of Graphs', J. Chem. Comput. Sci., 30 (1990), 263-269.
    [2]. Skorobogatov A. V., Dobrynin A. A., 'Metric Analysis of Graphs', Commun. Math. Comput. Chem., 23(1988), 105-151.
    [3]. Quenell T., 'Eigenvalue comparisons in Graph Theory', Pacific J. of Math., 176-2(1996), 443-461.
    [4]. Harary F., Schwenk A. J., 'The Spectral Approach to Determining the Number of Walks in a Graph', Pacific J. of Math., 80-2(1979), 443-449.
    [5]. Cheng S.-Y., 'Eigenvalue Comparison Theorems and Its Geometric Applications', Math. Z., 143(1975), 289-297.
    [6]. Basak C. S., R. V. Magnusson, G. Niemi, R. Regal, 'Determining Structural Similarity of Chemicals Using Graph-Theoretic Indices', Discr. Appl. Math., 19(1988), 17-44.
    [7]. Liu X., Balasubramanian K., E. M. Munk, 'Computational Techniques for Vertex Partitioning of Graphs', J. Chem. Inf. Comput. Sci., 30(1990), 263-269.
    [8]. Bersohn M., 'A Matrix Method for Partitioning the Atoms of a Molecule Into Equivalence Classes', Comput. Chem., 11(1987), 67-72.
    [9]. Balaban A. T., 'Local versus Global (i.e. Atomic versus Molecular) Numerical Modelling of Molecular Graphs', J. Chem. Inf. Comput. Sci., 34(1994), 398-402.
    [10]. Lerman M., Soare I. R., 'd-Simple Sets, Small Sets and Degree Classes', Pacific J. of Math., 87-1(1980), 135-155.
    [11]. Dhar D., 'Asymptotic Enumeration of Partially Ordered Sets', Pacific J. of Math., 90-2(1980), 299-306.
    [12]. Dobrynin A. A., 'Degeneracy of Some Matrix Graph Invariants', J. of Math. Chem., 14(1993) 175-184.
    [13]. Dobrynin A. A., 'Cubic Graphs with 62 Vertices Having the Same Path Layer Matrix', J. Graph Theory, 17(1993), 1-4.
    [14]. Balaban A. T., 'Applications of Graph Theory in Chemistry', J. Chem. Inf. Comput. Sci., 25(1985), 334-343.
    [15]. Balaban A. T., 'Solved and Unsolved Problems in Chemical Graph Theory', Annals of Discr. Math., 55(1993), 109-126.
    [16]. Dobrynin A. A., Kochetova A. A., 'Degree Distance of a Graph: A Degree Analogue of the Wiener Index', J. Chem. Inf. Comput. Sci., 36(1996), 1082-1086.
    [17]. Diudea M. V., 'Layer Matrices in Molecular Graphs', J. Chem. Inf. Comput. Sci., 34(1994), 1064-1071.
    [18]. Diudea M. V., Topan M., Graovac A., 'Layer Matrices of Walk Degrees', J. Chem. Inf. Comput. Sci., 34(1994), 1072-1078.
    [19]. Randić M., 'Design of Molecules with Desired Properties (A Molecular Similarity Approach to Property Optimization),' in 'Concept and Applications of Molecular Similarity', Ed. A. M. Johnson, G. M. Maggiora, John Wiley & Sons, 5(1990), 77-145.
    [20]. Exoo G., 'Some New Ramsey Colorings', The Electronic J. of Combinatorics, 5(1998), #R29(1-5).
    [21]. Jntschi L., L. M. Ungureşan, 'Special Chapters of Chemistry for Automatics' (in Romanian), U. T. Pres, Cluj-Napoca, Romania, (2001), 1-202.
    [22]. Diudea M. V., Gutman I., Jntschi L., 'Molecular Topology', Nova Science, Huntington, New York, (2001), 1-332.
    [23]. Jntschi L., 'Graph Theory. 1. Fragmentation of Structural Graphs', Leonardo Electronic Journal of Practices and Technologies, 1 (2002), 19-36.
    Issue 01, p. 53-60

    Loco2000. Technical Characteristics
    Gabriel MOISA
    Technical University Cluj-Napoca

    Abstract
    The paper show the function parameters of locomotive components Loco 2000, putting accent from their maximal values; the mode who works the force circuit, insisting of modulation technique necessary to obtain a high power factor and to eliminate harmonics. Is described the mode in who are realized the speed regulation and the afferent exploitation data. In the ultimate part of work is presenting the operation mode of the command-control MICAS-S2 system, the different commands imposed to others components (of the force circuit) and, in finale, the three diagnostic levels putting in service in case of troubles in system.
    Keywords
    Locomotive characteristics, Command systems, Control systems, European railways.

    1. Introduction
    Loco 2000, Re 4/4 460 type, is began in the trans-alpine transport in 1992 year, on the autumn. Is realized under ABB limited, Zurich and respond to very high exigencies, that: high traction force, necessary to surmount big ramps who reach occasionally 27 , a good curve situate and small maintenance necessity. Is concept to generate minimal network troubles, to use fully the regenerative braking, who the denomination exploitation less of wearing. The locomotive use on the first the principal automatic circuit breaker with vide, developed by ABB, who no necessitate, practically, no maintenance. She uses frequently the regenerative braking, practically to stop, being a little fault of current on the supply under the route that circulates. Being given the entire exploitations exigency from European railways by 15 kV, 16 2/3 Hz, can be adapted on c.c. network by 3000 V, she can circulate very good in others countries than Switzerland.

    2. Technical Description
    The commercial exploitation of this type of locomotives is begun in year 1992 in the autumn. They are realized by ABB Sistmes de Transport SA Zurich from cadre of Federal railroads (CFF). Them are in measure to circulate under ramps by 27, developing a maxim torque by 192 kN∙m. The maxim torque is available at a speed by 88 km/h, situated in proximity of adherence limit. At maxim technique speed, that is reducing under la 83 kN∙m. In her sequence, the axle power oscillates between 6100 and 4800 kW.

    (F-Traction, B-Braking, v-Speed, Z-Axle torque, ZB- Axle braking torque, Zp-Limit of adherence force)
    Figure no 1. Torque-speed diagram of locomotive Re 4/4 460
    The force electric circuit contents the principal transformer, with four independent traction windings, where are racordate, two by two, the frequency static converters. Hereby, in case of defect of a traction system, the train can continue the race at half-power. The GTO thyristors, with a blockage tension by 4.5 kV and a commutation current by 2.5 kA, permit the exploitation of intermediate converter circuit, in coupling so called in three points, with a nominal tension by 3.5 kV. For high powers, is benefiting a high tension in the intermediate circuit and permit the mention of currents between the admissible limits. She offer, such as, the possibility to use some circuit for two-current locomotives, that circulate at continuum current network by 3000 V. Otherwise, is similar with locomotive BB, series 1822. Grace of triple tension levels (0, 50 and 100%), the three points coupling of intermediate circuit offer the advantage of a bigger approximation of sinusoid. In this case, the request in tension of thyristors is not so big and is not need by a series coupling of semiconductor devices between poles. The traction motors are high speeds, with four poles and the armature in court-circuit. The maxim speed is by 4180 rot/min, with a supply frequency by 143 Hz. The motors power in continuum regime is by 1200 kW, at a tension by 2640 V. The admissible overload is Pmax = 1560 kW. The isolation and leakage inductance are geared to the particular exploitation conditions with inverter, by manner that the supplementary inductance for attenuate of harmonics no be necessary. The locomotive uses the regenerative braking as a prime priority. She serves to maintenance of train speed in descent under pant, as energy recuperation, practically to stop. Therefrom is the denomination wearing out exploitation. For protection anti over voltages of short duration, that can produce unexpected uncouples, in the intermediate circuit are integrated protection resistance. These resistance are coupling in case of network wedge, of system disturbs and their critics dynamic phenomenon. The entrance converters (by four quadrants) as the three-phase inverter are constituted by commutations (valve clearances) identical. Each of the two entrance converters is formatted by four identical valve clearances, situated in the secondary of principal transformer. Is practised the synchronous modulation format by 12 network synchronous impulses. The entrance converter modifies the ratio active power-reactive power by variation of width and phase of impulse. The impulses from eight valve clearances are synchronous and shifting, the resulting impulses at frequency by 1600 Hz into primary of principal transformer. Therefore, the current by supply no contain than a harmonics spectre very diminishing. From network a power factor cosφ > 0.95, for powers higher than 50% from the nominal power is obtaining.

    Figure no 2. The principal electric schema of locomotive Re 4/4 460
    Legend for figure 2:
  • DG 1,2 - Bogie I and II (drive unit)
  • A Converter for auxiliary services
  • B The electric circuit of auxiliary services by 220 V
  • C Warming line by 1000 V
  • 1 Pantograph
  • 4 Earth connect circuit breaker
  • 5 Principal circuit breaker of vehicle (rapid with vacuum)
  • 7 Principal transformer
  • 17 Single-phase converter (four quadrants)
  • 20 Traction three-phase asynchronous motor
  • 21.1 Filtration inductance
  • 21.2 Filtration condenser
  • 28 Three-phase inverter
  • 30.2 Condenser from intermediate circuit
  • 30.3 Instantaneous overvoltages limiter
  • 30.4 Afferent resistance
    Each of inverters is formed by three valve clearances, commanded with a postponement by 120 electric degrees. The frequency game is between 0 and 147 Hz and subdivision in three regulation games. In start game, the rapport U/f is maintained constant. The total motor power is touched at 54 Hz (c.c.a. 1600 rot/min, respectively by 88 km/h). In medium game, to 125 Hz (c.c.a. 3650 rot/min, 200 km/h) all of motor maxim power is available. In this case, the current must be decreasing, because of motors slide limit. The synchronisation of GTO thyristors it was chosen in so manner that the current harmonics into motors to be small of all the exploitation game. Therefore, the torque will be also small. The central element of command-control MICAS-S2 system is the serial vehicle bus. Using conductors with optic fibres is possible a transmission speed by 1.1 Mb/sec and can, also, interconnect 256 apparatus address. This vehicle bus transmits the mechanic orders to vehicle command-control apparatus, which are treated and retransmission by bus to component apparatus. It was assuming the functions of superior hierarchy, that: pace speed regulation, calculation of traction and breakage effort values, the allotment between: electric braking, slippers braking and rail electromagnetic braking, effective speed treatment, as well as the surveillance of different limit values. On the other hand, each of the two converter blocs contains the proper bus station, with concordant converter apparatus and the traction command-control. The last is seeing about inverters command and surveillance function of converters. The apparatus receive the command values by means of the vehicle bus. In their sequence, they provide all along the time the effective status of converters to vehicle command-control apparatus. The concordant information exchange is cyclic displaying, with different priorities. From redundancy motives, the important subsystems (bus control, pilot computer, central components) are two-ply, as the bus control. The active control regulates the telegrams traffic, interrogating each bus station by a cyclic program, checking out simultaneous his functions. The intern bus of each locomotive is interconnected with train bus by means of a bridge (alias two communication independent couplers). The signals of train bus are superimposed with command braking signals.

    Figure no 3. The principle schema of command-control installation
    Legend for figure 3:
  • ALG - Traction command-control apparatus
  • BR - Braking computer
  • BS - Bus station
  • BUR - Converter for auxiliary
  • BV - Bus control
  • DT - Diagnostic terminal
  • DV - Diagnostics trait
  • ELS - Electronic cupboard
  • E/A - Entrance/exit
  • SS - Interface
  • StB - Electric command cupboard
  • UR- Converter unity
  • FB - Vehicle bus
  • FIS - Passengers information system
  • Fk Radio FLG - Vehicle command-control apparatus
  • FR - Pilot room
  • HB - Auxiliary services block
  • MPR - Diagram MICAS computer
  • MR - Machine room
  • PT - Pneumatic keyboard
  • SLG - Converters command-control Apparatus
  • v-M - Installation for speed measurement
  • ZB 1 - Train bus 1 (EP line)
  • Zb 2 - Train bus 2 (UIC line)
  • ZMS - Communication coupling
  • ZS - Security system
  • ZUB - Train surveillance
    All troubles signs and correspondent messages are pre-programmed in microcomputers decentralised of command-control level. These intimate the possible divergences by behaviour report imposed in their correspondent sector and transmit the information to trait diagnostics of the vehicle apparatus. Her memory, non-volatile, has a capacity by 2500 messages. The treatment of troubles of messages is making fewer than three levels. In case of a non-correspondence, a lamp is switching on in front of mechanic. The short messages and the instructions are display on the screen, which is normally black. By action of a debugger button, the mechanic can be ignored, set out of command desk and parts of installations very disturbed. The second level is intended for little maintenance. Aid of simplified keyboard beside screen, can be interrogate the diagnostic trait apparatus, the registered trouble message appearing on the screen. The three level serves at deepen examination of troubles and the statistic trait of events. All the data are load by portable PC sand transferred in a central data bank. In case of multiple commands, the different diagnostic systems form independent unity and the trouble messages are visualisation by means of train bus. As well as is, the visualisation the messages derived by coaches too.

    3. Conclusions
    Less of his performances, mention in this paper, is desirable that the power factor and the efficiency to be ameliorated. From this reason, is necessary a detailed study, theoretical and practical, in different situations: climbing and descent of ramps, the half-function (with a single supply bogie) and, why not, the regenerative braking tentative to stop (of train), earn to be surveyed.

    References
    [1] Jrg Ltscher, Paul Schlpfer Loc 2000, Revue ABB 10/92.
    [2] Gerber, M.; Drabek,E; Mller,R Die Locomotiven 2000, Serie 460, der Schweizerischen Bundesbahnen, Schweizer Eisenbahn Revue 10/1991.
    [3] Weiss, T. Die Lokomotive 2000 der Schweizerischen Bundesbahnen, 89 (1991) 11.
    [4] Bonani, R. Die elektrischen Locomotiven Re 4/4 der BT un der SZU mit Drehstrom Antriebstechnik.
    [5] Kummrov, R.; Vitins, J. Die Typefamilie Lok 2000. ZEV-Glasers Annalen 116 (1992) 9/10.
    [6] Locomotives convertisseur avec entranement triphas pour le Rseau Express Rgional Zurich, Revue ABB 10/90.
    Issue 01, p. 61-68
    Le Shuttle, the locomotive from Eurotunnel
    Gabriel MOISA
    Technical University Cluj-Napoca

    Abstract
    This paper present some performances of locomotive Le Shuttle, so-called locomotive from Eurotunnel, techniques characteristics of traction motors 6 FHA 7079 and converters witch use it, the principal electric scheme and its function principle and no at last rind the principle scheme of command-control equipment MICAS-S2 with detailed description of its operation mode.
    Keywords
    Locomotive characteristics, Command systems, Control systems, European railways.

    1. Introduction
    Euroshuttle Consortium Locomotives put in traffic in year 1994 on the summer 38 locomotives from this series intended to support the different performances: for obtain exceptional traction effort, bred power and a optimum load axle, a weak wearing out on the wheels, but by a maximal availability, was chosen the formula with three bogie at two axle, provided with proper converter. The progress realized in the fabrication of thyristors GTO and command-control techniques assisted by microcomputer was resented since of construction on the first polyvalent locomotives Re 456. The command system MICASS2 based on logic, anterior was used on the high-speed locomotives Loc. 2000. Excepting of their predecessors, the principal transformer was conceived in a particular manner by compact type. Locomotives from this series, answers on extreme severe exigency: safety in case of wrecks, rigorous observance of timetable, redundancy, optimum traffic frequency, and big reliability.

    2. Technical Description
    In year 1994 on the summer, Euroshuttle Consortium Locomotives put in traffic 38 locomotives from this series. Because of: slashing conditions of exploitation like: big towed weight (coaches and car transportation trucks), air pressure exerted in the tunnel (Eurotunel), the locomotives had an axle disposition type BoBoBo, provided with a proper converter for each motor bogies. For Le Shuttle was realized a force circuit less sophisticated who used frequency static converters in three points circuits. The converters are purely with two interchangeable tension levels, with less of semiconductor elements. The locomotive is powered by single-phase alternating current, with 25 kV tension and 50 Hz frequency. The maxim shaft power touch 5600 kW, the maxim torque 400 kN∙m and maxim voyage speed 160 km/h, in accord of air pumping and the tunnel ramps.

    (F-Traction; B-Braking; v-Speed; Z-Active torque; ZB-Breaking torque)
    Figure no 1. Torque-speed diagram of locomotive Le Shuttle
    The traction motors have six poles, thick bares, isolation class H and forcible ventilation. The motors touch the maxim speed at 139 Hz and 2180 V like effective value. The nominal apparent power is 960 kW at 1100 rot/min. The electric energy was assumed from alternating current mains by two asymmetric pantographs, which were attached at a direction reverse situated under the principal vacuum circuit breaker, who supply the principal transformer.

    Figure no 2. The principal electric scheme of locomotive
    Legend:
  • 1 - Pantograph;
  • 2 - Pantographs section;
  • 5 - Principal automatic circuit-breaker of vehicle (with vacuum) with interrupter for earthling;
  • 7 - Principal transformer;
  • 9 - Thunderrod;
  • 11.0 -Traction frequency converter;
  • 12/1,12/2 - Network single-phase converter 1 and 2;
  • 12/3 - Three-phase inverter, 1 and 2 phases;
  • 12.1 - Contactor for coupling the resistance from position 14;
  • 12.2 - Section contactor;
  • 13 - Three-phase inverter (3-nd phase) and instantaneous tension limiter;
  • 14 - Resistance for striking current limit;
  • 15.2 - Resistance of instantaneous tension limiter;
  • 15.3 - The coil of smoothing circuit;
  • 15.4 - The condenser of smoothing circuit;
  • 15.5 - The condenser of intermediate circuit;
  • 20 - Traction three-phase induction motor;
  • A -Frequency converter for auxiliary services;
  • C - Converter of train collector bar;
  • DG - Bogie.

    The six secondary windings (identical) for motors supplying are galvanic separated. The motoring bogies are independent carrying away. Each of the two motors that compose a bogie was supplied by means of proper converter, which are commanded and coordinatessed by means of vehicle commander appliance, from the vehicle driven level. Each system current converter of the three traction converters was supplied by means of single-phase rectifier at full wave by two separated windings of the transformer. By precise command of ignition angle and frequency modulation of the pulses was obtain a power factor between 0.98 inductive and 1. The current supplies converter the intermediate circuit by continuous tension situated between 2.4 and 2.8 kV, in accord of load torque. In case of an overvoltage (fault on a line), a GTO thyristor introduce in circuit a big power resistance. That particularity is important already in case of regenerative braking, when could be surpassed the maxim admit tension in intermediate circuit. The frequency modulation principle is applied until the flux weackage are beginning. Therefore, at big speed the GTO thyristors conduct at an appropriate half-wave. The thyristors bridges from power supply system and traction of the converter are specific to regulation in two points, which allow the optimum simulation of a sinusoidal wave. All the GTO function status is commanded by means of logical command appliance of the converters (SLG). In cadre of MICAS-S2 system, the control and command functions are assured by means of computer, which command apparatus vehicle logic works (FLG). Accordingly, the different commands are direction to station bus compacted, where is controlled the retransmission messages reception too. If was selected, for example, a constant speeds, the instruction calculus the request torque and transmits the value to traction converters. The traction command apparatus (ALG) from different traction units determine arious parameters and ignition angles of GTO thyristors, necessary for elaboration of torque impose by FLG. At the same time, the ALG control the observance of exploitation conditions (temperature and currents) and take itself the protection functions that appertain on this level. ALG and SLG logic is peeling faster than FLG logic. The two locomotives and wagons are interconnection by two data buses. This bus work beyond multiple transmissions by frequency shift principle. So that, the two locomotives can by commanded and diagnosed setting out since driven locomotive.

    Figure no 3. The scheme by principle of command-control equipment
    Legend:
  • ALG - traction command apparatus;
  • ATO - pace automaton command;
  • ATP - train automaton surveillance;
  • BRI - calculator-braking interface;
  • BUR - command apparatus of converter frequency supply;
  • BV - bus controller;
  • DR- diagnostic computer;
  • DT- diagnostic terminal;
  • E/A - input/output interface;
  • FB - vehicle bus;
  • FLG - vehicle command-control apparatus;
  • FR - computer of pilotage cabin;
  • FST- engine driver's room;
  • MPR - Micas visualisation system;
  • MR - machine room;
  • NSL - multiple emergency command line (6 conductors);
  • RA - radio installation;
  • RC - radio command;
  • SLG - converter command apparatus;
  • SR - traction converter;
  • SSB - command currents block;
  • V-M - tachometric installation;
  • VR - vestibule room;
  • WBI - wagon bus interface;
  • ZLB - loc-loc bus;
  • ZMS - multiple commands on time multiplexer;
  • ZWB - wagon bus.

    The connection loc-loc bus and wagon bus is established by means of traction automate coupling by pressure. The command modules are supplied at 110 V permanently, by locomotive battery. Before of switching, the system receive a test routine before than the inquiry sequence is beginning. The command and regulating parameters are sticking on the monitor in the driven cabin. The diagnostic functions are organised by three levels: the first level include locomotive leaders message and instruction; the second level message and instruction settle the messages list memorised at overheads personnels intention and the last provide assistance for detailed tracking of troubles. In ALG are integrated the antiskating and antisliding functions of different traction units. In centre of antisliding protection is finding a motor torque command, very sensible, with a reaction time of milliseconds order. If the system observes some axle packing, the torque is reduced la until 40 %, according to the sliding conditions, by means of tension high frequency chopping. The adaptive algorithms assure a correct behaviour in every exploitation conditions. The requested electric braking torque regulation is transmitted between the locomotives by means of loc-loc bus. The electric and pneumatic braking is combined. The command algorithms of skating status ASM supervise in order that was provided a balanced braking effect, less of current shocks. 3. Conclusions Due to performances remembered in this paper and in the introductory part of work, is worth an thoroughgoing study by this locomotive in different situation: start, acceleration, pace, breakage, load, being therewith an interest in his implementation in our country Romania too, account of his working parameters: 25 kV/50 Hz on pantograph, identical with nationals parameters.

    References
    [1] Eggenberger, H.-P., Treacy, R.: Revue ABB 4/1994.
    [2] Streiff, H.: La locomotive BoBoBo serie 6/6 des Chemin de fer federaux suisses, Revue Brown Boveri, 64/1977.
    [3] Balzarini, G., Haller, B.: Les nouvelles locomotives de ligne re 4/4 du Chemin de fer BT et du Chemin de fer SZU, Revue Brown Boveri, 74/1987.
    [4] Eggenberger, H.: Locomotives a convertisseurs avec entrainement triphase pour Reseau Express Regional Zurich, Revue ABB, 10/90.
    [5] Galliker, F.: Bauformen der ABB-Fahrmotoren fur alle kommenden Zugforderungsaufgaben, ABB Systemes de transport SA, Zurich, imprime CH-B 0940 D.