The 2-edge geodetic number and graph operations

被引：2
作者：
A. P. Santhakumaran
S. V. Ullas Chandran
机构：
[1] Department of Mathematics, St. Xavier’s College (Autonomous), Palayamkottai
[2] Department of Mathematics, Amrita Vishwa Vidyapeetham, Amritapuri Campus, Kollam
来源：
Arabian Journal of Mathematics | 2012年 / 1卷 / 2期
关键词：
05C12;
D O I：
10.1007/s40065-012-0016-3
中图分类号：
学科分类号：
摘要：
For a connected graph G = (V, E) of order n ≥ 2, a set S ⊆ V is a 2-edge geodetic set of G if each edge e ∈ E − E(S) lies on a u-v geodesic with d(u, v) = 2 for some vertices u and v in S. The minimum cardinality of a 2-edge geodetic set in G is the 2-edge geodetic number of G, denoted by eg2(G). It is proved that for any connected graph G, β1(G) ≤ eg2(G), where β1(G) is the matching number of G. It is shown that every pair a, b of integers with 2 ≤ a ≤ b is realizable as the matching number and 2-edge geodetic number, respectively, of some connected graph. We determine bounds for the 2-edge geodetic number of Cartesian product of graphs. Also we determine the 2-edge geodetic number of certain classes of Cartesian product graphs. The 2-edge geodetic number of join of two graphs is obtained in terms of the 2-edge geodetic number of the factor graphs.[Figure not available: see fulltext.]. © 2012, The Author(s).
引用
收藏
页码：241 / 249
页数：8
相关论文
共 13 条
[1]  
Attici M., Computational complexity of geodetic sets, Int. J. Comput. Math., 79, pp. 587-591, (2002)
[2]  
Bresar B., Klavzar S., Horvat A.T., On the geodetic number and related metric sets in Cartesian product graphs, Discret. Math., 308, pp. 5555-5561, (2008)
[3]  
Buckley F., Harary F., Distance in Graphs, (1990)
[4]  
Chartrand G., Harary F., Zhang P., On the geodetic number of a graph, Networks, 39, 1, pp. 1-6, (2002)
[5]  
Chartrand G., Zhang P., Introduction to Graph Theory, (2006)
[6]  
Gera R., Zhang P., On k-geodomination in Cartesian products, Congr. Numer., 158, pp. 63-178, (2002)
[7]  
Harary F., Graph Theory, (1969)
[8]  
Imrich W., Klavzar S., Product Graphs: Structure and Recognition, (2000)
[9]  
Muntean R., Zhang P., On geodomination in graphs, Congr. Numer., 143, pp. 161-174, (2000)
[10]  
Muntean R., Zhang P., k-Geodomination in graphs, ARS Combin., 63, pp. 33-47, (2002)
12