Graph Theory.
1. Fragmentation of Structural Graphs
Lorentz JÄNTSCHI
Technical University Cluj-Napoca
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.
t = (v_{i})_{1≤i≤n} is named terminal path if: v_{i} Î V, t Î P(G) and "v Î V s. th. (v_{n}, v) Î E then t È (v_{n}, v) Ï P(G) |
(1) |
The set of terminal paths in G is T(G) = (T(G)_{v})_{v}_{Î}_{V} where T(G)_{i} is:
T(G)_{i} = {t = (v_{i})_{1≤i≤n} s. th. v_{1} = i and t terminal path} |
(2) |
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:
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} |
(3) |
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.
CJ_{i,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 Î P_{k,i} s. th. p Ç q = {i} |
(4) |
The set of sets of vertices CJS_{i,j} = {CJ_{i,j,p }: pÎP(G)_{i,j}} are named set of CJ sets of i vs. j.
CJDi_{i,j,p} = {k : k Î V} is named CJDi set of i vs. j and p if: CJDi_{i,j,p} Î CJS_{i,j} l(p) = d(G)_{i,j} |
(5) |
The set of sets of vertices CJDiS_{i,j} = {CJDi_{i,j,p} : p Î P(G)_{i,j}} are named set of CJDi sets of i vs. j.
CJDe_{i,j,p} = {k | k Î V} is named CJDe set of i vs. j and p if: CJDi_{i,j,p} Î CJS_{i,j} l(p) = δ(G)_{i,j} |
(6) |
The set of sets of vertices CJDeS_{i,j} = {CJDe_{i,j,p} | p Î P(G)_{i,j}} are named set of CJDe sets of i vs. j. CJDi^{M}_{i,j} = {s : s Î CJDiS_{i,j}} is named CJDi^{M} set of i vs. j if l(s) = max{ |cjdi| : cjdi Î CJDiS_{i,j}}. CJDe^{M}_{i,j} = {s : s Î CJDeS_{i,j}} is named CJDe^{M} set of i vs. j if l(s) = max{ |cjde| : cjde Î CJDeS_{i,j}}. The sets CJDi can be constructed as follows:
CJDi_{i,j,p }= Æ; CJDi_{j,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 CJDi_{i,j,p }= CJDi_{i,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 CJDi_{j,i,p }= CJDi_{j,i,p} È {v}; EndIf; EndFor; |
(7) |
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:
CJDiS^{M}_{i,j} Í CJDiS_{i,j} Í CJS_{i,j} and CJDeS^{M}_{i,j} Í CJDeS_{i,j} Í CJS_{i,j} |
(8) |
that are obviously from the definitions (4)-(6). Figurative, inclusions are:
Fig. 2. Inclusions relations in CJ sets
Note that in generally the sets CJDiS^{M}_{i,j}, CJDiS_{i,j}, CJS_{i,j}, CJDeS^{i,j}, CJDeS^{M}_{i,j} are not distinct; more, in trees the sets are equals.
To prove that the sets CJDiS^{M}_{i,j}, CJDiS_{i,j}, CJS_{i,j}, CJDeS^{i,j}, CJDeS^{M}_{i,j} are not banal, let’s apply the algorithm (7) to construct sets for graph G from fig. 1.
Following example shows that sets CJDiS^{M} and CJDeS^{M} are not identically:
CJDiS^{M}_{1,2} = {CJ_{1,2,[1,2]}}; CJ_{1,2,[1,2]} = {1, 3, 6, 8}
CJDiS^{M}_{2,1} = {CJ_{2,1,[2,1]}}; CJ_{2,1,[2,1]} = {2, 4, 7}
CJDeS^{M}_{1,2} = {CJ_{1,2,[1,3,6,7,4,2]}}; CJ_{1,2,[1,3,6,7,4,2]} = {1}
CJDeS^{M}_{1,2} = {CJ_{2,1,[2,4,7,6,3,1]}}; CJ_{2,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:
CJDiS^{M}_{4,8} = {CJ_{4,8,[4,7,6,8]}}; CJ_{4,8,[4,7,6,8]} = {1, 2, 4, 5}
CJDiS^{M}_{8,4} = {CJ_{8,4,[8,6,7,4]}}; CJ_{8,4,[8,6,7,4]} = {8}
CJDeS^{M}_{4,8} = {CJ_{4,8,[4,2,1,3,6,8]}}; CJ_{4,8,[4,2,1,3,6,8]} = {4, 5, 7}
CJDeS^{M}_{8,4} = {CJ_{8,4,[8,6,3,1,2,4]}}; CJ_{8,4,[8,6,3,1,2,4]} = {8}
and graphical representation of them are in fig. 4:
Fig. 4. CJDi_{4,8,[4,7,6,8]} and CJDe_{4,8,[4,2,1,3,6,8]} sets for graph G from fig. 1
The following example shows that sets CJDiS^{M} can contain more than one set:
CJDiS^{M}_{2,8} = {CJ_{2,8,[2,4,7,6,8]} = {1, 2, 5}, CJ_{2,8,[2,1,3,6,8]} = {4, 2, 5}};
CJDiS^{M}_{8,2} = {CJ_{8,2,[8,6,3,1,2]} , CJ_{8,2,[8,6,3,1,2]}}; CJ_{8,2,[8,6,3,1,2]} = CJ_{8,2,[8,6,7,4,2]} = {8};
and graphical representation of them are in fig. 5:
Fig. 5. CJDi_{2,8,[24768]} and CJDi_{2,8,[21368]} sets of graph G from fig. 1
4. G_{p} Subgraph
Let p = (i = v_{1}, …, v_{l(p)} = j) Î P(G) a path starting from vertex i and ending in vertex j. The G_{p} subgraph of graph G and path p is defined by:
G_{p} = (V_{p}, E_{p}), V_{p} = {v Î V : v Ï p\{i, j}}, E_{p} = {e = (e_{a}, e_{b}) Î E : e_{a}, e_{b} Ï p\{i, j}} |
(9) |
Note that G_{p} 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, G_{p} 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. G_{p} 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 G_{p} È 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 G_{p}
G_{p} = (V_{p}, E_{p}), V_{p} = {1, 2, 6, 7, 8}, E_{p} = {(1,2), (6, 7), (6, 8)}
Note that G = G_{p} È 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.
CF_{i,j,p} = {k : k Î V} is named CF fragment of i vs. j and p if: d(G_{p})_{k,i} < d(G_{p})_{k,j} |
(10) |
where subgraph G_{p} is obtained from graph G and path p according to definition (9).
Note that in definition (10) is used term of fragment for CF_{i,j,p}. Indeed, CF_{i,j,p} is an fragment, a connected set of vertices from graph G.
The set of sets of vertices CFS_{i,j} = {CF_{i,j,p }: p Î P(G)_{i,j}} are named set of CF sets of i vs. j.
More, in CFS_{i,j,p} fragment, there exist the relation:
"kÎCFS_{i,j,p}, $qÎP(G_{p})_{k.i} path from k to i in G_{p} s. th. qÇp = {i} |
(11) |
Similar to definitions (5) and (6), CFDi and CFDe fragments are defined:
CFDi_{i,j,p}={k : kÎV} is named CFDi fragment of i vs. j and p if: CFDi_{i,j,p} Î CFS_{i,j} l(p) = d(G_{p})_{i,j} |
(12) |
The fragments set CFDiS_{i,j} = {CFDi_{i,j,p} : p Î P(G)_{i,j}} are named set of CFDi fragments of i vs. j.
CFDe_{i,j,p}={k : kÎV} is named CFDe fragment of i vs. j and p if: CFDe_{i,j,p} Î CFS_{i,j} l(p) = δ(G_{p})_{i,j} |
(13) |
The fragments set CFDeS_{i,j} = {CFDe_{i,j,p} : pÎP(G)_{i,j}} are named set of CFDe fragments of i vs. j. CFDi^{M}_{i,j} = {f : f Î CFDiS_{i,j}} is named CFDi^{M} fragment of i vs. j if l(f) = max{ |cfdi| : cfdi Î CFDiS_{i,j}}. CFDe^{M}_{i,j} = {f : f Î CFDeS_{i,j}} is named CFDe^{M} set of i vs. j if l(f) = max{ |cfde| : cfde Î CFDeS_{i,j}}. The sets CFDi can be constructed as follows:
CFDi_{i,j,p }= Æ; CFDi_{j,i,p }= Æ; For (v = 1; v ≤ |V|; v++) If (d(G_{p})_{v,i} < d(G_{p})_{v,j}) then CFDi_{i,j,p }È= {v}; EndIf; If (d(G_{p})_{v,j} < d(G_{p})_{v,i}) then CFDi_{j,i,p }È= {v}; EndIf; EndFor; |
(14) |
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:
CFDiS^{M}_{i,j} Í CFDiS_{i,j} Í CFS_{i,j} and CFDeS^{M}_{i,j} Í CFDeS_{i,j} Í CFS_{i,j} |
(15) |
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 CFDiS^{M}_{i,j}, CFDiS_{i,j}, CFS_{i,j}, CFDeS^{i,j}, CFDeS^{M}_{i,j} are not banal, let’s apply the algorithm (14) to construct sets for graph G from fig. 1.
Following example shows that sets CFDiS^{M} and CFDeS^{M} are not identically:
CFDiS^{M}_{1,2} = {CF_{1,2,[1,2]}}; CF_{1,2,[1,2]} = {1, 3, 6, 8}
CFDiS^{M}_{2,1} = {CF_{2,1,[2,1]}}; CF_{2,1,[2,1]} = {2, 4, 7}
CFDeS^{M}_{1,2} = {CF_{1,2,[1,3,6,7,4,2]}}; CF_{1,2,[1,3,6,7,4,2]} = {1}
CFDeS^{M}_{1,2} = {CF_{2,1,[2,4,7,6,3,1]}}; CF_{2,1,[2,4,7,6,3,1]} = {2}
and graphical representation of them are in fig. 3:
Fig. 8. CFDi_{1,2,[1,2]} and CFDi_{1,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:
CFDiS^{M}_{4,8} = {CF_{4,8,[4,7,6,8]}}; CF_{4,8,[4,7,6,8]} = {1, 2, 3, 4, 5};
CFDeS^{M}_{4,8} = {CF_{4,8,[4,2,1,3,6,8]}}; CF_{4,8,[4,2,1,3,6,8]} = {4, 5, 7};
CFDiS^{M}_{8,4} = {CF_{8,4,[8,6,7,4]}} = {{8}} = {CF_{8,4,[8,6,3,1,2,4]}} = CFDeS^{M}_{8,4}
and fragments are depicted in fig. 9:
Fig. 9. CFDi_{4,8,[4,7,6,8]} and CFDe_{4,8,[4,2,1,3,6,8]} fragments of graph G from fig. 1
The following example shows that sets CFDiS^{M} can contain more than one fragment:
CFDiS^{M}_{7,1} = {CF_{7,1,[7,4,2,1]} , CF_{7,1,[7,6,3,1]}};
CF_{7,1,[7,4,2,1]} = {6, 7, 8}; CF_{7,1,[7,6,3,1]} = {4, 5, 7}
and graphical representation of them are in fig. 10:
Fig. 10. CFDi_{7,1,[7,4,2,1]} and CFDi_{7,1,[7,6,3,1]} fragments of graph G from fig. 1
The Szeged (SzDi) fragments are defined by:
SzDi_{i,j} = {k : k Î V} is named SzDi fragment of i vs. j if: d(G)_{k,i} < d(G)_{k,j} |
(16) |
The SzDi sets are connected subgraphs (fragments). Looking at (5) and (16) definitions, is easy to observe that:
CJDi Í SzDi, |
(17) |
and also:
CFDi Ë SzDi, |
(18) |
The following construction collects the fragments SzDi for all i and j pairs of vertices:
For (i = 1; i < |X|; i++) For (j = i + 1; j ≤ |X|; j++) SzDi_{i,j }:= Æ; SzDi_{j,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 SzDi_{i,j} È= {v}; EndIf; If dvi > dvj then SzDi_{j,i} È= {v}; EndIf; EndFor; EndFor; EndFor; |
(19) |
A graphical example of SzDi fragments for vertices 2 and 6 and graph G from fig. 1 is depicted in fig. 11:
Fig. 11. SzDi_{2,6} and SzDi_{6,2} fragments of graph G from fig. 1
Like CJ and CF, SzDe sets can be defined as:
SzDi_{i,j} = {k : k Î V} is named SzDe set of i vs. j if: δ(G)_{k,i} < δ(G)_{k,j} |
(20) |
SzDe sets are not fragments (connected subgraphs). An example is depicted in fig. 12:
Fig. 12. SzDe_{2,6} = {2,3} and SzDe_{6,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:
CFDi_{1,4,[1,2,3,4]} = {1, 8, 9, 10}; CFDi_{4,1,[4,3,2,1]} = {4, 5, 6, 7};
CJDi_{1,4,[1,2,3,4]} = {1, 9, 10}; CJDi_{4,1,[4,3,2,1]} = {4, 5, 6, 7, 8};
SzDi_{1,4} = {1, 2, 9, 10}, SzDi_{4,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
CFDi_{1,4,[1,2,3,4]}, CFDi_{4,1,[4,3,2,1]}, CJDi_{1,4,[1,2,3,4]}, CJDi_{4,1,[4,3,2,1]}, SzDi_{1,4}, SzDi_{4,1} sets
From fig. 13, some conclusions are immediate:
· The sets CFDi and CJDi are distinct: CF_{4,1,[4,3,2,1]} Ì CJ_{4,1,[4,3,2,1]} and CF_{1,4,[1,2,3,4]} Ì CJ_{1,4,[1,2,3,4]};
· The sets SzDi and CJDi are distinct: CJ_{4,1,[4,3,2,1]} Ì Sz_{4,1} and CJ_{1,4,[1,2,3,4]} Ì Sz_{1,4};
· The sets SzDi and CFDi are distinct: CF_{4,1,[4,3,2,1]} Ì Sz_{4,1} and CF_{1,4,[1,2,3,4]} Ë Sz_{1,4};
· The sets CFDi are not contained in sets SzDi: CF_{4,1,[4,3,2,1]} Ì Sz_{4,1} and CF_{1,4,[1,2,3,4]} Ë Sz_{1,4};
· The CJDi sets are contained in SzDi sets: CJ_{4,1,[4,3,2,1]} Ì Sz_{4,1} and CJ_{1,4,[1,2,3,4] }Ì Sz_{1,4};
Let us consider another two fragmentation methods, the minimal set that contain i vertex and not contain j vertex MI_{i,j}:
MI_{i,j} = {i} |
(21) |
and maximal set that contain i vertex and not contain j vertex:
MA_{i,j} = G\{j} |
(22) |
Some interesting properties are also available now:
· MI_{i,j} is a set that is contained in all sets generated for (i,j) pair of vertices:
MI_{i,j} Í CJ_{i,j,p}; MI_{i,j} Í CF_{i,j,p}; MI_{i,j} Í Sz_{i,j} |
(23) |
· MA_{i,j} it contain all fragments generated for (i,j) pair of vertices:
CJ_{i,j,p} Ê MA_{i,j}; CF_{i,j,p} Ê MA_{i,j}; Sz_{i,j} Ê MA_{i,j} |
(24) |
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 i’s belonging versus j, that is CFDi_{i,j,p};
· region of j’s belonging versus i, that is CFDi_{j,i,p};
· the path p\{i, j};
· indifferent region G\{p\{i, j} È CFDi_{i,j,p} È CFDi_{j,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: CFDi_{i,j}; turquoise: CFDi_{j,i}; pink: p\{i, j}; red: rest;
The fragments from fig. 15 are:
CFDi_{3,6,[3,6]} = [1,2,3,5]; CFDi_{6,3,[6,3]} = [6,7,8];
CFDi_{3,4,[3,5,4]} = [1,3,6,8]; CFDi_{4,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 i’s belonging versus j, that is CFDe_{i,j,p};
· region of j’s belonging versus i, that is CFDe_{j,i,p};
· the path p\{i, j};
· indifferent region G\{p\{i, j} È CFDe_{i,j,p} È CFDe_{j,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: CFDe_{i,j}; turquoise: CFDe_{j,i}; pink: p\{i, j}; red: rest;
The fragments from fig. 16 are:
CFDi_{3,6,[3,1,2,4,7,6]} = [3,5]; CFDi_{6,3,[6,7,4,2,1,3]} = [6,8];
CFDi_{3,4,[3,1,2,4]} = [3,6,8]; CFDi_{4,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 i’s belonging versus j, that is CFDe_{i,j,p};
· region of j’s belonging versus i, that is CFDe_{j,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: CFDe_{i,j}; turquoise: CFDe_{j,i}; red: equidistant region {k : d(k,i) = d(k,j)};
The fragments from fig. 17 are:
SzDi_{3,6} = [1,2,3,5]; SzDi_{6,3} = [6,7,8];
SzDi_{3,4} = [1,3,6,8]; SzDi_{4,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 F_{i,j,p} fragment
Demonstration:
Fig. 18. Auxiliary construction for theorem 1 demonstration
Let v Î CF_{i,j,p}. Then:
(Case 1) d(G_{p})_{v,i} < ¥, d(G_{p})_{v,j} = ¥ and respectively
(Case2) d(G_{p})_{v,i} < ¥, d(G_{p})_{v,j} < ¥, d(G_{p})_{v,i} < d(G_{p})_{v,j}
(Case 1, demonstration):
d(G_{p})_{v,i }< ¥ Þ $p_{v,i }Î P(G_{p})_{v,i} (P(G_{p})_{k,i }¹ Æ). Let k Î p_{v,i} Þ $p_{k,i }Î P(G_{p})_{k,i} (p_{k,i }Í p_{v,i}) Þ
d(G_{p})_{k,i }< ¥ Þ $p_{v,k}Î P(G_{p})_{v,k} (p_{v,k }Í p_{v,i}) |
(25) |
If d(G_{p})_{k,j }< ¥ Þ $p_{k,j }Î P(G_{p})_{k,j} (P(G_{p})_{k,j }¹ Æ). Let w_{v,j }= p_{v,k }È p_{k,j}; w_{v,j }Î W(G_{p})_{v,j} (W(Gp)_{v,j }¹ Æ) Þ d(Gp)_{v,j }£ l(p_{v,k}) + l(p_{k,j}) < ¥ contradiction with d(G_{p})_{v,j }= ¥ Þ
d(G_{p})_{k,j }= ¥ |
(26) |
From (25) and (26) Þ k Î CF_{i,j,p} Þ p_{v,i }Í CF_{i,j,p} Þ v connected with i in CF_{i,j,p} Þ
CF_{i,j,p} connected |
(27) |
(Case 2, demonstration):
d(G_{p})_{v,i }< ¥ Þ $p_{v,i }Î P(G_{p})_{v,i} s. th. l(p_{v,i}) = min{l(q), q Î P(G_{p})_{v,i}} (P(G_{p})_{v,i }¹ Æ; l(p_{v,i}) = d(G_{p})_{v,i}). Let k Î p_{v,i }Þ
$ p_{k,i }Î P(G_{p})_{k,i} (p_{k,i }Í p_{v,i}) , $p_{v,k }Î P(G_{p})_{v,k} (p_{v,k }Í p_{v,i}) |
(28) |
Because a geodesic path can contain only geodesic paths, from (28) it results:
l(p_{k,i}) = d(G_{p})_{k,i }, l(p_{v,k}) = d(G_{p})_{v,k} , l(p_{v,i}) = l(p_{v,k}) + l(p_{k,i}) Þ d(G_{p})_{v,i }= d(G_{p})_{v,k }+ d(G_{p})_{k,i}
d(G_{p})_{v,j }£ d(G_{p})_{v,k }+ d(G_{p})_{k,j} (d(G_{p}) a metric); (28) Þ d(G_{p})_{v,j }-d(G_{p})_{v,i }£ d(G_{p})_{k,j }- d(G_{p})_{k,i}
From d(G_{p})_{v,i }< d(G_{p})_{v,j} Þ 0 <d(G_{p})_{v,j }- d(G_{p})_{v,i}£d(G_{p})_{k,j}-d(G_{p})_{k,i} and then:
d(G_{p})_{k,i} < d(G_{p})_{k,j} Þ k Î CF_{i,j,p} Þ p_{v,i }Í CF_{i,j,p} Þ
v connected with i in CF_{i,j,p} Þ CF_{i,j,p} connected |
(29) |
From (27) and (29) it result that CF_{i,j,p} is a connected subgraph (q.e.d.).
Theorem 2. SzDi is a fragment.
"i, j Î V then SZDi_{i,j} fragment
Demonstration:
Let v Î SZDi_{i,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 }< ¥ Þ $p_{v,i }Î P(G)_{v,i} s. th. l(p_{v,i}) = min{l(q), qÎ P(G)_{v,i}} (P(G)_{v,i }¹ Æ; l(p_{v,i}) = d(G)_{v,i}). Let k Î p_{v,i }Þ
$ p_{k,i }Î P(G)_{k,i} (p_{k,i }Í p_{v,i}) , $p_{v,k }Î P(G)_{v,k} (p_{v,k }Í p_{v,i}) |
(30) |
Because a geodesic path can contain only geodesic paths, from (28) it results:
l(p_{k,i}) = d(G)_{k,i }, l(p_{v,k}) = d(G)_{v,k} , l(p_{v,i}) = l(p_{v,k}) + l(p_{k,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 Î SzDi_{i,j }Þ p_{v,i }Í SzDi_{i,j} Þ v connected with i in SzDi_{i,j} Þ
SzDi_{i,j} connected subgraph (q.e.d.).
Theorem 3. CJDi sets are contained in SzDi fragments.
CJDi_{i,j,p} Ì SzDi_{i,j}
Demonstration:
Let v Î CJDi_{i,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 Î SzDi_{i,j,p}. From here, it result immediately that CJDi_{i,j,p} Ì SzDi_{i,j} (q.e.d.).
References
[1] M. V. Diudea, I. Gutman, L. Jäntschi, '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.