×

On the distance pattern distinguishing number of a graph. (English) Zbl 1442.05051

Summary: Let \(G = (V, E)\) be a connected simple graph and let \(M\) be a nonempty subset of \(V\). The \(M\)-distance pattern of a vertex \(u\) in \(G\) is the set of all distances from \(u\) to the vertices in \(M\). If the distance patterns of all vertices in \(V\) are distinct, then the set \(M\) is a distance pattern distinguishing set of \(G\). A graph \(G\) with a distance pattern distinguishing set is called a distance pattern distinguishing graph. Minimum number of vertices in a distance pattern distinguishing set is called distance pattern distinguishing number of a graph. This paper initiates a study on the problem of finding distance pattern distinguishing number of a graph and gives bounds for distance pattern distinguishing number. Further, this paper provides an algorithm to determine whether a graph is a distance pattern distinguishing graph or not and hence to determine the distance pattern distinguishing number of that graph.

MSC:

05C12 Distance in graphs
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Slater, P. J., Leaves of trees, Congressus Numerantium, 14, 549-559 (1975)
[2] Germina, K. A.; Joseph, A., Some general results on distance pattern distinguishing graphs, International Journal of Contemporary Mathematical Sciences, 6, 15, 713-720 (2011) · Zbl 1227.05139
[3] Germina, K. A., Set-valuations of graphs and applications, Project Completion Report, DST Grant-In-Aid Project No.SR/S4/277/05 (2011), The Department of Science & Technology (DST), Government of India
[4] Chartrand, G.; Eroh, L.; Johnson, M. A.; Oellermann, O. R., Resolvability in graphs and the metric dimension of a graph, Discrete Applied Mathematics, 105, 1-3, 99-113 (2000) · Zbl 0958.05042
[5] Khuller, S.; Raghavachari, B.; Rosenfeld, A., Landmarks in graphs, Discrete Applied Mathematics, 70, 3, 217-229 (1996) · Zbl 0865.68090
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.