Advanced
ON THE MONOPHONIC NUMBER OF A GRAPH
ON THE MONOPHONIC NUMBER OF A GRAPH
Journal of Applied Mathematics & Informatics. 2014. Jan, 32(1_2): 255-266
Copyright © 2014, Korean Society of Computational and Applied Mathematics
  • Received : January 11, 2013
  • Accepted : October 23, 2013
  • Published : January 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
A.P. SANTHAKUMARAN
P. TITUS
K. GANESAMOORTHY

Abstract
For a connected graph G = ( V,E ) of order at least two, a set S of vertices of G is a monophonic set of G if each vertex v of G lies on an x y monophonic path for some elements x and y in S . The minimum cardinality of a monophonic set of G is the monophonic number of G , denoted by m ( G ). Certain general properties satisfied by the monophonic sets are studied. Graphs G of order p with m ( G ) = 2 or p or p − 1 are characterized. For every pair a, b of positive integers with 2 ≤ a b , there is a connected graph G with m ( G ) = a and g ( G ) = b , where g ( G ) is the geodetic number of G . Also we study how the monophonic number of a graph is affected when pendant edges are added to the graph. AMS Mathematics Subject Classification : 05C12.
Keywords
1. Introduction
By a graph G = ( V,E ) we mean a finite undirected connected graph without loops or multiple edges. The order and size of G are denoted by p and q respec-tively. For basic graph theoretic terminology we refer to Harary [5] . For vertices u and v in a connected graph G , the distance d ( u, v ) is the length of a shortest u v path in G . An u v path of length d ( u, v ) is called an u v geodesic . It is known that d is a metric on the vertex set V of G . The neighborhood of a vertex v is the set N ( v ) consisting of all vertices u which are adjacent with v . The closed neighborhood of a vertex v is the set N [ v ] = N ( v )⋃{ v }. A vertex v is an extreme vertex if the subgraph induced by its neighbors is complete. The closed interval I [ x, y ] consists of all vertices lying on some x y geodesic of G , while for
PPT Slide
Lager Image
A set S of vertices is a geodetic set if I [ S ] = V , and the minimum cardinality of a geodetic set is the geodetic number g ( G ). A geodetic set of cardinality g ( G ) is called a g - set . The geodetic number of a graph was introduced in [1 , 6] and further studied in [2 , 4] . The detour distance D ( u, v ) between two vertices u and v in G is the length of a longest u v path in G . An u v path of length D ( u, v ) is called an u v detour . It is known that D is a metric on the vertex set V of G . The concept of detour distance was introduced and studied in [3] .
PPT Slide
Lager Image
A graph G with radmG = 3 and diammG = 5
A chord of a path P is an edge joining two non-adjacent vertices of P . A path P is called monophonic if it is a chordless path. For any two vertices u and v in a connected graph G , the monophonic distance dm ( u, v ) from u to v is defined as the length of a longest u v monophonic path in G . The monophonic eccentricity em ( v ) of a vertex v in G is em ( v ) = max { dm ( v, u ) : u V ( G )}. The monophonic radius , radmG of G is radmG = min { em ( v ) : v V ( G )} and the monophonic diameter , diammG of G is diammG = max { em ( v ) : v V ( G )}. A vertex u in G is monophonic eccentric vertex of a vertex v in G if em ( u ) = dm ( u, v ). For the graph G given in Figure 1 , d ( v 1 , v 4 ) = 2, D ( v 1 , v 4 ) = 6 and dm ( v 1 , v 4 ) = 4. Thus the monophonic distance is different from both the distance and the detour distance. The usual distance d and the detour distance D are metrics on the vertex set V of a connected graph G , whereas the monophonic distance dm is not a metric on V . For the graph G given in Figure 1 , dm ( v 4 , v 6 ) = 5, dm ( v 4 , v 5 ) = 1 and dm ( v 5 , v 6 ) = 1. Hence dm ( v 4 , v 6 ) > dm ( v 4 , v 5 ) + dm ( v 5 , v 6 ) and so the triangle inequality is not satisfied. It is clear that for vertices u and v in a connected graph G of order p , 0≤ d ( u, v )≤ dm ( u, v )≤ D ( u, v )≤ p − 1. The monophonic distance was introduced and studied in [7] . For the graph G given in Figure 1 , the monophonic distance between vertices and the monophonic eccentricities of vertices are given in Table 1 . Thus radmG = 3 and diammG = 5.
Monophonic eccentricities of the graphGgiven inFigure 1
PPT Slide
Lager Image
Monophonic eccentricities of the graph G given in Figure 1
The following theorems will be used in the sequel.
Theorem 1.1 ( [6] ). Each extreme vertex of a connected graph G belongs to every geodetic set of G .
Theorem 1.2 ( [6] ). For any tree T with k endvertices, g(T) = k .
Throughout this paper G denotes a connected graph with at least two vertices.
2. Monophonic number of a graph
Definition 2.1. A set S of vertices of a graph G is a monophonic set of G if each vertex v of G lies on an x y monophonic path in G for some x, y S . The minimum cardinality of a monophonic set of G is the monophonic number of G and is denoted by m ( G ).
Example 2.2. For the graph G given in Figure 2 , S 1 = { x,w } and S 2 = { u,w } are the minimum monophonic sets of G and so m ( G ) = 2.
PPT Slide
Lager Image
A graph G with m(G) = 2
A vertex v in a graph G is a monophonic vertex if v belongs to every minimum monophonic set of G . If G has a unique minimum monophonic set S , then every vertex in S is a monophonic vertex. In the next theorem, we show that there are certain vertices in a nontrivial connected graph G that are monophonic vertices of G .
Theorem 2.3. Each extreme vertex of a connected graph G belongs to every monophonic set of G. Moreover, if the set S of all extreme vertices of G is a monophonic set, then S is the unique minimum monophonic set of G.
Proof . Let u be an extreme vertex and let S be a monophonic set of G . Suppose that u S . Then u is an internal vertex of an x y monophonic path, say P , for some x, y S . Let v and w be the neighbors of u on P . Then v and w are not adjacent and so u is not an extreme vertex, which is a contradiction. Therefore u belongs to every monophonic set of G . The second part of the theorem is clear.
Corollary 2.4. For the complete graph Kp ( p ≥ 2), m ( Kp ) = p .
Theorem 2.5. Let G be a connected graph with a cutvertex v and let S be a monophonic set of G. Then every component of G v contains an element of S.
Proof . Suppose that there is a component B of G v such that B contains no vertex of S . Let u be any vertex in B . Since S is a monophonic set, there exists a pair of vertices x and y in S such that u lies in some x y monophonic path P : x = u 0 , u 1 , u 2 , ..., u , ..., un = y in G with u x, y . Since v is a cutvertex of G , the x u subpath P 1 of P and the u y subpath P 2 of P both contain v , it follows that P is not a path, which is a contradiction.
Theorem 2.6. No cutvertex of a connected graph G belongs to any minimum monophonic set of G.
Proof . Let v be a cutvertex of G and let S be a minimum monophonic set of G . Then by Theorem 2.5, every component of G v contains an element of S . Let U and W be two distinct components of G v and let u U and w W . Then v is an internal vertex of an u w monophonic path. Let S′ = S − { v }. It is clear that every vertex that lies on an u v monophonic path also lies on an u w monophonic path. Hence it follows that S′ is a monophonic set of G , which is a contradiction to S a minimum monophonic set of G .
Corollary 2.7. If T is a tree with k endvertices, then m ( T ) = k .
Proof . This follows from Theorem 2.3 and Theorem 2.6.
We denote the vertex connectivity of a connected graph G by k ( G ) or k .
Theorem 2.8. If G is a non - complete connected graph such that it has a minimum cutset consisting of k vertices, then m ( G ) ≤ p k .
Proof . Since G is a non-complete connected graph, it is clear that 1 ≤ k p −2. Let U = { u 1 , u 2 , u 3 , ..., uk } be a minimum cutset of G . Let G 1 , G 2 , ..., Gr , ( r ≥ 2) be the components of G U and let S = V U . Then every vertex ui (1 ≤ i k ) is adjacent to at least one vertex of Gj , for each j (1 ≤ j r ). It is clear that S is a monophonic set of G and so m ( G ) ≤ | S | = p k .
Remark 2.1. The bound in Theorem 2.8 is sharp. For the cycle C 4 , m ( C 4 ) = 2. Also k = 2 and p k = 2. Thus m ( G ) = p k .
The following theorem is clear.
Theorem 2.9. For any connected graph G , 2 ≤ m ( G ) ≤ p .
The bounds in the above theorem are sharp. For the complete graph Kp ( p ≥ 2), m ( Kp ) = p . The set of two endvertices of a path Pn ( n ≥ 2) is its unique minimum monophonic set so that m ( Pn ) = 2.
Theorem 2.10. For any integer k such that 2 ≤ k p there is a connected graph G of order p such that m ( G ) = k .
Proof . For k = p , the theorem follows from Corollary 2.4 by taking G = Kp . For 2 ≤ k p −1, the tree G given in Figure 3 has p vertices and it follows from Corollary 2.7 that m ( G ) = k .
PPT Slide
Lager Image
The graph G in Theorem 2.10 with m(G) = k
Now we proceed to characterize graphs G for which the bounds in Theorem 2.9 are attained.
Theorem 2.11. For any connected graph G of order p, m ( G ) = p if and only if G is complete.
Proof . Let m ( G ) = p . Suppose that G is not a complete graph. Then there exist two vertices u and v such that u and v are not adjacent in G . Since G is connected, there is a monophonic path from u to v , say P , with length at least 2. Let x be a vertex of P such that x u, v . Then S = V −{ x } is a monophonic set of G and hence m ( G ) ≤ p −1, which is a contradiction. The converse follows from Corollary 2.4.
Definition 2.12. Let x be any vertex in G . A vertex y in G is said to be an x - monophonic superior vertex if for any vertex z with dm ( x, y ) < dm ( x, z ), z lies on an x y monophonic path.
Example 2.13. For any vertex x in the cycle Cp ( p ≥ 4), V ( Cp ) − N [ x ] is the set of all x - monophonic superior vertices.
We give below a property related with monophonic eccentric vertex of x and x - monophonic superior vertex in a graph G .
Theorem 2.14. Let x be any vertex in G. Then every monophonic eccentric vertex of x is an x - monophonic superior vertex .
Proof . Let y be a monophonic eccentric vertex of x so that em ( x ) = dm ( x, y ). If y is not an x - monophonic superior vertex, then there exists a vertex z in G such that dm ( x, y ) < dm ( x, z ) and z does not lie on any x y monophonic path and hence em ( x ) ≥ dm ( x, z ) > dm ( x, y ), which is a contradiction.
Note 2.15. The converse of Theorem 2.14 is not true. For the cycle C 6 : v 1 , v 2 , v 3 , v 4 , v 5 , v 6 , v 1 , the vertex v 4 is a v 1 - monophonic superior vertex and it is not a monophonic eccentric vertex of v 1 .
Theorem 2.16. Let G be a connected graph. Then m ( G ) = 2 if and only if there exist two vertices x and y such that y is an x - monophonic superior vertex and every vertex of G is on an x y monophonic path .
Proof . Let m ( G ) = 2 and let S = { x, y } be a minimum monophonic set of G . If y is not an x - monophonic superior vertex, then there is a vertex z in G with dm ( x, y ) < dm ( x, z ) and z does not lie on any x y monophonic path. Thus S is not a monophonic set of G , which is a contradiction. The converse is clear from the definition.
Theorem 2.17. Let G be a connected graph of order p ≥ 3. Then m ( G ) = p −1 if and only if G = K 1 + ⋃ mjKj , where Σ mj ≥ 2.
Proof . Let G = K 1 + ⋃ mj Kj , where Σ mj ≥ 2. Then G has exactly one cutvertex and all other vertices are extreme and hence by Theorems 2.3 and 2.6, m ( G ) = p − 1. Conversely, let m ( G ) = p − 1. Let S be a monophonic set such that | S | = p − 1. Let v S . We show that v is a cutvertex of G . Otherwise, G v has just one component. By Theorem 2.3, v is not an extreme vertex of G . Hence there exist vertices x, y N ( v ) such that x and y are not adjacent in G v . Let P be an x y monophonic path in G v of length at least 2. Choose a vertex z on P such that z x, y . Note that z v . Then it is clear that S 1 = V − { v, z } is a monophonic set of G so that m ( G ) ≤ p − 2, which is a contradiction. Hence v is a cutvertex of G and by Theorem 2.6, v is the only cutvertex of G .
Now, let G 1 , G 2 , ..., Gr be the components of G v . First, we show that each Gi is complete. Suppose that some component, say G 1 , is not complete. Then there exist two vertices x and y in G 1 such that x and y are not adjacent. Choose a vertex z in an x y geodesic such that z x, y . Then S 2 = V − { v, z } is a monophonic set of G so that m ( G ) ≤ p − 2, which is a contradiction. Now, it remains to show that v is adjacent to every vertex of Gi for each i (1 ≤ i r ). Otherwise, there exists a component, say Gi , such that v is not adjacent to at least one vertex of Gi . Hence there is a vertex u in Gi such that u is not extreme in G . Then S 3 = V −{ v, u } is a monophonic set of G so that m ( G ) ≤ p −2, which is a contradiction. Hence G = K 1 +⋃ mjKj , where K 1 = { v } and Σ mj ≥ 2.
3. Bounds for the monophonic number of a graph
In the following theorem we give an improved upper bound for the mono-phonic number of a graph in terms of its order and monophonic diameter. For convenience, we denote the monoponic diameter diammG by dm itself.
Theorem 3.1. If G is a non - trivial connected graph of order p and monophonic diameter dm, then m ( G ) ≤ p dm + 1.
Proof . Let u and v be vertices of G such that dm ( u, v ) = dm and let P : u = v 0 , v 1 , ..., vdm = v be a u v monophonic path of length dm . Let S = V − { v 1 , v 2 , ..., vdm −1 }. Then it is clear that S is a monophonic set of G so that m ( G ) ≤ | S | = p dm + 1.
For the complete graph Kp ( p ≥ 2), dm = 1 and m ( Kp ) = p so that the bound in Theorem 3.1 is sharp.
A caterpillar is a tree for which the removal of all the endvertices gives a path.
Theorem 3.2. For every non-trivial tree T of order p and monophonic diameter dm, m ( T ) = p dm + 1 if and only if T is a caterpillar.
Proof . Let T be any non-trivial tree. Let P : u = v 0 , v 1 , ..., vdm be a monophonic diametral path. Let k be the number of endvertices of T and l be the number of internal vertices of T other than v 1 , v 2 , ..., vdm −1 . Then dm − 1 + l + k = p . By Corollary 2.7, m ( T ) = k and so m ( T ) = p dm l +1. Hence m ( T ) = p dm +1 if and only if l = 0, if and only if all the internal vertices of T lie on the monophonic diametral path P , if and only if T is a caterpillar.
For any connected graph G , radmG diammG . It is shown in [7] that every two positive integers a and b with a b are realizable as the monophonic radius and monophonic diameter, respectively, of some connected graph. This theorem can also be extended so that the monophonic number can be prescribed when radmG < diammG .
Theorem 3.3. For positive integers r, d and k ≥ 4 with r < d, there exists a connected graphs G such that radmG = r, diammG = d and m ( G ) = k .
Proof . We prove this theorem by considering two cases.
Case 1. r = 1. Then d ≥ 2. Let C d+2 : v 1 , v 2 , ..., v d+2 , v 1 be a cycle of order d +2. Let G be the graph obtained by adding k −2 new vertices u 1 , u 2 , ..., u k−2 to C d+2 and joining each of the vertices u 1 , u 2 , ..., u k−2 , v 3 , v 4 , ..., v d+1 to the vertex v 1 . The graph G is shown in Figure 4 . It is easily verified that 1 ≤ em ( x ) ≤ d for any vertex x in G and em ( v 1 ) = 1, em ( v 2 ) = d . Then radmG = 1 and diammG = d . Let S = { u 1 , u 2 , ..., u k−2 , v 2 , v d+2 } be the set of all extreme vertices of G . Since S is a monophonic set of G , it follows from Theorem 2.3 that m ( G ) = k .
Case 2. r ≥ 2. Then C : v 1 , v 2 , ..., v r+2 , v 1 be a cycle of order r +2 and let W = K 1 + C d+2 be the wheel with V ( C d+2 ) = { u 1 , u 2 , ..., u d+2 }, K 1 = { v 1 } and all other vertices distinct. Now, add k −3 new vertices w 1 , w 2 , ..., w k-3 and join each wi (1 ≤ i k − 3) to the vertex v 1 and obtain the graph G of Figure 5 . It is easily verified that r em ( x ) ≤ d for any vertex x in G and em ( v 1 ) = r and em ( u 1 ) = d . Thus radmG = r and diammG = d . Let S = { w 1 , w 2 , ..., w k-3 } be the set of all extreme vertices of G . By Theorem 2.3, every monophonic set of G contains S . It is clear that S is not a monophonic set of G . Let T = S ⋃ { u 1 , u 3 , v 3 }. It is easily verified that T is a minimum monophonic set of G and so m ( G ) = k .
PPT Slide
Lager Image
The graph G in Case 1 of Theorem 3.3
PPT Slide
Lager Image
The graph G in Case 2 of Theorem 3.3
Problem 3.4. For any three positive integers r, d and k ≥ 4 with r = d, does there exist a connected graph G with radm = r, diamm = d and m ( G ) = k?
Theorem 3.5. For each triple d, k, p of integers with 2 ≤ k p d +1 and d 2, there is a connected graph G of order p such that diammG = d and m ( G ) = k .
Proof . Let P d+1 : u 1 , u 2 , ..., u d+1 be a path of length d . Add p d −1 new vertices, v 1 , v 2 , ..., v k-2 , w 1 , w 2 , ..., w p-d-k+1 to P d+1 and join each wi (1 ≤ i p d k +1) to u 1 , u 2 and u 3 and also join each vj (1 ≤ j k -2) to u 2 , thereby producing the graph G of Figure 6 . Then G has order p and monophonic diameter d . If p d k + 1 ≤ 1, then S = { v 1 , v 2 , ..., v k-2 , u 1 , u d+1 } is the set of all extreme vertices of G . Since S is a monophonic set of G , it follows from Theorem 2.3 that m ( G ) = k . So, let p d k + 1 ≥ 2. If d = 2, then S 1 = { v 1 , v 2 , ..., v k-2 } is the set of all extreme vertices of G . It is clear that neither S 1 nor S 1 ⋃ { x } where x S 1 , is a monophonic set of G . Since S 2 = S 1 ⋃ { u 1 , u 3 } is a monophonic set of G , it follows from Theorem 2.3 that m ( G ) = k . If d ≥ 3, then S 3 = { v 1 , v 2 , ..., v k-2 , u d+1 } is the set of all extreme vertices of G . Now, S 3 is not a monophonic set of G . Since S 4 = S 3 ⋃ { u 1 } is a monophonic set of G , it follows from Theorem 2.3 that m ( G ) = k .
PPT Slide
Lager Image
The graph G in Theorem 3.5 with diammG = d and m(G) = k
Theorem 3.6. For any connected graph G of order p , 2 ≤ m ( G ) ≤ g ( G ) ≤ p .
Proof . Since every geodesic is a monophonic path, it follows that every geodetic set is a monophonic set, and hence m ( G ) ≤ g ( G ). The other inequalities are trivial.
Remark 3.1. The bounds in Theorem 3.6 are sharp. For the complete graph Kp , m ( Kp ) = g ( Kp ) = p . For a non-trivial path Pn , m ( Pn ) = g ( Pn ) = 2. Also, if G is a non-trivial tree, or an even cycle, or a complete bipartite graph, then m ( G ) = g ( G ). All the inequalities in Theorem 3.6 are strict. For the graph G given in Figure 7 , S = { v 6 , v 7 , v 3 } is a minimum monophonic set of G so that m ( G ) = 3 and no 3-elements subset of the vertex set is a geodetic set of G . Since S ∪ { v 1 } is a geodetic set of G , it follows that g ( G ) = 4. Thus we have 2 < m ( G ) < g ( G ) < p .
PPT Slide
Lager Image
A graph G in Remark 3.1 with 2 < m(G) < g(G) < p
In view of this remark, we have the following problem.
Problem 3.7. Characterize graphs G for which m ( G ) = g ( G )
Theorem 3.8. For every pair a, b of positive integers with 2 ≤ a b, there is a connected graph G with m ( G ) = a and g ( G ) = b .
Proof . For 2 ≤ a = b , any tree with a endvertices has the desired properties, by Theorem 1.2 and Corollary 2.7. So, assume that 2 ≤ a < b . Let Pi : xi , wi , yi (1 ≤ i b a ) be b a copies of a path of length 2 and P : v 1 , v 2 , v 3 , v 4 a path of length 3. Let G be the graph obtained by joining each xi (1 ≤ i b a ) in Pi and v 2 in P , joining each yi (1 ≤ i b a ) in Pi and v 4 in P ; and adding a − 1 new vertices u 1 , u 2 , ..., u a−1 and joining each ui (1 ≤ i a −1) to v 4 . The graph G is shown in Figure 8 . Let S = { vi , ui , ..., u a−1 } be the set of all extreme vertices of G . It is easily verified that S is a monophonic set of G and so by Theorem 2.3, m ( G ) = | S | = a .
PPT Slide
Lager Image
The graph G in Theorem 3.8 with m(G) = a and g(G) = b
Next, we show that g ( G ) = b . By Theorem 1.1, every geodetic set of G contains S . Clearly, S is not a geodetic set of G . It is easily verified that at least one of the vertex of each Pi (1 ≤ i b a ) must belong to every geodetic set of G . Since T = S ∪ { w 1 , w 2 , ..., w ba } is a geodetic set of G , it follows from Theorem 1.1 that T is a minimum geodetic set of G and so g ( G ) = b .
4. Monophonic number of a graph by adding some pendant edges
Theorem 4.1. If G′ is a graph obtained by adding l pendant edges to a connected graph G, then m ( G ) ≤ m ( G′ ) ≤ m ( G ) + l .
Proof . Let G′ be the connected graph obtained from G by adding l pendant edges uivi (1 ≤ i l ), where each ui (1 ≤ i l ) is a vertex of G and each vi (1 ≤ i l ) is not a vertex of G . Let S be a minimum monophonic set of G . Then S ∪ { v 1 , v 2 , ..., vl } is a monophonic set of set of G′ and so m ( G′ ) ≤ m ( G ) + l .
Now, we claim that m ( G ) ≤ m ( G′ ). Suppose that m ( G ) > m ( G′ ). Then let S ′ be a monophonic set of G′ with | S′ | < m ( G ). Since each vi (1 ≤ i l ) is an extreme vertex of G′ , it follows from Theorem 2.3 that { v 1 , v 2 , ..., vl } ⊆ S′ . Let S = ( S′ − { v 1 , v 2 , ..., vl }) ∪ { u 1 , u 2 , ..., ul }. Then S is a subset of V ( G ) and | S | = | S′ | < m ( G ). Now, we show that S is a monophonic set of G . Let w V ( G )− S . Since S′ is a monophonic set of G′ , w lies on an x y monophonic path P in G′ for some vertices x, y S′ . If neither x nor y is vi (1 ≤ i l ), then x, y S . If exactly one of x, y is vi (1 ≤ i l ), say x = vi . Then w lies on the ui y monophonic path in G obtained from P by removing vi . If both x, y ∈ { v 1 , v 2 , ..., vl }, then let x = vi and y = vj where i j . Hence w lies on the ui uj monophonic path in G obtained from P by removing vi and vj . Thus S is a monophonic set of G . Hence m ( G ) ≤ | S | < m ( G ), which is a contradiction.
Remark 4.1. The bounds for m ( G′ ) in Theorem 4.1 are sharp. Consider a tree T with number of endvertices k ≥ 3. Let S = { v 1 , v 2 , ..., vk } be the set of all endvertices of T . Then by Corollary 2.7, m ( G ) = k . If we add a pendant edge to an endvertex of T , then we obtain another tree T′ with k endvertices. Hence m ( T ) = m ( T′ ). On the otherhand, if we add l pendant edges to a cutvertex of T , then we obtain another tree T′′ with k + l endvertices. Then by Corollary 2.7, m ( T′ ) = m ( T ) + l .
Now, we proceed to characterize graphs G for which m ( G ) = m ( G′ ), where G′ is obtained from G by adding l pendant edges.
Theorem 4.2. Let G′ be a graph obtained from a connected graph G by adding l pendant edges uivi (1 ≤ i l ), where ui V ( G ) and vi V ( G ). Then m ( G ) = m ( G′ ) if and only if l m ( G ) and { u 1 , u 2 , ..., ul } is a subset of some minimum monophonic set of G .
Proof . Let l m ( G ) and let { u 1 , u 2 , ..., ul } be a subset of some minimum monophonic set S of G . Let S′ = ( S − { u 1 , u 2 , ..., ul }) ⋃ { v 1 , v 2 , ..., vl }. Then | S′ | = | S |. We show that S′ is a monophonic set of G′ . Let z V ( G′ ) − S′ . If z = ui (1 ≤ i l ), then z lies on every vi w monophonic path in G′ , where w S′ , since ui is the only vertex adjacent to vi . So we may assume that z ui (1 ≤ i l ). Since z is a vertex of G and S is a monophonic set of G , it follows that z lies on some x y monophonic path P in G for some x, y S . Then by an argument similar to the one used in the proof of Theorem 4.1, we can show that S′ is a monophonic set of G′ . Hence m ( G′ ) ≤ | S′ | = | S | = m ( G ). Now, the result follows from Theorem 4.1.
Conversely, let m ( G ) = m ( G′ ). Suppose that l > m ( G ). Since each vi (1 ≤ i l ) is an endvertex of G′ , by Theorem 2.3, m ( G′ ) ≥ l . Hence m ( G′ ) > m ( G ), which is a contradiction. Thus l m ( G′ ). Now, let S′ be a minimum monophonic set of G′ . Since each ui (1 ≤ i l ) is a cutvertex of G′ , it follows from Theorem 2.6 that ui S′ for 1 ≤ i l . Since each vi (1 ≤ i l ) is an endvertex of G′ , it follows from Theorem 2.3 that vi S′ for 1 ≤ i l . Let S = ( S′ − { v 1 , v 2 , ..., vl }) ⋃ { u 1 , u 2 , ..., ul }. Then S is a subset of V ( G ) and | S | = | S′ |. Then, as in the proof of Theorem 4.1, S is a monophonic set of G . Since | S | = | S′ | = m ( G′ ) = m ( G ), it follows that S is a minimum monophonic set of G that contains { u 1 , u 2 , ..., ul }.
Theorem 4.3. For each triple a, b and l of integers with 2 ≤ a b , 1 ≤ l b , and a + l b ≥ 0, there exists a connected graph G with m ( G ) = a and m ( G′ ) = b , where G′ is a graph obtained by adding l pendant edges to G .
Proof . Let G be a tree with number of endvertices a . Let G′ be a graph obtained by adding b a pendant edges to a cutvertex of G and also adding l + a b pendant edges each with different endvertices of G . Then G′ is another tree with b endvertices. By Corollary 2.7, m ( G ) = a and m ( G′ ) = b .
BIO
A. P. Santhakumaran received Ph.D. in Mathematics from Manonmaniam Sundaranar University, Tirunelveli. He was professor of Mathematics from 1977 to 2012 in St. Xavier’s College(Autonomous), Palayamkottai - 627 002, India. He is currently Professor of Mathematics in Hindustan University, Hindustan Institue of Technology and Science, Chennai 603 103. His research interests include convexiy, centrality and domination in graphs.
Department of Mathematics, Hindustan University, Hindustan Institute of Technology and Science, Chennai - 603 103, India.
e-mail: apskumar1953@yahoo.co.in
P. Titus received Ph.D. in Mathematics from Manonmaniam Sundaranar University, Tirunelveli. He has 15 years of teaching experience in Mathematics both in Engineering Colleges and Anna University. His research interests include geodomination, detour and monophonic concepts in graphs.
Department of Mathematics, University College of Engineering Nagercoil, Anna University, Tirunelveli Region, Nagercoil - 629 004, India.
e-mail: titusvino@yahoo.com
K. Ganesamoorthy received Ph.D. in Science and Humanities from Anna University, Chennai. Since 2009 he has been at University College of Engineering Nagercoil, Anna University, Tirunelveli Region, Nagercoil - 629 004, India. His research interests include detour, monophonic concepts in graphs.
Department of Mathematics, University College of Engineering Nagercoil, Anna University, Tirunelveli Region, Nagercoil - 629 004, India.
e-mail: kvgm 2005@yahoo.co.in
References
Buckley F. , Harary F. (1990) Distance in Graphs Addison-Wesley Redwood City, CA
Buckley F. , Harary F. , Quintas L.U. (1988) Extremal results on the geodetic number of a graph Scientia A2 17 - 26
Chartrand G. , Escuadro H. , Zhang P. (2005) Detour distance in graphs J. Combin. Math. Combin. Comput. 53 75 - 94
Chartrand G. , Harary F. , Zhang P. (2002) On the geodetic number of a graph Networks. 39 1 - 6    DOI : 10.1002/net.10007
Harary F. 1969 Graph Theory Addison-Wesley
Harary F. , Loukakis E. , Tsouros C. (1993) The geodetic number of a graph Math. Comput. Modeling 17 (11) 87 - 95
Santhakumaran A.P. , Titus P. (2011) Monophonic distance in graphs Discrete Mathematics, Algorithms and Applications 3 (2) 159 - 169    DOI : 10.1142/S1793830911001176