IJPAM: Volume 106, No. 2 (2016)

THE UPPER VERTEX MONOPHONIC NUMBER OF A GRAPH

P. Titus$^1$, K. Iyappan$^2$
$^1$Department of Mathematics
University College of Engineering Nagercoil
Anna University
Tirunelveli Region, Nagercoil, 629 004, INDIA
$^2$Department of Mathematics
V.V. College of Engineering
Tirunelveli, 627 657, INDIA


Abstract. For any vertex $x$ in a connected graph $G$ of order $p\geq 2$, a set $S\subseteq V(G)$ is an x-monophonic set of $G$ if each vertex $v\in 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_x(G)$. An $x$-monophonic set $S$ is called a minimal x-monophonic set if no proper subset of $S$ is an $x$-monophonic set. The upper x-monophonic number, denoted by $m_x^+(G)$, is defined as the maximum cardinality of a minimal $x$-monophonic set of $G$. We determine bounds for it and find the same for some special classes of graphs. For any two positive integers $a$ and $b$ with $1\leq a \leq b$, there exists a connected graph $G$ with $m_x(G)=a$ and $m_x^+(G)=b$ for some vertex $x$ in $G$. Also, it is shown that for any three positive integers $a$, $b$ and $n$ with $a\geq 2$ and $a\leq n\leq b$, there exists a connected graph $G$ with $m_x(G)=a$, $m_x^+(G)=b$ and a minimal $x$-monophonic set of cardinality $n$.

Received: October 9, 2015

AMS Subject Classification: 05C12

Key Words and Phrases: monophonic path, vertex monophonic set, vertex monophonic number, minimal vertex monophonic set, upper vertex monophonic number

Download paper from here.



DOI: 10.12732/ijpam.v106i2.4 How to cite this paper?

Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2016
Volume: 106
Issue: 2
Pages: 389 - 400


Google Scholar; DOI (International DOI Foundation); WorldCAT.

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).