Record number :

948567

Title of article :

On the Steiner, geodetic and hull numbers of graphs Original Research Article

Author/Authors :

Carmen Hernando، نويسنده , , Tao Jiang، نويسنده , , Mercè Mora، نويسنده , , Ignacio M. Pelayo، نويسنده , , Carlos Seara، نويسنده ,

Issue Information :

روزنامه با شماره پیاپی سال 2005

Pages :

16

From page :

139

To page :

154

Abstract :

Given a graph G and a subset image, a Steiner W -tree is a tree of minimum order that contains all of W. Let image denote the set of all vertices in G that lie on some Steiner W-tree; we call image the Steiner interval of W. If image, then we call W a Steiner set of G. The minimum order of a Steiner set of G is called the Steiner number of G.
Given two vertices image in G, a shortest image–image path in G is called a image–image geodesic. Let image denote the set of all vertices in G lying on some image–image geodesic, and let image denote the set of all vertices in G lying on some induced image–image path. Given a set image, let image, and let image. We call image the geodetic closure of S and image the monophonic closure of S. If image, then S is called a geodetic set of G. If image, then S is called a monophonic set of G. The minimum order of a geodetic set in G is named the geodetic number of G.
In this paper, we explore the relationships both between Steiner sets and geodetic sets and between Steiner sets and monophonic sets. We thoroughly study the relationship between the Steiner number and the geodetic number, and address the following questions: in a graph G when must every Steiner set also be geodetic and when must every Steiner set also be monophonic. In particular, among others we show that every Steiner set in a connected graph G must also be monophonic, and that every Steiner set in a connected interval graph H must be geodetic.

Keywords :

Monophonic set , Steiner set , Chordal graph , Convexity , geodesic , Geodetic set , Geodetic number , Hull number , Monophonic path , Steiner number

Journal title :

Discrete Mathematics

Serial Year :

2005

Link To Document :