Extreme Monophonic Graphs and Extreme Geodesic Graphs

Main Article Content

P. Titus
A.P Santhakumaran

Abstract

For a connected graph $G=(V,E)$ of order at least two, 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 set of $G$ is a set $S$ of vertices such that every vertex of $G$ lies on a monophonic path joining some pair of vertices in $S$. The monophonic number of $G$ is the minimum cardinality of its monophonic sets and is denoted by $m(G)$. A geodetic set of $G$ is a set $S$ of vertices such that every vertex of $G$ lies on a geodesic joining some pair of vertices in $S$. The geodetic number of $G$ is the minimum cardinality of its geodetic sets and is denoted by $g(G)$. The number of extreme vertices in $G$ is its extreme order $ex(G)$. A graph $G$ is an extreme monophonic graph if $m(G)=ex(G)$ and an extreme geodesic graph if $g(G)=ex(G)$. Extreme monophonic graphs of order $p$ with monophonic number $p$ and $p-1$ are characterized. It is shown that every pair $a,b$ of integers with $0 \leq a \leq b$ is realized as the extreme order and monophonic number, respectively, of some graph. For positive integers $r,d$ and $k \geq 3$ with $r < d$, it is shown that there exists an extreme monophonic graph $G$ of monophonic radius $r$, monophonic diameter $d$, and monophonic number $k$. Also, we give a characterization result for a graph $G$ which is both extreme geodesic and extreme monophonic.

Article Details

How to Cite
Titus, P., & Santhakumaran, A. (2016). Extreme Monophonic Graphs and Extreme Geodesic Graphs. Tamkang Journal of Mathematics, 47(4), 393–404. https://doi.org/10.5556/j.tkjm.47.2016.2045
Section
Papers
Author Biography

P. Titus, Anna University, Chennai

Head of the department

References

F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley, Redwood City, CA, 1990.

G. Chartrand, F. Harary and P. Zhang, On the geodetic number of a graph, Networks, 39(2002), 1--6.

G. Chartrand and P. Zhang, Extreme Geodesic Graphs, Czechoslova Mathematical Journal, 52(2002), 771--780.

F.Harary, Graph Theory, Addison-Wesley, 1969.

F. Harary, E. Loukakis and C. Tsouros, The geodetic number of a graph, Math. Comput. Modeling, 17(1993), 87--95.

P. A. Ostrand, Graphs with specified radius and diameter, Discrete Math., 4(1973), 71-75.

A. P. Santhakumaran and P. Titus, Monophonic Distance in Graphs, Discrete Mathematics, Algorithms and Applications, 3(2011), 159--169.

A. P. Santhakumaran and P. Titus, A note on monophonic distance in graphs, Discrete Mathematics, Algorithms and Applications, 4(2012).

A. P. Santhakumaran, P. Titus and K. Ganesamoorthy, On the monophonic number of a graph, J. Appl. Math. & Informatics, 32(2014),255--266.