# Consultar departamento

Por fecha Por autores Por títulos Por temas (CDU)

Del documento Todo RECERCAT

# Mi RECERCAT

Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/868

 Título: On the Steiner, geodetic and hull numbers of graphs Hernando Martín, María del Carmen; Tao, Jiang; Mora Giné, Mercè; Pelayo Melero, Ignacio Manuel; Seara Ojea, Carlos Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada I; Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta Given a graph G and a subset W ? V (G), a Steiner W-tree is a tree of minimum order that contains all of W. Let S(W) denote the set of all vertices in G that lie on some Steiner W-tree; we call S(W) the Steiner interval of W. If S(W) = V (G), 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 u, v in G, a shortest u − v path in G is called a u − v geodesic. Let I[u, v] denote the set of all vertices in G lying on some u − v geodesic, and let J[u, v] denote the set of all vertices in G lying on some induced u − v path. Given a set S ? V (G), let I[S] = ?u,v?S I[u, v], and let J[S] = ?u,v?S J[u, v]. We call I[S] the geodetic closure of S and J[S] the monophonic closure of S. If I[S] = V (G), then S is called a geodetic set of G. If J[S] = V (G), 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 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. Graph theoryChordal graphConvexitygeodesicgeodetic setgeodetic numberhull numbermonophonic pathmonophonic setSteiner setSteiner numberGrafs, Teoria deClassificació AMS::05 Combinatorics::05C Graph theory Attribution-NonCommercial-NoDerivs 2.5 Spain http://creativecommons.org/licenses/by-nc-nd/2.5/es/ Artículo

## Otros documentos del mismo autor/a

Hernando Martín, María del Carmen; Mora Giné, Mercè; Pelayo Melero, Ignacio Manuel; Seara Ojea, Carlos
Hernando Martín, María del Carmen; Mora Giné, Mercè; Pelayo Melero, Ignacio Manuel; Seara Ojea, Carlos; Wood, David
Hernando Martín, María del Carmen; Mora Giné, Mercè; Pelayo Melero, Ignacio Manuel; Seara Ojea, Carlos
Cáceres González, José; Hernando Martín, María del Carmen; Mora Giné, Mercè; Pelayo Melero, Ignacio Manuel; Puertas González, María Luz; Seara Ojea, Carlos
Hernando Martín, María del Carmen; Mora Giné, Mercè; Seara Ojea, Carlos; Wood, David

Coordinación

Patrocinio