On bounds for the cutting number of a graph

The cutting number of a vertex v of a finite graph G = ( V,E ) is a natural measure of the extent to which the removal of v disconnects the graph. Precisely, the cutting number c ( v ) of v is defined as the number of pairs of vertices { u , w } of G such that u,w ≠ v and every u - w path contains v...

Full description

Saved in:
Bibliographic Details
Published in:Indian journal of pure and applied mathematics 2012-12, Vol.43 (6), p.637-649
Main Authors: Mukwembi, Simon, Hove-Musekwa, Senelani Dorothy
Format: Article
Language:English
Subjects:
Applications of Mathematics
Mathematics
Mathematics and Statistics
Numerical Analysis
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The cutting number of a vertex v of a finite graph G = ( V,E ) is a natural measure of the extent to which the removal of v disconnects the graph. Precisely, the cutting number c ( v ) of v is defined as the number of pairs of vertices { u , w } of G such that u,w ≠ v and every u - w path contains v . The cutting number c ( G ) of G is the maximum value of c ( v ) over all vertices in V . We provide exact bounds on the cutting number of G in terms of order and diameter of the graph.
ISSN:0019-5588
0975-7465
DOI:10.1007/s13226-012-0038-8