On the shortest path in some k-connected graphs

Suppose G is a connected graph and u and v are two distinct vertices of G. Let P[u, v] be the shortest path in G with endpoints u and v. Let t(G) = max{| V (P[u, v]) |:u, v ∈ V (G)}. A graph G is said to be k-connected if it has more than k vertices and removal of fewer than k vertices does not disc...

Full description

Saved in:
Bibliographic Details
Main Authors: Sim, K. A., Tan, T. S., Wong, K. B.
Format: Conference Proceeding
Language:English
Subjects:
Graph theory
Graphs
Shortest-path problems
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Suppose G is a connected graph and u and v are two distinct vertices of G. Let P[u, v] be the shortest path in G with endpoints u and v. Let t(G) = max{| V (P[u, v]) |:u, v ∈ V (G)}. A graph G is said to be k-connected if it has more than k vertices and removal of fewer than k vertices does not disconnect the graph G. We show that in any k-connected graph G with n vertices, t ( G ) ≤ ⌊ n − 2 k ⌋ + 2 . We also present some graphs where the equality holds.
ISSN:0094-243X
1551-7616
DOI:10.1063/1.4954598