# The vertex monophonic number of a graph

• Volume: 32, Issue: 2, page 191-204
• ISSN: 2083-5892

top

## Abstract

top
For a connected graph G of order p ≥ 2 and a vertex x of G, a set S ⊆ V(G) is an x-monophonic set of G if each vertex v ∈ V(G) lies on an x -y monophonic path for some element y in S. The minimum cardinality of an x-monophonic set of G is defined as the x-monophonic number of G, denoted by mₓ(G). An x-monophonic set of cardinality mₓ(G) is called a mₓ-set of G. We determine bounds for it and characterize graphs which realize these bounds. A connected graph of order p with vertex monophonic numbers either p - 1 or p - 2 for every vertex is characterized. It is shown that for positive integers a, b and n ≥ 2 with 2 ≤ a ≤ b, there exists a connected graph G with radₘG = a, diamₘG = b and mₓ(G) = n for some vertex x in G. Also, it is shown that for each triple m, n and p of integers with 1 ≤ n ≤ p -m -1 and m ≥ 3, there is a connected graph G of order p, monophonic diameter m and mₓ(G) = n for some vertex x of G.

## How to cite

top

A.P. Santhakumaran, and P. Titus. "The vertex monophonic number of a graph." Discussiones Mathematicae Graph Theory 32.2 (2012): 191-204. <http://eudml.org/doc/270812>.

@article{A2012,
abstract = {For a connected graph G of order p ≥ 2 and a vertex x of G, a set S ⊆ V(G) is an x-monophonic set of G if each vertex v ∈ V(G) lies on an x -y monophonic path for some element y in S. The minimum cardinality of an x-monophonic set of G is defined as the x-monophonic number of G, denoted by mₓ(G). An x-monophonic set of cardinality mₓ(G) is called a mₓ-set of G. We determine bounds for it and characterize graphs which realize these bounds. A connected graph of order p with vertex monophonic numbers either p - 1 or p - 2 for every vertex is characterized. It is shown that for positive integers a, b and n ≥ 2 with 2 ≤ a ≤ b, there exists a connected graph G with radₘG = a, diamₘG = b and mₓ(G) = n for some vertex x in G. Also, it is shown that for each triple m, n and p of integers with 1 ≤ n ≤ p -m -1 and m ≥ 3, there is a connected graph G of order p, monophonic diameter m and mₓ(G) = n for some vertex x of G.},
author = {A.P. Santhakumaran, P. Titus},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {monophonic path; monophonic number; vertex monophonic number},
language = {eng},
number = {2},
pages = {191-204},
title = {The vertex monophonic number of a graph},
url = {http://eudml.org/doc/270812},
volume = {32},
year = {2012},
}

TY - JOUR
AU - A.P. Santhakumaran
AU - P. Titus
TI - The vertex monophonic number of a graph
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 2
SP - 191
EP - 204
AB - For a connected graph G of order p ≥ 2 and a vertex x of G, a set S ⊆ V(G) is an x-monophonic set of G if each vertex v ∈ V(G) lies on an x -y monophonic path for some element y in S. The minimum cardinality of an x-monophonic set of G is defined as the x-monophonic number of G, denoted by mₓ(G). An x-monophonic set of cardinality mₓ(G) is called a mₓ-set of G. We determine bounds for it and characterize graphs which realize these bounds. A connected graph of order p with vertex monophonic numbers either p - 1 or p - 2 for every vertex is characterized. It is shown that for positive integers a, b and n ≥ 2 with 2 ≤ a ≤ b, there exists a connected graph G with radₘG = a, diamₘG = b and mₓ(G) = n for some vertex x in G. Also, it is shown that for each triple m, n and p of integers with 1 ≤ n ≤ p -m -1 and m ≥ 3, there is a connected graph G of order p, monophonic diameter m and mₓ(G) = n for some vertex x of G.
LA - eng
KW - monophonic path; monophonic number; vertex monophonic number
UR - http://eudml.org/doc/270812
ER -

## References

top
1. [1] F. Buckley and F. Harary, Distance in Graphs (Addison-Wesley, Redwood City, CA, 1990). Zbl0688.05017
2. [2] F. Buckley, F. Harary and L.U. Quintas, Extremal results on the geodetic number of a graph, Scientia A2 (1988) 17-26. Zbl0744.05021
3. [3] G. Chartrand, F. Harary and P. Zhang, On the geodetic number of a graph, Networks 39 (2002) 1-6, doi: 10.1002/net.10007. Zbl0987.05047
4. [4] G. Chartrand, G.L. Johns and P. Zhang, The detour number of a graph, Utilitas Mathematica 64 (2003) 97-113. Zbl1033.05032
5. [5] G. Chartrand, G.L. Johns and P. Zhang, On the detour number and geodetic number of a graph, Ars Combinatoria 72 (2004) 3-15. Zbl1073.05022
6. [6] F. Harary, Graph Theory (Addison-Wesley, 1969).
7. [7] F. Harary, E. Loukakis and C. Tsouros, The geodetic number of a graph, Math. Comput. Modeling 17(11) (1993) 87-95, doi: 10.1016/0895-7177(93)90259-2. Zbl0825.68490
8. [8] A.P. Santhakumaran and P. Titus, Vertex geodomination in graphs, Bulletin of Kerala Mathematics Association, 2(2) (2005) 45-57.
9. [9] A.P. Santhakumaran and P. Titus, On the vertex geodomination number of a graph, Ars Combinatoria, to appear. Zbl1265.05203
10. [10] A.P. Santhakumaran, P. Titus, The vertex detour number of a graph, AKCE International J. Graphs. Combin. 4(1) (2007) 99-112. Zbl1144.05028
11. [11] A.P. Santhakumaran and P. Titus, Monophonic distance in graphs, Discrete Mathematics, Algorithms and Applications, to appear. Zbl1222.05043

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.