Opuscula Mathematica
Opuscula Math. 29, no. 4 (), 427-441
http://dx.doi.org/10.7494/OpMath.2009.29.4.427
Opuscula Mathematica

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



Abstract. An edge geodetic set of a connected graph \(G\) of order \(p \geq 2\) is a set \(S \subseteq V(G)\) such that every edge of \(G\) is contained in a geodesic joining some pair of vertices in \(S\). The edge geodetic number \(g_1(G)\) of \(G\) is the minimum cardinality of its edge geodetic sets and any edge geodetic set of cardinality \(g_1(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 \(g_1^+(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 \leq a \leq b\), there exists a connected graph \(G\) with \(g_1(G)=a\) and \(g_1^+(G)=b\). For an edge geodetic basis \(S\) of \(G\), a subset \(T \subseteq 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 \(f_1(S)\), is the cardinality of a minimum forcing subset of \(S\). The forcing edge geodetic number of \(G\), denoted by \(f_1(G)\), is \(f_1(G) = min\{f_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 \leq a \lt b\) and \(b \geq 2\), there exists a connected graph \(G\) such that \(f_1(G)=a\) and \(g_1(G)=b\).
Keywords: geodetic number, edge geodetic basis, edge geodetic number, upper edge geodetic number, forcing edge geodetic number.
Mathematics Subject Classification: 05C12.
Cite this article as:
A. P. Santhakumaran, J. John, The upper edge geodetic number and the forcing edge geodetic number of a graph, Opuscula Math. 29, no. 4 (2009), 427-441, http://dx.doi.org/10.7494/OpMath.2009.29.4.427
 
Download this article's citation as:
a .bib file (BibTeX), a .ris file (RefMan), a .enw file (EndNote)
or export to RefWorks.

RSS Feed

horizontal rule

ISSN 1232−9274, e-ISSN 2300−6919, DOI http://dx.doi.org/10.7494/OpMath
Copyright © 2003−2017 OPUSCULA MATHEMATICA
Contact: opuscula@agh.edu.pl
Made by Tomasz Zabawa

horizontal rule

In accordance with EU legislation we advise you this website uses cookies to allow us to see how the site is used. All data is anonymized.
All recent versions of popular browsers give users a level of control over cookies. Users can set their browsers to accept or reject all, or certain, cookies.