IJPAM: Volume 96, No. 1 (2014)

THE MONOPHONIC GRAPHOIDAL COVERING
NUMBER OF A GRAPH

P. Titus$^1$, S. Santha Kumari$^2$
$^1$Department of Mathematics
University College of Engineering Nagercoil
Anna University
Tirunelveli Region
Nagercoil, 629 004, INDIA
$^2$Department of Mathematics
Udaya School of Engineering
Vellamodi, 629 204, INDIA


Abstract. A chord of a path $P$ is an edge joining two non-adjacent vertices of $P$. A path $P$ is called a monophonic path if it is a chordless path. A monophonic graphoidal cover of a graph $G$ is a collection $\psi_m$ of monophonic paths in $G$ such that every vertex of $G$ is an internal vertex of at most one monophonic path in $\psi_m$ and every edge of $G$ is in exactly one monophonic path in $\psi_m$. The minimum cardinality of a monophonic graphoidal cover of $G$ is called the monophonic graphoidal covering number of $G$ and is denoted by $\eta_m$. We determine bounds for it and characterize graphs which realize these bounds. Also, for any positive integer $n$ with $q - p + 2 \leq n \leq q - 1$, there exists a tree $T$ such that the monophonic graphoidal covering number is n.

Received: March 21, 2014

AMS Subject Classification: 05C70

Key Words and Phrases: graphoidal cover, acyclic graphoidal cover, geodesic graphoidal cover, monophonic path, monophonic graphoidal cover, monophonic graphoidal covering number

Download paper from here.



DOI: 10.12732/ijpam.v96i1.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: 2014
Volume: 96
Issue: 1
Pages: 37 - 45


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

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