On the geodetic and the hull numbers in strong product graphs

被引：32

作者：

Caceres, J. ^{[2
]}

Hernando, C. ^{[1
]}

Mora, M. ^{[1
]}

Pelayo, I. M. ^{[1
]}

Puertas, M. L. ^{[2
]}

机构：

[1] Univ Politecn Cataluna, Barcelona, Spain

[2] Univ Almeria, Almeria, Spain

来源：

COMPUTERS & MATHEMATICS WITH APPLICATIONS | 2010年 / 60卷 / 11期

关键词：

Metric graph theory; Geodetic set; Hull set; Geodetic number; Hull number; Strong product; CARTESIAN PRODUCT; SETS; CONVEXITY;

D O I：

10.1016/j.camwa.2010.10.001

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A set S of vertices of a connected graph G is convex, if for any pair of vertices u, v is an element of S, every shortest path joining u and v is contained in S. The convex hull CH (S) of a set of vertices S is defined as the smallest convex set in G containing S. The set S is geodetic, if every vertex of G lies on some shortest path joining two vertices in S, and it is said to be a hull set if its convex hull is V (G). The geodetic and the hull numbers of G are the minimum cardinality of a geodetic and a minimum hull set, respectively. In this work, we investigate the behavior of both geodetic and hull sets with respect to the strong product operation for graphs. We also establish some bounds for the geodetic number and the hull number and obtain the exact value of these parameters for a number of strong product graphs. (C) 2010 Elsevier Ltd. All rights reserved.

引用

页码：3020 / 3031

页数：12

共 25 条

[1]

[Anonymous], 1999, Introduction to Graph Theory

[2]

BRESAR B, 2007, GRAPH THEORY, V27, P333

[3] On the geodetic number and related metric sets in Cartesian product graphs [J].