Affordable Access

Publisher Website

The recognition of geodetically connected graphs

Authors
Journal
Information Processing Letters
0020-0190
Publisher
Elsevier
Publication Date
Volume
65
Issue
2
Identifiers
DOI: 10.1016/s0020-0190(97)00201-9
Keywords
  • Hinge Vertices
  • Geodetically Connected
  • Recognition Algorithm
Disciplines
  • Computer Science

Abstract

Abstract Let G = ( V, E) be a graph with vertex set V of size n and edge set E of size m. A vertex υ ϵ V is called a hinge vertex if the distance of any two vertices becomes longer after v is removed. A graph without hinge vertex is called a hinge-free graph. In general, a graph G is k-geodetically connected or k-GC for short if G can tolerate any k − 1 vertices failures without increasing the distance among all the remaining vertices. In this paper, we show that recognizing a graph G to be k-GC for the largest value of k can be solved in O( nm) time. In addition, more efficient algorithms for recognizing the k-GC property on some special graphs are presented. These include the O( n + m) time algorithms on strongly chordal graphs (if a strong elimination ordering is given), ptolemaic graphs, and interval graphs, and an O( n 2) time algorithm on undirected path graphs (if a characteristic tree model is given). Moreover, we show that if the input graph G is not hinge-free then finding all hinge vertices of G can be solved in the same time complexity on the above classes of graphs.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Minimum 3-geodetically connected graphs

on Discrete Applied Mathematics Jan 01, 2003

Some special minimum [formula omitted]-geodeticall...

on Discrete Applied Mathematics Jan 01, 2011

Onk-critical,n-connected graphs

on Discrete Mathematics Jan 01, 1977
More articles like this..