Some Steiner concepts on lexicographic products of graphs

Bijo S. Anand (Author), Manoj Changat (Author), Iztok Peterin (Author), Prasanth G. Narasimha-Shenoi (Author)

Abstract

The smallest tree that contains all vertices of a subset ▫$W$▫ of ▫$V(G)$▫ is called a Steiner tree. The number of edges of such a tree is the Steiner distance of ▫$W$▫ and union of all Steiner trees of ▫$W$▫ form a Steiner interval. Both of them are described for the lexicographic product in the present work. We also give a complete answer for the following invariants with respect to the Steiner convexity: the Steiner number, the rank, the hull number, and the Carathéodory number, and a partial answer for the Radon number. At the end we locate and repair a small mistake from [J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, On the geodetic and the hull numbers in strong product graphs, Comput. Math. Appl. 60 (2010) 3020--3031].

Keywords

teorija grafov;leksikografski produkt;Steinerjeva konveksnost;Steinerjeva množica;Steinerjeva razdalja;graph theory;lexicographic product;Steiner convexity;Steiner set;Steiner distance;

Data

Language:	English
Year of publishing:	2012
Typology:	1.01 - Original Scientific Article
Organization:	UM FERI - Faculty of Electrical Engineering and Computer Science
UDC:	519.17
COBISS:	16322393
ISSN:	2232-2094
Parent publication:	Preprint series
Views:	326
Downloads:	29
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary keywords:	teorija grafov;leksikografski produkt;Steinerjeva konveksnost;Steinerjeva množica;Steinerjeva razdalja;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 1-15
Volume:	Vol. 50
Issue:	št. 1179
Chronology:	2012
ID:	1476609