Graph Theory of Free Radicals Validation of a Recent Assertion and Its Relation to the Pairing Theorem BY COLINL. HONEYBOURNE Physical Chemistry Laboratories, The Polytechnic, Ashley Down, Bristol 7 Received 1st May, 1975 The criteria for the occurrence of a symmetric eigenvector in odd graphs are deduced ;these con- firm the validity of a recent assertion concerning the cause of such an eigenvector. The relationship to the Coulson-Rushbrooke Pairing Theorem is noted. In a recent paper it was asserted that those odd graphs of N vertices having an unmarked unvalued starred partial graph display a spectrum containing an eigenvector such that the coefficients at all unstarred vertices are zero and those at all starred vertices have the value kG*where 8 = (N+ 1)/2.The adjective "symmetric " was chosen to describe eigenvectors of this type which proved extremely important in discussing the behaviour of the odd a-electron in free radica1s.l The purpose of this paper is to demonstrate the validity of the proposed relationship between the occur- rence of a symmetric eigenvector and a starred partial graph that is unmarked and unvalued. The terminology to be used is closely allied to that adopted by Longuet- Higgins in his paper concerning the eigenvalue problem of alternant hydrocarbons.2 Although the general form of the work presented below is similar to that used in discussions of the Coulson-Rushbrooke Pairing Theorem 2* 4* (CRT), it is em- phasised that symmetric eigenvectors can arise in graphs which do not obey the CRT, and frequently do not arise in graphs which do obey the CRT.THEORY A PROPERTY OF CERTAIN MATRICES Attention is drawn to the following property of the characteristic polynomial of matrices which can be factored into a particular blocked form. Consider a matrix of dimension N x N (where N is odd) which has a leading diagonal block A* (see fig. 1) of dimension G x G with a set of equal diagonal elements, a*, and off diagonal elements of zero. The detailed forms of the blocks B, B and A" will be considered later because they do not affect the present argument. The diagonal form and dimensions of A* dictate that the characteristic polynomial, f(~),tlways contains a factor (a* -E) regardless of the values of the matrix elements in B, B and A".Thus one eigenvalue, and the associated eigenvector, of such a matrix may be determined with particular ease. ADJACENCY MATRICES OF ODD ALTERNANT GRAPHS An alternant graph is one which may have alternate vertices distinguished by a star with no two starred vertices being adjacent to each other.2* It has become 34 C. L. HONEYBOURNE 35 customary to apply the adjective " alternant " only when all vertices are unmarked and all edges are equally valued ;such graphs obey the CRT (e.g., the alternant hydro- carbons). However, in this work we will apply the adjective &' alternant " to any framework for which the starring criterion holds whether it be unmarked and unvalued marked (0-o-o-o-o),(0-0-0-0-o), valued (o---o-o-o---o) or marked and valued (0-0--0--0-0).The adjacency matrix of a bipartite graph has non-zero matrix elements for vertices and edges and matrix elements of zero elsewhere. The adjacency matrix, M, of any odd alternant graph may be partitioned into blocks as shown in fig. 1. If A* is to have the form required to exploit the property described above, then all starred vertices must be equally marked (i.e., with a*). A" is diagonal with diagonal elements FIG.1. at,,(v = G+ 1, G+2, . . .,N) and B and B have zero matrix elements except for edges connecting adjacent starred and unstarred vertices. The CRT holds 2* when all the a;" = a* ;there are no restrictions on the magnitude of non-zero elements in B or B.6 In what follows the restriction on the matrix elements a;,, is lifted; these may be unequal to a* and to each other.Further, the restriction is imposed that all non- zero elements in B and B take the same value. Clearly, the characteristic polynomial of M has at least one solution Ej = a* if A* takes the prescribed form. THE STARRED PARTIAL GRAPH Odd alternant graphs relevant to n-electron free radicals may contain vertices of degree a, b or c1 according as that vertex is connected to 1, 2 or 3 other vertices. The starred partial graph, G* of an odd graph G is assembled from the starred vertices in G and new edges of type A, B or C1according as the omitted unstarred vertices are of degree a, b or c. In order that the adjacency matrix A4of G should contain a block A* it is sufficient that G*should be unmarked ;i.e., all starred vertices in G must be identically marked. The criterion specified for B and B indicates that G must be unvalued.Thus, .-@-.-o-e has the required form whereas 0-0-0-0-0and 0---0-~-0 ---0 do not. The connectedness of the vertices in G will determine the form of B and B,the valuing of the edges in G*, and the form of the secular equations. In what follows we will show that G must only contain unstarred vertices of degree b in order that the eigenvalue cj = a* is associated with a " symmetric " eigenvector -this then determines that if G* is unvalued as well as unmarked a symmetric eigenvector does occur. GRAPH THEORY OF FREE RADICALS LINEAR ODD ALTERNANT GRAPHS The adjacency matrices of those odd linear graphs that are unvalued and equally marked at all starred sites have the general form 0 I I 1 I 0 \ \ I \ \ I \\ I M= 0 \'\ \' \ '\ I I 1 I ! 'a* I a* ! P FIG.2.where all non-zero elements in B and B are given the value j. We find that the characteristic polynomial, J(E),of the secular determinant D of A4 is given by 6 where the dk(&)are formed by striking out the first k rows of D, the single kth column of the starred block, and the first (k-1) columns of the unstarred block ;we refer to the subdeterminant obtained from A* and B as the starred block and to that from A" and B as the unstarred block. The secular equations given below have the following terminology: p, A, cr) are running indices for starred vertices, v, IC, z are running indices for unstarred vertices and j labels the eigenvalue with the corresponding eigenfunction coefficients being labelled cy, or c;~.(a* -Ej)CTl +flc;2 =o These equations determine that, for Ej = a*, all coefficientsat unstarred vertices (the cgy)are zero and that all other coefficients have the value _+awhere the normalisation condition determines that a = /-*. The eigenvalue E~ = a* is a consequence of (i) the alternant nature of the odd graph and (ii) the identical marking at all starred vertices. C.L. HONEYBOURNE The symmetric form of the eigenvector (Lee, c:: = cy2N--Q+ is a further consequence of all uiistarred vertices being of degree b, thereby generating the relationships cTp = 3-CTL.Clearly the above criteria may be summarised in the statement that “ the starred partial graph must be unmarked and unvalued ”. NON-LINEAR ODD ALTERNANT GRAPHS The criteria for the occurrence of at least one solution of the form E~ = u* have already been discussed. A detailed examination of the various types of secular equa- tion is necessary to determine the general criterion for the solution E~ = a* to be associated with a symmetric eigenvector. The deduction of the general criterion proceeds stepwise as follows : starred site (degree a) (a” -Ej)qfl + starred site (degree b) pqv+(a” -Ej)CYP +pi”, =o (11) starred site (degree c) pcyv+(a” -Ej)CYP +pcj9,+ = 0 (111) unstarred site (degree b) flcj*,+(a&-~JciD, +acj*, =o (W unstarred site (degree c) flcx +(a:v -cj)cjOv-tSc?, +Pc& = 0 (V) unstarred site (degree a> pcyp+(a:” -.sj)cj”y =o (W (i) All odd alternant graphs have at least one secular equation of type I from the convention that the number of starred vertices is >d.Hence, at least one of the csv (say, cjo2) is always zero. (ii) This particular unstarred vertex must be of degree b or c to which secular equations of type IV or V apply respectively. Type IV propagates the required rela- tionship (cY1 = -&, say) whereas Type V destroys any such relationship except for the trivial case of all coefficients being zero. The only sequence of interest is that beginning *-o-*. . .. 1231234 123 o4 (iii) The three possible sequences are *-o-*,*-o-*-o... . and *-o-*/ . \05 All three give = -cy3, with cj”2 = 0; the second gives c’j4 = 0 as a consequence of being linear. If the latter is to be incorporated into a larger graph, then vertex 4 is of either degree b or degree c; only the first of these propagates the relationship of the general form cyP = +cj*,, because the unstarred site of degree c gives cTp+cya+ cya = 0. The third possible sequence mentioned above may either be the final sequ- ence or be incorporated into larger graphs with vertices 4 and 5 in sites of various degrees of connectedness -these will be dealt with below. (iv) If the third possible sequence is final, then it must be relabelled o-*-o/*\* GRAPH THEORY OF FREE RADICALS and the presence of a secular equation of type V prevents the occurrence of cyp = rfI.$A. *7 4/ 12 ”0 \(v) If vertices 4 and 5 are both of degree b (Le., *-o--* 1 0 5\ *6 then IC;~~ = Icy?] = lty61 = lcj*,l and cj2 = c;4 = cj”6 = 0as required. (vi) If one site is of degree n (say 4) and one of degree b we have cj2+cj4+c;~= 0 and pc73+c;4(a24-~j) = 0. If az4 # a* then c74 # 0 and if ai4 = a* then c;~= c:3 = 0 ;in both instances the symmetry relation is destroyed. The occurrence of an unstarred vertex of degree a is not possible in. a Kekul6 structure of a n-electron mono- radical. (vii) If one or both of vertices 4 or 5 are of degree c the required relationship cannot occur [see (ii) and (iii) above]. (viii) Any extension of the graph only introduces cases already considered.(ix) In all the cases where the relationship cyp = +cyA is propagated, all unstarred vertices are of degree b; whenever this relationship is not propagated, at least one vertex is not of degree 6. (x) Therefore, if an unmarked starred partial graph is unvalued, the eigenvalue E~ = a* of the related complete graph will be associated with a symmetric eigenvector. A consequence of the above deduction is that a symmetric eigenvector cannot occur in odd alternant cyclic systems. These must contain even-membered rings attached to one (or three. . .) odd-membered side chains which automatically gene- rates an unstarred vertex of degree c in either the ring (e.g., benzyl) or the side chain (e.g., iso-propenyl phenyl).A symmetric eigenvector does occur in, say, trivinyl- methyl or divinyl butadienyl methyl and allied appropriately star-marked systems obtained during discussions of the effect of the odd unpaired e1ectron.l Inspection of secular equation (IV) shows that if, in contrast to the foregoing, # /IvA,the required symmetry property cyp = & cy~is not obtained. Although the pair of edges at a given unstarred vertex of degree b must therefore have the same value, this value can differ from that assigned to any other pair of such edges. The restriction imposed on the non-zero matrix elements in B and B can be partially lifted. CONCLUSION It has been shown that, for there to be an eigenvector with zero coefficients at unstarred vertices and with coefficients of -t [(N+ 1)/2]-* (i.e., +t-*)at all starred vertices, then a graph G of N vertices must be (i) odd, (ii) alternant with respect to the starring criterion, (iii) equally marked at all starred vertices, (iv) contain unstarred vertices of degree b only, (v) have identically valued edges at a given unstarred vertex.Criteria (i)-(iv) are commensurate with the requirement that the starred partial graph G* be unmarked and unvalued as asserted previously.’ Criterion (v) does not pre- clude the requirement that G* shall be unvalued because it is the degree of an unstarred vertex in G that determines the valuing of G*.I The Coulson-Rushbrooke Pairing Theorem does not demand criteria (iv) and (v) but does demand that (vi) all vertices be equally marked [this includes (iii) but is more C.L. HONEYBOURNE restrictive]. In recent work unvalued graphs which fulfil (i)-(iv) and (vi) were classi- fied as I(CR) and those fulfilling only (i)-(iii) and (vi) were classified as II(CR). Those graphs which do not obey the pairing theorem, but which do exhibit a symmetric eigenvector in their spectrum, are obtained by identically marking I(CR) graphs at all starred vertices and marking unstarred vertices at random. Extensive valuing can also occur provided that criterion (v) is complied with. The value of j in cJ = a* has not been investigated although it has been found (and asserted) in earlier work thatj = G. In odd alternant hydrocarbons j = 6' by the CRT, and j = G in recent work on perturbed free radicals in which, in units of the standard Hiickel beta, p = 1 and either CI* = 0 and a:,, = 1 or 0, or a* = 4/(N+1) and aiv = 0.l In both categories the perturbation imposed does not alter the sym- metries of the highest doubly filled, partially filled and lowest empty orbitals from those observed in the parent hydrocarbon.A Referee is thanked for calling attention to recent relevant work on graph theory, Recent Advances in Graph Tt2eory (Academia, Prague, 1975). C. L. Honeybourne, J.C.S. Faraday II, 1975, 71, 1343, H. C. Longuet-Higgins, J. Chem. Phys., 1950, 18, 265. C. A. Coulson and G. S. Rushbrooke, Proc. Camb. Phil. SOC.,1940, 36, 193. C. A. Coulson and H. C. Longuet-Higgins, Proc. Roy. Soc. A, 1947,192,16. A. Graovac, I. Gutman, N. TrinajstiC and T. ZivkoviC, Theor. Chim. Acta, 1972, 26, 27, and references therein. L. Salem, The Molecuiar Orbital Theory of Conjugated Systems (W. A. Benjamin, New York, 1975), p. 37. (PAPER 5 1813)