The Connected Monophonic Number of a Graph

作者：Titus P^*; Ganesamoorthy K

来源：Graphs and Combinatorics, 2014, 30(1): 237-245.

DOI：10.1007/s00373-012-1260-1

• Monophonic path
• Monophonic number
• Connected monophonic number

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 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 defined as the monophonic number of G, denoted by m(G). A connected monophonic set of G is a monophonic set S such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected monophonic set of G is the connected monophonic number of G and is denoted by m (c) (G). We determine bounds for it and characterize graphs which realize these bounds. For any two vertices u and v in G, the monophonic distance d (m) (u, v) from u to v is defined as the length of a longest u - v monophonic path in G. The monophonic eccentricity e (m) (v) of a vertex v in G is the maximum monophonic distance from v to a vertex of G. The monophonic radius rad (m) G of G is the minimum monophonic eccentricity among the vertices of G, while the monophonic diameter diam (m) G of G is the maximum monophonic eccentricity among the vertices of G. It is shown that for positive integers r, d and n a parts per thousand yen 5 with r < d, there exists a connected graph G with rad (m) G = r, diam (m) G = d and m (c) (G) = n. Also, if a,b

• 出版日期2014-1