To install StudyMoose App tap and then “Add to Home Screen”
Save to my list
Remove from my list
The Wiener index, a pivotal topological invariant in chemical graph theory, measures the sum of shortest distances between all pairs of vertices in a graph. This paper introduces an innovative method to compute the Wiener index of bicyclic graphs, which significantly reduces computational complexity. By dividing the bicyclic graph into subgraphs and leveraging modular arithmetic, the proposed method offers a more efficient calculation pathway. The effectiveness of this method is demonstrated through examples, showcasing its potential to streamline computations in graph theory and its applications.
Bicyclic graphs, characterized by having one more edge than vertices, play a crucial role in various scientific disciplines, including chemistry and network theory.
The traditional approach to calculating the Wiener index, a task fundamental to analyzing graph properties, involves extensive iteration and computation. This study proposes a novel methodology that simplifies this process, particularly for bicyclic graphs without pendant vertices.
A graph G of order n is called a bicyclic graph if G is connected and the number of edges of G are n+1. Bicyclic graphs are connected graphs in which the number of edges equals the number of vertices plus one.
Verified writer
Proficient in: Math
5 (234)
“ Very organized ,I enjoyed and Loved every bit of our professional interaction ”
It is easy to see from the definition that G is a bicyclic graph if and only if G can be obtained from a tree T (with the same order) by adding two new edges to T.
Old Method to Calculate Wiener Index of Bicyclic Graph:
Suppose a graph that full fill condition of bicyclic graph. In this graph I have six vertices and seven edges.
Now I am going to calculate wiener index of that by using some old method.
V_1 V_2=1×1×3=3
V_1 V_3=1×1×4=4
V_1 V_4=2×1×2=4
V_1 V_5=3×1×5=15
V_1 V_6=3×1×7=21
V_2 V_3=2×3×4=24
V_2 V_4=1×3×2=6
V_2 V_5=2×3×5=30
V_2 V_6=2×3×7=42
V_3 V_4=1×4×2=8
V_3 V_5=2×4×5=40
V_3 V_6=2×4×7=56
V_4 V_5=1×2×5=10
V_4 V_6=1×2×7=14
V_5 V_6=1×5×7=35
Sum all above values and the answer would be the W-I of above graph which is WI=312
Now I am going to proof our main objective that shows how I can reduce the time complexity of calculating W-I of a bicyclic graph. After proof I will do the same above example to check either my calculations work or not.
Proof
Suppose we have a graph V with n vertices
V(G)={V_1,V_2 (,……..V)_n }
|V(G)|=n
Let’s start our vertices from 0 instead of 1
V(G)={V_0,V_1 (,……..V)_(n-1) }
Vertices with values are
We can put these values in an array
0 1 2 k-1
a_0 a_1 a_2 …………… a_(k-1)
Now calculate distance from half of vertices which would be done by calculating distance from each vertex to every vertex.
a_0 (1a_1+2a_2+3a_3+⋯…….|(k-1)/2| a_|(k-1)/2| )
a_1 (1a_2+2a_3+3a_4+⋯…….|(k-1)/2| a_|(k+1)/2| )
So
a_(k-1) (1a_0+2a_1+3a_2+⋯…….|(k-1)/2| a_|(k-3)/2| )
Now sum all the values
∑_(j=0)^(k-1)(a_j ∑_(i=1)^|(k-1)/2|(ia_((j+i)%k) ))
This is our wiener index. In this case we have two summations in multiplication which means time complexity is O(k^2)
Now make a notation here which is
S(j)=∑_(i=1)^(|(k-1)/2|)(ia_((j+i)%k) )
Then
WI=∑_(j=0)^(k-1)(a_j S(j))
S(0)=1a_1+2a_2+3a_3+⋯…….|(k-1)/2| a_|(k-1)/2|
S(1)=1a_2+2a_3+3a_4+⋯…….+|(k-3)/2| a_|(k-1)/2| +|(k-1)/2| a_|(k-1)/2|
S(1)-S(0)=-[a_1+a_2+a_3+⋯…….+a_|(k-1)/2| ]+|(k-1)/2| a_|(k-1)/2|
S(1)=S(0)-[a_1+a_2+a_3+⋯…….+a_|(k-1)/2| ]+|(k-1)/2| a_|(k-1)/2|
S(1)=S(0)-∑_(i=1)^((k-1)/2) a_i +|(k-1)/2| a_|(k-1)/2|
Similarly
S(2)=S(1)-∑_(i=2)^((k+1)/2) a_i +|(k-1)/2| a_|(k+3)/2|
Suppose that
T(i)=∑_(i=2)^((k+1)/2) a_i
S(i)=S(i-1)-T(i)+[(k-1)/2]a_((|(k-1)/2|+i)%k)
Now I am going to solve the same example in figure 5.4 using the proof given above. To solve the same graph divide it into two parts and do calculation separately and sum both answers to get W-I of given graph. Value 14 is the distance we obtain after adding other remaining vertices. Now I am going to calculate distance from each vertex to other vertices with no more then n/2 distance. So the distances are:
d_1=1×3×1+1×14×2
d_1=3+28=31
d_3=3×14×1+3×4×2
d_3=42+24=66
d_4=4×1×1+4×3×2
d_4=4+24=28
d_14=14×4×1+14×1×2
d_14=56+28=84
Now I will remove the duplicate entries from above distances and the duplicate entries are:
d_sub=1×14×2+3×2×2
d_sub=28+24=52
d_(part 1)=d_1+d_3+d_4+d_14-d_sub
d_(part 1)=31+66+28+84-52
d_(part 1)=157
Part 2 of graph would be
Value 10 is the distance we obtain after adding other remaining vertices. Now I am going to calculate distance from each vertex to other vertices.
d_(part 2)=10×5×1+5×7×1+7×10×1
d_(part 2)=50+35+70
d_(part 2)=155
To calculate W-I I will add both distances which I calculate in both parts So the W-I would be:
W-I=d_(part 1)+d_(part 2)
W-I=157+155=312
Hence proved we got the same results by applying what we got after doing old methods. To further verify let’s do another example by using different type of bicyclic Graph.
Old Method
In this method first I will calculate distances from each vertex by exempting duplications then W-I would be calculated by adding all the distances. So the distances would be:
d_A=1+1+2+3+3+4
d_A=14
d_B=1+1+2+2+3
d_B=9
d_C=2+3+3+4
d_C=12
d_D=1+1+2
d_D=4
d_E=1+2
d_E=3
d_F=1
WI=〖d_A+d_B+d_C+d_D+d_E+d〗_F
WI=14+9+12+4+3+1
WI=43
Now solve the same example using my algorithm. To do this first I will remove the edge between vertex B and vertex D. This would divide my graph between two parts then I will calculate distances of both parts and by adding all distances required results would be obtain. So my step one is to remove edge between vertex B and D.
In above figure distance at vertex B becomes 5 because distances of other remaining vertices are added in it. Now calculate distances from each vertex.
d_A=1×5×1
d_A=5
d_B=5×1×1
d_B=5
d_C=1×1×1
d_C=1
d_1=5+5+1=11
In above figure distance at vertex D becomes 4 because distances of other remaining vertices are added in it. Now I will calculate distances from each vertex with vertex having maximum of n/2 distance. And the distances are.
d_D=4×1×1+4×1×2
d_D=12
d_E=1×1×1+1×1×2
d_E=3
d_F=1×1×1+1×4×1
d_F=5
d_2=12+3+5=20
Now only one edge left which is missing in all above calculation. That particular edge is the one which was removed in first step. Now I will calculate distance for that particular edge. After that I will add all distances and the answer after addition would be my result. In above figure distance at vertex B becomes 3 and distance at vertex D becomes 4 because distances of other remaining vertices are added in it. Now the distance would be:
d_3=3×4=12
WI=d_1+d_2+d_3
WI=11+20+12
WI=43
In both methods results are same which proves my algorithm is giving correct results by reducing calculation and iterations.
The introduction of a novel methodology for computing the Wiener index of bicyclic graphs marks a significant advancement in the field of graph theory. By reducing computational complexity, this method enables faster and more efficient calculations, offering valuable implications for research in chemistry, network analysis, and beyond. The method's validation through examples underscores its potential to replace more cumbersome traditional approaches.
Efficient Computation of the Wiener Index in Bicyclic Graphs. (2024, Feb 22). Retrieved from https://studymoose.com/document/efficient-computation-of-the-wiener-index-in-bicyclic-graphs
👋 Hi! I’m your smart assistant Amy!
Don’t know where to start? Type your requirements and I’ll connect you to an academic expert within 3 minutes.
get help with your assignment
