Advances and Applications in Discrete Mathematics
Volume 6, Issue 1, Pages 45 - 54
(July 2010)
|
|
SOME CONNECTIVITY CONCEPTS IN WEIGHTED GRAPHS
Sunil Mathew and M. S. Sunitha
|
Abstract: In a weighted graph, each arc is assigned a weight. The weight of a path or a cycle is defined as the minimum weight of its arcs. The maximum of weights of all paths between two nodes is defined as the strength of connectedness between the nodes. In applications, the reduction in the strength of connectedness is more relevant than the total disconnection of the graph. The concepts of partial cutnodes, bridges and blocks in weighted graphs are introduced in this paper. Partial cutnodes are characterized using maximum spanning trees. The arcs in a weighted graph are classified into three, according to the strength of connectedness between their end nodes. Partial bridges are characterized in two different ways. The concepts of strong and strongest paths are introduced and partial blocks are characterized using strongest paths. |
Keywords and phrases: weighted graph, partial cutnode, partial bridge, partial block, strong path, strongest path. |
|
Number of Downloads: 228 | Number of Views: 740 |
|