The upper edge geodetic number and the forcing edge geodetic number of a graph

• Autorzy: Santhakumaran A. P. , John J.
• Języki publikacji: EN

Abstrakty

EN

An edge geodetic set of a connected graph G of order p ≥ 2 is a set S ⊆ V(G) such that every edge of G is contained in a geodesic joining some pair of vertices in S. The edge geodetic number g1(G) of G is the minimum cardinality of its edge geodetic sets and any edge geodetic set of cardinality g1(G) is a minimum edge geodetic set of G or an edge geodetic basis of G. An edge geodetic set S in a connected graph G is a minimal edge geodetic set if no proper subset of S is an edge geodetic set of G. The upper edge geodetic number g1+(G) of G is the maximum cardinality of a minimal edge geodetic set of G. The upper edge geodetic number of certain classes of graphs are determined. It is shown that for every two integers a and b such that 2 ≤ a ≤ b, there exists a connected graph G with g1(G) = a and g1+(G) = b. For an edge geodetic basis S of G, a subset T ⊆ S is called a forcing subset for S if S is the unique edge geodetic basis containing T. A forcing subset for S of minimum cardinality is a minimum forcing subset of S. The forcing edge geodetic number of S denoted by ƒ1(S), is the cardinality of a minimum forcing subset of S. The forcing edge geodetic number of G, denoted by ƒ1(G), is ƒ1(G) = min{ ƒ1(S)}, where the minimum is taken over all edge geodetic bases S in G. Some general properties satisfied by this concept are studied. The forcing edge geodetic number of certain classes of graphs are determined. It is shown that for every pair a, b of integers with 0 ≤ a < b and b ≥ 2, there exists a connected graph G such thatƒ1(G) = a and g1(G) = b.

Słowa kluczowe

EN

geodetic number; edge geodetic basis; edge geodetic number; upper edge geodetic number; forcing edge geodetic number

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2009
• Tom: Vol. 29, no. 4
• Strony: 427--441
• Opis fizyczny: Bibliogr. 10 poz., rys.

Twórcy

autor

Santhakumaran A. P.

autor

John J.

• St. Xavier's College (Autonomous) Research Department of Mathematics Palayamkottai - 627 002, India,

Bibliografia

• [1] F. Buckley, F. Harary, Distance in Graphs, Addison-Wesley, Redwood City, CA, 1990.
• [2] F. Buckley, F. Harary, L. V. Quintas, Extremal results on the geodetic number of a graph, Scientia A2 (1988) 17–26.
• [3] G. Chartrand, F. Harary, P. Zhang, On the geodetic number of a graph, Networks 39 (2002) 1, 1–6.
• [4] G. Chartrand, E.M. Palmer, P. Zhang, The geodetic number of a graph: a survey, Congr. Numer. 156 (2002), 37–58.
• [5] G. Chartrand, P. Zhang, The forcing geodetic number of a graph, Discuss. Math. Graph Theory 19 (1999), 45–58.
• [6] F. Harary, Graph Theory, Addison-Wesley, 1969.
• [7] F. Harary, E. Loukakis, C. Tsouros, The geodetic number of a graph, Math. Comput. Modeling 17 (1993) 11, 89–95.
• [8] A.P. Santhakumaran, J. John, Edge geodetic number of graph, Journal of Discrete Mathematical Sciences and Cryptography 10 (2007) 3, 415–432.
• [9] A.P. Santhakumaran, P. Titus, J. John, On the connected geodetic number of a graph, Congressus Numerantium, to appear.
• [10] A.P. Santhakumaran, P. Titus, J. John, The upper connected geodetic number and forcing connected geodetic number of a graph, Discrete Applied Mathematics (2008), DOI: 10.1016/j.dam.2008.06.005.