Some Steiner concepts on lexicographic products of graphs

被引:5
作者
Anand, Bijo S. [1 ,2 ]
Changat, Manoj [3 ]
Peterin, Iztok [4 ]
Narasimha-Shenoi, Prasanth G. [5 ]
机构
[1] Sree Narayana Coll Women, Dept Math, Kollam 691001, India
[2] Univ Kerala, Dept Futures Studies, Trivandrum 695034, Kerala, India
[3] Univ Kerala, Dept Futures Studies, Trivandrum 695581, Kerala, India
[4] Univ Maribor, FEECS, SLO-2000 Maribor, Slovenia
[5] Govt Coll, Dept Math, Chittur 678104, Palakkad, India
关键词
Lexicographic product; Steiner convexity; Steiner set; Steiner distance;
D O I
10.1142/S1793830914500608
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Let G be a graph and W a subset of V(G). A subtree with the minimum number of edges that contains all vertices of W is a Steiner tree for W. The number of edges of such a tree is the Steiner distance of W and union of all vertices belonging to Steiner trees for W form a Steiner interval. We describe both of these for the lexicographic product of graphs. 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 Caratheodory number, and a partial answer for the Radon number.
引用
收藏
页数:14
相关论文
共 28 条
[1]   Convex Sets in Lexicographic Products of Graphs [J].
Anand, Bijo S. ;
Changat, Manoj ;
Klavzar, Sandi ;
Peterin, Iztok .
GRAPHS AND COMBINATORICS, 2012, 28 (01) :77-84
[2]   Approximation schemes for NP-hard geometric optimization problems: a survey [J].
Arora, S .
MATHEMATICAL PROGRAMMING, 2003, 97 (1-2) :43-69
[3]  
Balakrishnan K., 2008, LECT NOTES SER 5 RAM, V5, P47
[4]   On a local 3-Steiner convexity [J].
Bresar, Bostjan ;
Gologranc, Tanja .
EUROPEAN JOURNAL OF COMBINATORICS, 2011, 32 (08) :1222-1235
[5]   The geodetic number of the lexicographic product of graphs [J].
Bresar, Bostjan ;
Sumenjak, Tadeja Kraner ;
Tepeh, Aleksandra .
DISCRETE MATHEMATICS, 2011, 311 (16) :1693-1698
[6]   Steiner intervals, geodesic intervals, and betweenness [J].
Bresar, Bostjan ;
Changat, Manoj ;
Mathews, Joseph ;
Peterin, Iztok ;
Narasimha-Shenoi, Prasanth G. ;
Horvat, Aleksandra Tepeh .
DISCRETE MATHEMATICS, 2009, 309 (20) :6114-6125
[7]   On 3-Steiner simplicial orderings [J].
Caceres, Jose ;
Oellermann, Ortrud R. .
DISCRETE MATHEMATICS, 2009, 309 (19) :5828-5833
[8]  
Canoy SR, 2005, ARS COMBINATORIA, V75, P113
[9]   On triangle path convexity in graphs [J].
Changat, M ;
Mathew, J .
DISCRETE MATHEMATICS, 1999, 206 (1-3) :91-95
[10]   Convexities related to path properties on graphs [J].
Changat, M ;
Mulder, HM ;
Sierksma, G .
DISCRETE MATHEMATICS, 2005, 290 (2-3) :117-131