Connected edge monophonic number of a graph
DOI:
https://doi.org/10.4067/S071609172013000300002Keywords:
Monophonic path, Edge monophonic number, Connected edge monophonic number, Connected edge geodetic number.Abstract
For a connected graph G of order n,a set S of vertices is called an edge monophonic set of G if every edge of G lies on a monophonic path joining some pair of vertices in S, and the edge monophonic number m_{e}(G) is the minimum cardinality of an edge monophonic set. An edge monophonic set S of G is a connected edge monophonic set if the subgraph induced by S is connected, and the connected edge monophonic number m_{ce}(G) is the minimum cardinality of a connected edge monophonic set of G. Graphs of order n with connected edge monophonic number 2, 3 or n are characterized. It is proved that there is no noncomplete graph G of order n > 3 with m_{e}(G) = 3 and m_{ce}(G) = 3. It is shown that for integers k,l and n with 4 < k < l < n, there exists a connected graph G of order n such that m_{e}(G) = k and m_{ce}(G) = l.Also, for integers j,k and l with 4 < j < k < l, there exists a connected graph G such that m_{e}(G)= j,m_{ce}(G)= k and g_{ce}(G) = l,where g_{ce}(G) is the connected edge geodetic number ofa graph G.References
[1] F. Buckley and F. Harary, Distance in Graphs, AddisonWesley, Redwood City, CA, (1990).
[2] G. Chartrand, F. Harary and P. Zhang, On the geodetic number of a graph, Networks, 39(1), pp. 16, (2002).
[3] G. Chartrand, F. Harary , H. C. Swart and P. Zhang, Geodomination in graphs, Bulletin of the ICA, 31, pp. 5159, (2001).
[4] F. Harary, Graph Theory, AddisionWesely (1969).
[5] F. Harary, E. Loukakis and C. Tsouros, The geodetic number of a graph, Mathl. Comput. Modeling, 17(11), pp. 8995, (1993).
[6] R. Muntean and P. Zhang, On geodomonation in graphs, Congr. Numer., 143, pp. 161174, (2000).
[7] A. P. Santhakumaran P. Titus and P. Balakrishnan, Edge monophonic number of a graph, communicated.
[8] A. P. Santhakumaran and S. V. Ullas Chandran, On the edge geodetic number and kedge geodetic number of a graph, Inter. J. Math. Combin., 3, pp. 8593, (2008).
[9] A. P. Santhakumaran and S. V. Ullas Chandran, The edge geodetic number and cartesian product of a graph, Discussiones Mathematicae Graph Theory 30 (1), pp. 5573, (2010).
[2] G. Chartrand, F. Harary and P. Zhang, On the geodetic number of a graph, Networks, 39(1), pp. 16, (2002).
[3] G. Chartrand, F. Harary , H. C. Swart and P. Zhang, Geodomination in graphs, Bulletin of the ICA, 31, pp. 5159, (2001).
[4] F. Harary, Graph Theory, AddisionWesely (1969).
[5] F. Harary, E. Loukakis and C. Tsouros, The geodetic number of a graph, Mathl. Comput. Modeling, 17(11), pp. 8995, (1993).
[6] R. Muntean and P. Zhang, On geodomonation in graphs, Congr. Numer., 143, pp. 161174, (2000).
[7] A. P. Santhakumaran P. Titus and P. Balakrishnan, Edge monophonic number of a graph, communicated.
[8] A. P. Santhakumaran and S. V. Ullas Chandran, On the edge geodetic number and kedge geodetic number of a graph, Inter. J. Math. Combin., 3, pp. 8593, (2008).
[9] A. P. Santhakumaran and S. V. Ullas Chandran, The edge geodetic number and cartesian product of a graph, Discussiones Mathematicae Graph Theory 30 (1), pp. 5573, (2010).
How to Cite
[1]
A. P. Santhakumaran, P. Titus, and P. Balakrishnan, “Connected edge monophonic number of a graph”, Proyecciones (Antofagasta, On line), vol. 32, no. 3, pp. 215234, 1.
Issue
Section
Artículos

Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
 No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.