14_524_germina.dvi EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 3, No. 4, 2010, 748-764 ISSN 1307-5543 – www.ejpam.com Distance Neighbourhood Pattern Matrices Germina Kizhekekunnel Augustine1,2,∗, Alphy Joseph 2, Sona Jose 2 1 P.G. & Research Department of Mathematics, Mary Matha Arts & Science College (Kannur Univer- sity), Mananthavady-670645, India 2 Centre for Mathematical Sciences, Pala Campus, Arunapuram-686 574, Kerala, INDIA. Abstract. Let G = (V, E) be a given connected simple (p,q)-graph, and an arbitrary nonempty subset M ⊆ V (G) of G and for each v ∈ V (G), define N M j [u] = {v ∈ M : d(u, v) = j}. Clearly, then N j[u] = N V (G) j [u]. B.D. Acharya [2] defined the M-eccentricity of u as the largest integer for which N M j [u] 6= ; and the p× (dG + 1) nonnegative integer matrix DM G = (|N M j [vi]|), called the M -distance neighborhood pattern (or, M-dnp) matrix of G. The matrix D∗M G is obtained from DM G by replacing each nonzero entry by 1. Clearly, fM (u) = { j : N M j [u] 6= ;}. Hence, in particular, if fM : u 7→ fM (u) is an injective function, then the set M is a distance-pattern distinguishing set (or, a ‘DPD-set’ in short) of G and G is a dpd-graph. If fM(u)− {0} is independent of the choice of u in G then M is an open distance-pattern uniform (or, ODPU) set of G. A study of these sets is expected to be useful in a number of areas of practical importance such as facility location [5] and design of indices of “quantitative structure- activity relationships” (QSAR) in chemistry [3, 10]. This paper is a study of M -dnp matrices of a dpd-graph. 2000 Mathematics Subject Classifications: 05C78 Key Words and Phrases: Distance-pattern distinguishing sets, distance neighborhood pattern matrix, M -distance neighborhood pattern matrix. 1. Introduction For all terminology which are not defined in this paper, we refer the reader to F. Harary [5]. Unless mentioned otherwise, all the graphs considered in this paper are finite, simple and without self loops. On 26th November 2006, B.D. Acharya [2] conveyed to the first author the following defini- tions and problems for a detailed study. ∗Corresponding author. Email addresses: srgerminaka�gmail. om (G. Augustine), alphy22joseph�gmail. om (A. Joseph),sonamaryjose�yahoo. om (S. Jose) http://www.ejpam.com 748 c© 2010 EJPAM All rights reserved. G. Augustine, A. Joseph, S. Jose / Eur. J. Pure Appl. Math, 3 (2010), 748-764 749 Definition 1 ([2, 9]). Let G = (V, E) be a given connected simple (p,q)-graph, M ⊆ V (G) and for each u ∈ V (G), let fM (u) = {d(u, v) : v ∈ M} be the distance-pattern of u with respect to the marker set M. If fM is injective then the set M is a distance-pattern distinguishing set (or, a “dpd-set” in short) of G and G is a dpd-graph. If fM (u)−{0} is independent of the choice of u in G then M is an open distance-pattern uniform (or, odpu) set of G and G is called an odpu-graph. The minimum cardinality of a dpd-set (odpu-set) in G, if it exists, is the dpd-number(odpu- number) of G and it is denoted by ̺(G). B.D. Acharya [2], raised the following problems during the conversation. Problem 1. For what structural properties of the graph G, the function fM is injective? Problem 2. Characterize dpd-graphs having the given dpd-number. Problem 3. Which graphs G have the property that every k-subset of V (G) is a dpd-set of G. Solve this problem in particular when k = ̺(G)? Problem 4. Which graphs G have exactly one ̺(G)-set? Given a positive integer n, an n-distance coloring of a graph G is a coloring of the vertices of G in such a way that no two vertices at distance n are colored by the same color; G is n-distance colorable if it indeed admits such a coloring (e.g., see Sampathkumar, 1977 [13], 1988 [14]). Clearly, if G admits an n-distance coloring then 1≤ n≤ diam(G). Problem 5. For which values of n it is possible to extract a proper n-distance coloring of a given graph G using a distance-pattern function as a listing of colors for the vertices? Problem 6. Given any positive integer k, does there exist a graph G with ̺(G) = k? Some of the above mentioned problems studied are reported in the Technical Report [9]. B.D. Acharya, while sharing his many incisive thoughts, during the discussion, in June 2008, introduced a new approach namely, distance neighborhood pattern matrices (dnp-matrices), to study dpd-graphs. In this paper we initiate a study of dnp-matrices of a graph. For an arbitrarily fixed vertex u in G and for any nonnegative integer j, we let N j[u] = {v ∈ V (G) : d(u, v) = j}. Clearly, N0[u] = {u}, ∀ u ∈ V (G) and N j[u] = V (G) − V (Cu) whenever j exceeds the eccentricity ǫ(u) of u in the component Cu to which u belongs. Thus, if G is connected then, N j[u] = ; if and only if j > ǫ(u). If G is a connected graph then the vectors u = (|N0[u]|, |N1[u]|, |N2[u]|, . . . , |Nǫ(u)[u]|) associated with u ∈ V (G) can be arranged as a p× (dG + 1) nonnegative integer matrix DG given by        1 |N1[v1]| |N2[v1]| . . . |Nǫ(v1) [v1]| 0 0 0 1 |N1[v2]| |N2[v2]| . . . . . . |Nǫ(v2) [v2]| 0 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 |N1[vp]| |N2[vp]| . . . . . . . . . . . . |Nǫ(vp) [vp]|        where dG denotes the diameter of G; we call DG distance neighborhood pattern (or, dnp-) matrix of G. For a dnp-matrix the following observations are immediate. G. Augustine, A. Joseph, S. Jose / Eur. J. Pure Appl. Math, 3 (2010), 748-764 750 Observation 7. Since N0[u] = {u} for all u ∈ V (G), each entry in the first column of DG is equal to 1. Observation 8. Entries in the second column of DG corresponds to the degree of the correspond- ing vertices in G. Observation 9. In each row of DG, the entry zero will be after the nonzero entries. Proposition 1. For each u ∈ V (G) of a connected graph G, {N j[u] : N j[u] 6= ;, 0 ≤ j ≤ dG} gives a partition of V (G). Proof. If possible, let N j[u] ⋂ Nk[u] = v, for some u, v ∈ V (G), which implies d(u, v) = j and d(u, v) = k, and hence j = k. Therefore, N j[u] ⋂ Nk[u] = ; for any ( j, k) with j 6= k. Now, clearly, ⋃dG j=0 N j[u] ⊆ V (G). Also, for any v ∈ V (G), since G is connected, d(u, v) = k, for some k ∈ {0,1,2, . . . , dG}. That is, v ∈ Nk[u] for some k ∈ {0,1,2, . . . , dG}, which implies V (G) ⊆ ⋃dG j=0 N j[u]. Hence, ⋃dG j=0 N j[u] = V (G). Corollary 1. Each row of the dnp-matrix DG of a graph G is the partition of the order of G. Hence, sum of the entries in each row of the dnp-matrix DG of a graph G is equal to the order of G. 2. M-distance Neighborhood Pattern Matrix of a Graph Given an arbitrary nonempty subset M ⊆ V (G) of G and for each u ∈ V (G), define N M j [u] = {v ∈ M : d(u, v) = j}; clearly then N V (G) j [u] = N j[u]. One can define the M - eccentricity of u as the largest integer for which N M j [u] 6= ; and the p× (dG + 1) nonnegative integer matrix DM G = (|N M j [u]|) is called the M -distance neighborhood pattern (or M -dnp) matrix of G. D∗MG is obtained from DM G by replacing each nonzero entry by 1. Acharya [2] defined dnp matrix of any graph and in particular, M-dnp matrix of a dpd-graph as follows: Definition 2. Let G = (V, E) be a given connected simple (p,q)-graph, ; 6= M ⊆ V (G) and u ∈ V (G). Then, the M-distance-pattern of u is the set fM (u) = {d(u, v) : v ∈ M}. Clearly, fM (u) = { j : N M j [u] 6= ;}. Hence, in particular, if fM : u 7→ fM (u) is an injective function then the set M is a distance-pattern distinguishing set (or, a “dpd-set”in short) of G and if fM (u)−{0} is independent of the choice of u in G then M is an open distance-pattern uniform (or, odpu) set of G. A graph G with a dpd-set(odpu-set) is called a dpd-(odpu-)graph. Following are some interesting results on M -dnp matrix of a connected graph G. Observation 10. Both DM G and D∗MG do not admit null rows. Proposition 2. For each ui ∈ V (G), N M 0 [ui] = ¨ ui if ui ∈ M ; if ui 6∈ M Therefore, the entries in the first column of DM G and D∗MG will either be 0 or 1. G. Augustine, A. Joseph, S. Jose / Eur. J. Pure Appl. Math, 3 (2010), 748-764 751 Remark 1. It should note that Observation 9 is not true in the case of DM G . Corollary 2. The sum of the entries in the first column of DM G and D∗MG is equal to |M |. Lemma 1 is similar to Proposition 1. Lemma 1. For each u ∈ V (G), of a connected graph G, {N M j [u] : N M j [u] 6= ;, 0 ≤ j ≤ dG} is a partition of M. Proof. Let N M j [u] ⋂ N M k [u] = v, for some u ∈ V (G), v ∈ M . Then d(u, v) = j and d(u, v) = k, and hence j = k. Therefore, N M j [u] ⋂ N M k [u] = ; for j 6= k. Now, ⋃dG j=0 N M j [u] ⊆ M is trivial. Also, for any vertex v ∈ M , since G is connected d(u, v) = k, for some k ∈ {0,1,2, . . . , dG}. That is, v ∈ N M k [u] for some k ∈ {0,1,2, . . . , dG}. Hence, v ∈ ⋃dG j=0 N M j [u], which implies M ⊆ ⋃dG j=0 N M j [u]. Hence, ⋃dG j=0 N M j [u] = M . Corollary 3. Each row of DM G is a partition of |M |. Corollary 4. Sum of the entries in each row of DM G gives |M | and sum of the entries in each row of D∗MG is less than or equal to |M |. 3. M-dnp Matrix of a dpd-graph In this section we investigate some interesting results of DM G (D ∗M G ) of a dpd-graph. From the definition of D∗MG , we have the following important observations. Observation 11. In any graph G, a nonempty M ⊆ V (G) is a dpd-set if and only if no two rows of D∗MG are identical. Observation 12. If M is a dpd-set of a dpd-graph G, no row in D∗MG is a scalar multiple of any other row. Remark 2. For any ; 6= M ⊆ V (G), if the rows of D∗MG are linearly independent, M is a dpd-set. However, the converse need not be true. For example, let G be a graph obtained by attaching two vertices u1 and u2 to two adjacent vertices v4 and v5 respectively of the cycle C5 : v1v2v3v4v5. Choose M = {v2, v3,u1}. Then, D∗MG =            1 1 1 0 1 1 0 1 0 1 1 1 1 0 1 1 0 1 1 0 0 0 1 0 0 0 0 1            In D∗MG the third row is the sum of fifth and seventh rows. G. Augustine, A. Joseph, S. Jose / Eur. J. Pure Appl. Math, 3 (2010), 748-764 752 Lemma 2. Let G be a graph with dpd-set M. If there exists a row say, Rm, in D∗MG as the sum of any other rows, say, R1,R2, . . . ,Rk then, each column sum of the sub matrix formed by R1,R2, . . . ,Rk is either 0 or 1. Proof. Let C j : j = 1,2, . . . , (dG + 1) be the j th column sum of the sub-matrix formed by R1,R2, . . . ,Rk. Assume C j = c where c is a constant not equal to 0 or 1 for some j. Then the j th entry in row Rm is, c 6= 0, 1, which is a contradiction to the fact that D∗MG is a (0,1)−matrix. Proposition 3. Any dpd-graph G, with dpd-set M and the M-dnp matrix DM G as an identity matrix of order n is isomorphic to a path Pn on n vertices with dpd-set M as any of its pendent vertices. Proof. Let G be a graph with dpd-set M such that DM G ∼= In, the identity matrix of order n. From Corollary 4, sum of the entries in each row of DM G = |M |. Hence |M | = 1, since, DM G ∼= In. Since |M | = 1, M = {x}, where x is any vertex in G. We claim that x is a pendent vertex. If possible assume there exists at least two vertices v1, v2 ∈ V (G) adjacent to x . Then the rows corresponding to v1 and v2 in DM G will be � 0 1 0 . . . 0 0 0 1 0 . . . 0 0 � , which is not possible since, DM G ∼= In. Therefore, x is a pendent vertex. Now we prove that G ∼= Pn, a path on n vertices. Since, DM G ∼= In, O(G) = n and dG = n− 1. Since dG = n− 1, G contains a path of length n− 1. Since O(G) = O(Pn) = n, number of vertices of G and Pn are same. Now, if G � Pn, G contains at least one edge other than the edges of Pn, which is not possible, since dG = n− 1. Hence, G ∼= Pn, the path on n vertices. For the converse, consider the path Pn = v1v2 . . . vn with dpd-set M as any of its pendent vertices. Then, DM G = In =      1 0 0 . . . 0 0 1 0 . . . 0 . . . . . . . . . . . . . . . 0 0 0 . . . 1      Proposition 4. Let G be a dpd-graph. Then the dnp-matrix DM G of G is a diagonal matrix if and only if all the diagonal entries in DM G are unity. Also, DM G can neither be upper triangular nor lower triangular. Proof. Let G be graph with dpd-set M and M -dnp matrix DM G , a diagonal matrix say, D. By Proposition 2, entries in the first column of DM G are 0 or 1 and by Observation 10, DM G does not admit null rows, hence, a11 = 1. Also, by Corollary 4, the sum of the entries in each row of DM G = |M |. Therefore, from first row of D, |M | = 1 and hence aii = 1 ∀ i = 2,3, . . . , n. Hence D ∼= In. Converse part follows from Proposition 3. For the second part of the theorem, assume that G is a graph with dpd-set M and DM G as an upper triangular matrix with atleast one nonzero entry above the main diagonal. From G. Augustine, A. Joseph, S. Jose / Eur. J. Pure Appl. Math, 3 (2010), 748-764 753 Proposition 2, the entries in the first column of DM G are either 0 or 1. Also, from Corollary 2 sum of the entries in the first column of DM G = |M |. Hence a11 = 1 and |M | = 1. From Corollary 4, sum of the entries in each row of DM G = |M |. Hence, in each row, the nonzero entry appears in exactly one place and is unity. DM G being an upper triangular matrix, the entry 1 cannot be below the main diagonal and DM G contains atleast one nonzero entry above the main diagonal, which in turn implies, DM G contains identical rows, a contradiction. By a similar argument, we can prove that DM G is not a lower triangular matrix. 4. Main Results Theorem 13. For any graph G = (V, E), there exists no dpd-set M of cardinality 2. Proof. Suppose there exists a dpd-graph G with a dpd-set M of cardinality 2. Let us choose M = {x , y}, where x and y are arbitrary vertices in G. Then D∗MG contains 2× (dG + 1) sub- matrix so that rows of the sub-matrix represent the M-distance neighborhood pattern(M-dnp) of x and M-distance neighborhood pattern(M-dnp) of y in D∗MG . Hence, the entry 1 can be only at the first and (d(x , y) + 1)th columns, and the rows will be of the following form � 1 0 0 . . . 1 0 . . . 0 1 0 0 . . . 1 0 . . . 0 � Hence, D∗MG contains identical rows and so M is not a dpd-set. Theorem 14. For any (p,q)-graph G, V (G) is a dpd-set if and only if G is isomorphic to K1, the trivial graph. Proof. Assume that G is isomorphic to K1. Clearly, K1 has the dpd-set M = {v} where V (K1) = {v}. Converse follows from the fact when M = V (G), the rows in the dnp-matrix D∗MG correspond- ing to the diametrically opposite vertices are identical. Hence, G can have exactly one row and column (i.e., exactly one vertex) and hence is isomorphic to K1. Theorem 15. The complete graph Kn possess a dpd-set if and only if n≤ 2. Proof. Suppose G ∼= Kn has a dpd-set M with cardinality k. Then the first k rows of DM G represent the M-dnp of those vertices which belongs to M and the remaining n− k rows represent the M-dnp of those vertices which are not in M . G. Augustine, A. Joseph, S. Jose / Eur. J. Pure Appl. Math, 3 (2010), 748-764 754 That is, DM G =                  1 k− 1 1 k− 1 · · · · · · · · · · · · 1 k− 1 0 k 0 k · · · · · · · · · · · · 0 k                  Hence, D∗MG =                1 1 1 1 · · · · · · · · · · · · 1 1 0 1 · · · · · · · · · · · · 0 1                Clearly, when n ≥ 3, D∗MG contains identical rows and hence M is not a dpd-set. Converse follows from Theorem 14 and proposition 3. Theorem 16. Complete bipartite graph Km,n possess a dpd-set M if and only if either m = n= 1 or m= 1, n= 2 . Proof. Let G ∼= Km,n be a complete bipartite graph with partition of the vertex set as P1 and P2 with |P1| = m and |P2| = n. Assume Km,n possess a dpd-set M such that |M | = k. Let M = {v1, v2, . . . , vk} where {v1, v2, . . . , vr} ∈ P1 and {vr+1, vr+2, . . . , vk} ∈ P2. Then the first k rows of D∗MG represent the M-dnp of the vertices in M . In this k rows, the first r rows represent the M-dnp of the vertices which are in P1 and the remaining k− r rows represent the M-dnp of the vertices which are in P2. The remaining (m+ n)− k rows represent the M-dnp of the vertices which are not in M . Now, in this (m+ n)− k rows, the first m− r rows represent the M-dnp of the vertices in P1 and the remaining n−(k− r) rows represent the M-dnp of vertices which are in P2. Case 1: r ≥ 2 and k− r ≥ 2 G. Augustine, A. Joseph, S. Jose / Eur. J. Pure Appl. Math, 3 (2010), 748-764 755 Then, D∗MG =            1 1 1 1 1 1 . . . . . . . . . 1 1 1 0 1 1 . . . . . . . . . 0 1 1            Since r ≥ 2 and k− r ≥ 2, D∗MG contains identical rows and hence, M is not a dpd-set. Case 2: r = 1 and k− r ≥ 2 D∗MG =            1 1 0 1 1 1 . . . . . . . . . 1 1 1 0 1 1 . . . . . . . . . 0 1 1            Since, k− r ≥ 2, D∗MG contains identical rows and hence, M is not a dpd-set. Case 3: r = 0 and k− r ≥ 2 D∗MG =                1 0 1 . . . . . . . . . 1 0 1 0 1 0 . . . . . . . . . 0 1 0 0 0 1 . . . . . . . . . 0 0 1                Since, k− r ≥ 2, D∗MG will have identical rows and hence, M is not a dpd-set. Case 4: r = 1 and k− r = 1 In this case, k = |M |= 2. Therefore, by Theorem 13, M is not a dpd-set. Case 5: r = 0 and k− r = 1 D∗MG =            1 0 0 0 1 0 . . . . . . . . . 0 1 0 0 0 1 . . . . . . . . . 0 0 1            G. Augustine, A. Joseph, S. Jose / Eur. J. Pure Appl. Math, 3 (2010), 748-764 756 Hence, from D∗MG it is clear that D∗MG contains nonidentical rows only if either m = 1, n= 1 or m= 1, n= 2. Converse follows from proposition 3. Corollary 5. The star graph K1,n admits a dpd-set M if and only if n≤ 2. Theorem 17. For a dpd-graph G with a dpd-set M of |M | = 3, the vertices in M should be at distinct distances from each other. Proof. Let G be a dpd-graph with dpd-set M = {v1, v2, v3}. Let us denote d(v1, v2) = k1, d(v2, v3) = k2 and d(v1, v3) = k3. Case 1: d(v1, v2) = d(v2, v3) = d(v1, v3) = k In this case D∗MG has a 3 × (dG + 1) sub-matrix where the rows represent the M-dnp of the vertices v1, v2 and v3 respectively, with entries 1 only at the first and (k + 1)th columns.    1 0 . . . 0 1 0 . . . 0 1 0 . . . 0 1 0 . . . 0 1 0 . . . 0 1 0 . . . 0    Therefore, D∗MG contains identical rows and hence, M is not a dpd-set. Case 2: k1 = k2 6= k3 In this case, D∗MG has a 2× (dG + 1) sub-matrix where the rows represent the M-dnp of the vertices v1 and v3 respectively with entries 1 only at the first, (k1+1)th and (k3+1)th columns. � 1 0 . . . 0 1 0 . . . 0 1 0 . . . 0 1 0 . . . 0 1 0 . . . 0 1 0 . . . 0 � Hence, D∗MG has identical rows and M is not a dpd-set. Case 3: k1 6= k2 6= k3 In this case, the first, second and the third rows represent the M-dnp of the vertices v1, v2 and v3 respectively in D∗MG , with entries 1 only at the first, (k1 + 1)th, (k2 + 1)th and the (k3 + 1)th columns.    1 0 . . . 0 1 0 . . . 0 0 0 . . . 0 1 0 . . . 0 1 0 . . . 0 1 0 . . . 0 1 0 . . . 0 0 0 0 0 1 0 . . . 0 0 0 . . . 0 1 0 . . . 0 1 0 . . . 0    Hence, it is possible to form a dpd-set M with |M | = 3 in this case. However, any subset M = {v1, v2, v3} ⊆ V (G), satisfying the condition stated in Theo- rem 17, is not a sufficient condition for M to be a dpd-set. Consider C6 = (v1v2 . . . v6), with M = {v1, v2, v4} which are at distinct distances, but clearly do not form a dpd-set. G. Augustine, A. Joseph, S. Jose / Eur. J. Pure Appl. Math, 3 (2010), 748-764 757 Theorem 18. A cycle G ∼= Cn of order n admits a dpd-set if and only if n≥ 7. Proof. Let Cn = (v1v2 . . . vnv1) be a cycle on n vertices. Case 1: n, an even integer and n≥ 8 Let M = {v1, v2, v4}. Then, D∗MG =                             1 1 0 1 0 0 . . . 0 0 0 0 0 0 1 1 1 0 0 0 . . . 0 0 0 0 0 0 0 1 1 0 0 0 . . . 0 0 0 0 0 0 1 0 1 1 0 0 . . . 0 0 0 0 0 0 0 1 0 1 1 0 . . . 0 0 0 0 0 0 0 0 1 0 1 1 . . . 0 0 0 0 0 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 0 0 0 0 0 . . . 0 1 0 1 1 0 0 0 0 0 0 0 . . . 0 0 1 0 1 1 0 0 0 0 0 0 . . . 0 0 0 1 1 1 0 0 0 0 0 0 . . . 0 0 0 1 1 0 0 0 0 0 0 0 . . . 0 0 1 1 0 1 0 0 0 0 0 0 . . . 0 1 1 0 1 0 0 0 0 0 0 0 . . . 1 1 0 1 0 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 1 1 0 1 0 . . . 0 0 0 0 0 0                             , where the rows of D∗MG represent the M -dnp of the vertices v1, v2, . . . , vn taken in order. Now, we can partition D∗MG in to two sub-matrices say, A and B where A is a n 2 × ( n 2 + 1) sub-matrix of the form              1 1 0 1 0 0 . . . 0 0 0 0 0 1 1 1 0 0 0 . . . 0 0 0 0 0 0 1 1 0 0 0 . . . 0 0 0 0 0 1 0 1 1 0 0 . . . 0 0 0 0 0 0 1 0 1 1 0 . . . 0 0 0 0 0 0 0 1 0 1 1 . . . 0 0 0 0 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 0 0 0 0 0 . . . 1 0 1 1 0              , If we denote the columns of A as (c1, c2, . . . , cdG+1), then B is such that, the columns of B are (cdG+1, . . . , c2, c1). Looking at the rows of A and B, it is clear that the rows of D∗MG are not identical, and hence, {v1, v2, v4} form a dpd-set. Case 2: n, an odd integer and n≥ 7 G. Augustine, A. Joseph, S. Jose / Eur. J. Pure Appl. Math, 3 (2010), 748-764 758 Let M = {v1, v2, v4}. Then, D∗MG =                             1 1 0 1 0 0 . . . 0 0 0 0 0 0 1 1 1 0 0 0 . . . 0 0 0 0 0 0 0 1 1 0 0 0 . . . 0 0 0 0 0 0 1 0 1 1 0 0 . . . 0 0 0 0 0 0 0 1 0 1 1 0 . . . 0 0 0 0 0 0 0 0 1 0 1 1 . . . 0 0 0 0 0 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 0 0 0 0 0 . . . 0 0 1 0 1 1 0 0 0 0 0 0 . . . 0 0 0 1 0 1 0 0 0 0 0 0 . . . 0 0 0 0 1 1 0 0 0 0 0 0 . . . 0 0 0 1 1 1 0 0 0 0 0 0 . . . 0 0 1 1 0 1 0 0 0 0 0 0 . . . 0 1 1 0 1 0 0 0 0 0 0 0 . . . 1 1 0 1 0 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 1 1 0 1 0 . . . 0 0 0 0 0 0                             where rows of D∗MG represent the M-dnp of the vertices v1, v2, . . . , vn taken in order. In this case, D∗MG can have three sub-matrices A, B, C as its partition as described below. Choose the sub-matrix Að n 2 ñ× (dG + 1) as              1 1 0 1 0 0 . . . 0 0 0 0 0 1 1 1 0 0 0 . . . 0 0 0 0 0 0 1 1 0 0 0 . . . 0 0 0 0 0 1 0 1 1 0 0 . . . 0 0 0 0 0 0 1 0 1 1 0 . . . 0 0 0 0 0 0 0 1 0 1 1 . . . 0 0 0 0 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 0 0 0 0 0 . . . 0 1 0 1 1              We choose B as 3× (dG + 1) sub-matrix of D∗MG , which is of the form    0 0 0 0 0 0 . . . 0 0 0 1 0 1 0 0 0 0 0 0 . . . 0 0 0 0 1 1 0 0 0 0 0 0 . . . 0 0 0 1 1 1    Also, choose C as ((n− 3)− ð n 2 ñ)× (dG + 1) sub-matrix of D∗MG , which is of the form,        0 0 0 0 0 0 . . . 0 0 1 1 0 1 0 0 0 0 0 0 . . . 0 1 1 0 1 0 0 0 0 0 0 0 . . . 1 1 0 1 0 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 1 1 0 1 0 . . . 0 0 0 0 0 0        G. Augustine, A. Joseph, S. Jose / Eur. J. Pure Appl. Math, 3 (2010), 748-764 759 None of the rows of the sub-matrices of A, B and C are identical and hence the rows of D∗MG are not identical. Therefore, for any cycle Cn, n≥ 7 there exist a dpd-set. Now to complete the proof of the theorem it is enough to prove that Cn is not a dpd- graph for n≤ 6. Case 3: n= 3. Since C3 is a complete graph by Theorem 15, C3 is not a dpd-graph. Case 4: n= 4 or n = 5. Subcase 1: |M | = 1. Let M = {v}; v ∈ V (G). Then the rows represent the M-dnp of the adjacent vertices of v gives a 2× (dG + 1) sub-matrix of D∗MG of the form � 1 1 0 0 . . . 0 1 1 0 0 . . . 0 � in which the rows are identical. Hence, M is not a dpd-set. Subcase 2: |M | = 2. By Theorem 13, there exist no dpd-set M of cardinality 2. Subcase 3: |M | = 3 For C4 and C5 we cannot find a dpd-set M with |M | = 3, in which the vertices of M are at distinct distances from each other. Hence, by Theorem 17 there exist no dpd-set M with |M | = 3 for C4 and C5. Subcase 4: |M | = 4. By Theorem 14, C4 doesn’t have a dpd-set M with |M | = 4 and for C5, M with any four vertices of C5 gives D∗MG as: D∗MG =        1 1 1 1 1 1 1 1 1 1 1 1 0 1 1        in which the rows are identical. Hence, M is not a dpd-set. Subcase 5: |M | = 5. By Theorem 14, C5 cannot have a dpd-set M with |M | = 5. Thus C4 and C5 are not dpd-graphs. Case 5: n= 6. As in Case 4, M with |M | = 1 and |M | = 2 are not possible. G. Augustine, A. Joseph, S. Jose / Eur. J. Pure Appl. Math, 3 (2010), 748-764 760 Let |M | = 3. Then, any dpd-set M satisfies Theorem 17, has D∗MG as: D∗MG =          1 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 0 1 1 0          in which third and sixth rows are identical. Hence, M with |M | = 3, is not a dpd-set for C6. Let C6 has a dpd-set M with |M | = 4. Subcase 1: Let M = {v1, v2, v3, v4} D∗MG =          1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1          in which there are identical rows and hence, M is not a dpd-set. Subcase 2: M = {v1, v3, v4, v5} D∗MG =          1 0 1 1 0 1 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 1 1          in which there are identical rows and hence, M is not a dpd-set. Subcase 3: M = {v1, v3, v4, v6} D∗MG =          1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1          in which there are identical rows and hence, M is not a dpd-set. By symmetry, similar argument follows for the other choices of four vertices in M and hence, C6 doesn’t have a dpd-set with |M | = 4. G. Augustine, A. Joseph, S. Jose / Eur. J. Pure Appl. Math, 3 (2010), 748-764 761 Now, let C6 has a dpd-set M of |M | = 5. Then, D∗MG =          1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1          in which there are identical rows and hence, M is not a dpd-set. Thus, for C6, a dpd-set M with |M | = 5 is not possible. By Theorem 14, C6 cannot possess a dpd-set M with |M | = 6. Thus C6 is not a dpd-graph. Theorem 19. The set of all vertices in a diametrical path of a graph G cannot form a dpd-set. Proof. Let Pn = v1, v2, . . . , vn be an arbitrary diametrical path of G, where M = {v1, v2, . . . , vn} be a dpd-set of G. Then, the rows representing the M-dnp of the antipodal vertices v1 and vn in D∗MG forms a 2× (dG + 1) sub matrix as � 1 1 . . . 1 1 1 1 . . . 1 1 � Hence, M is not a dpd-set. Theorem 20. For all non-trivial dpd-graphs G, the number of nonzero entries in the first column of DM G is less than the number of rows. In particular, all the nonzero entries in the first column of DM G are unity. Proof. By Proposition 2, all the nonzero entries in the first column are unity. If possible, let the number of entries in the first column of DM G is equal to the number of rows. Since, all the nonzero entries in the first column are unity, |N M 0 (ui)| = 1 ∀ui ∈ V (G), which implies, N M 0 (ui) = {ui} ∀ui ∈ V (G). Hence, ui ∈ M ∀ui ∈ V (G). Therefore, by Theorem 14, G ≅ K1. Corollary 6. Let G be a nontrivial graph with dpd-set M and M-dnp matrix DM G as an n× n square matrix. Then, the number of nonzero entries in the first column ≦ n− 1. Theorem 21. Let G be a graph with a dpd-set M. Then, the M-dnp matrix DM G is a square matrix of order n if and only if G ≅ Pn, path on n vertices. Proof. Assume that the M -dnp matrix DM G of dpd-graph G is a square matrix of order n. Then O(G) = n and dG = n − 1. Since dG = n − 1, G contains a path P of length n − 1. Since O(G) = O(P) = n, the number of vertices of G and P are same. Therefore, if G � P, G contains at least one edge connecting the nonadjacent vertices of P, which is not possible since, in this case dG < n− 1, a contradiction. Hence, G ≅ Pn. Conversely, let G be a path on n vertices with dpd-set M and M -dnp matrix DM G . Then, DM G is a square matrix of order n, since the number of vertices of G is n and dG = n− 1 . G. Augustine, A. Joseph, S. Jose / Eur. J. Pure Appl. Math, 3 (2010), 748-764 762 Corollary 7. Let G be a graph with dpd-set M and the M-dnp matrix DM G as an invertible matrix. Then G ≅ Pn, a path on n vertices. Theorem 22. Let G be a graph with dpd-set M and the M-dnp matrix DM G is such that the rows of DM G are the elements of a basis of the Euclidean space Rn. Then G ≅ Pn, a path on n vertices. Proof. Since the rows of DM G are the elements of a basis of Rn, DM G is a square matrix of order n. Therefore, G ≅ Pn, a path on n vertices. Remark 3. In Proposition 3, we proved that if the rows of D∗MG are the elements of the standard basis of the Euclidean space Rn, then G is a path Pn on n vertices with the dpd-set M as one of its pendent vertices. Remark 4. The converse of Theorem 22 and Corollary 7 need not be true. Consider the path P7 = v1v2v3 . . . v7. Let M = {v1, v2, v3, v4, v5, v7}. Then, M is a dpd-set. Now DM G is a square matrix, but the rows of DM G are not linearly independent. Therefore, the rows cannot form the basis elements of R7. Also note that DM G is not invertible. Remark 5. All invertible matrices need not be a M-dnp matrix DM G of a graph G. For example A=    1 2 3 3 2 1 0 0 1    is invertible but not a M-dnp, since the row sums are not equal. From above discussion, it is interesting to investigate those M−dnp matrices DM G that are invertible. Also, distinguishing those invertible matrices which are M -dnp matrix of a graph is an open problem. Problem 23. Characterize those invertible matrices, which are the M-dnp of some graph G. 5. Conclusion and Scope As well known, apart from theoretical interest in the study of the distance matrix, such as the realization of a given matrix as the distance matrix of a graph [12], it has found applications in many practically interesting areas such as Quantitative Structure-Activity Re- lation (QSAR) in discrete mathematical chemistry [3] and studies on the effect of indirect qualitative relationships between individuals in a social network [7, 11]. Also, the M-Weiner index WM (G) may be defined as the sum of the entries in the upper triangular half of the M -distance matrix DM G ; by a partial Weiner index W ′(G), we mean the M -Weiner index of G for some nonempty proper subset M of V (G) and the well known Weiner index W (G) [11] is then seen as the M -Weiner index with M = V (G). An interesting question for chemists would be the following. REFERENCES 763 Problem 24. Consider any structure-activity relationship R of a molecular graph that has been identified to be well correlated with the Weiner index. Is it possible to achieve such a correlation using M-Weiner index for as low cardinality (dpd-)sets M as possible? [Choice of marker sets M in the molecular graph might be very crucial and hence might involve deeper insights into the molecular characteristics.] ACKNOWLEDGEMENTS Authors deeply indebted to B.D. Acharya for suggesting the con- cept of dnp-matrices of a dpd-graph and sparing his valuable time in sharing his many incisive thoughts to propel our vigorous discussion on the content of this paper. The work reported in this note is a part of the research work done under the project No.SR/S4/MS:287/05 funded by the Department of Science & Technology (DST), Govt. of India, New Delhi. The first author is thankful to the Department of Science & Technology, Government of India for supporting this research under the project No. SR/S4/MS:277/06, Govt. of India, New Delhi. References [1] B.D. Acharya. Contributions to the theories of Graphs, Graphoids and Hypergraphs. PhD thesis, The Indian Institute of Technology, Bombay, 1975. [2] B.D. Acharya. Personal communication, November, 2006. [3] S.C. Basak, D. Mills and B.D. Gute. Predicting bioactivity and toxicity of chemicals from mathematical descriptors: A chemical-cum-biochemical approach. In D.J. Klein and D. Brandas, editors, Advances in Quantum Chemistry: Chemical Graph Theory: Wherefrom, wherefor and whereto?, Elsevier-Academic Press, 1-91, 2007. [4] F. Buckley and F. Harary. Distance in graphs. Addison Wesley Publishing Company, Ad- vanced Book Programme, Redwood City, CA, 1990. [5] F. Harary and Melter. On the metric dimension of a graph, Ars Combin., 2, 191-195, 1976. [6] F. Harary. Graph Theory, Addison Wesley Publ. Comp., Reading, Massachusetts, 1969. [7] J. Fiksel. Dynamic evolution of societal networks, J. Math. Sociology, 7, 27-46, 1980. [8] H.J. Ryser.(0,1)-Matrices, Carus Mathematical Monographs No.14, New York, 1968. [9] K.A. Germina, Set Valuations of Graphs and Their Applications, Technical Report, grant- in-aid project No.SR/S4/277/06, Department of Science & Technology (DST),Govt. of India, April 2009. [10] D.H. Rouvrey. Predicting chemistry from topology. Scientific American, 254, 9, 40-47, 1986. [11] N. Trinajstic, Chemical graph theory, Boca Raton, 1983. REFERENCES 764 [12] Wai-Kai Chen. The metric structure of graphs: Theory and Applications. London Math. Soc., 123, 197-221, 1987.