Volume 15, Issue 2 (10-2020)                   IJMSI 2020, 15(2): 77-99 | Back to browse issues page

XML Print

Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

Kumar A, Mohankumar E. Uniform Number of a Graph. IJMSI. 2020; 15 (2) :77-99
URL: http://ijmsi.ir/article-1-1144-en.html
We introduce the notion of uniform number of a graph. The  uniform number of a connected graph $G$ is the least cardinality of a nonempty subset $M$ of the vertex set of $G$ for which the function $f_M: M^crightarrow mathcal{P}(X) - {emptyset}$ defined as $f_M(x) = {D(x, y): y in M}$ is a
constant function, where $D(x, y)$ is the detour distance between $x$ and $y$ in $G$ and $mathcal{P}(X)$
is power set of $X = {D(x_i, x_j): x_i neq x_j}.$ We obtain some basic results and compute the newly
introduced graph parameter for some specific graphs.
Type of Study: Research paper | Subject: General

1. K. Abhishek and A. Ganesan, Detour Distance Pattern Of A Graph, International Journal of Pure and Applied Mathematics Volume 87 No. 5 2013, 719-728. doi: http://dx.doi.org/10.12732/ijpam.v87i5.5. [DOI:10.12732/ijpam.v87i5.5]
2. G. Chartrand, L. Eroh, M. A. Johnson and O. R. Oellermann, Resolvability in graphs and the metric dimension of a graph,Discrete Applied Mathematics, 105(13), (2000), 99-113. [DOI:10.1016/S0166-218X(00)00198-0]
3. G. Chartrand, Linda Eroha, Mark A. Johnsonb and Ortrud R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Applied Mathematics, Volume 105, Issues 13, 15 October 2000, Pages 99-113. [DOI:10.1016/S0166-218X(00)00198-0]
4. G. Chartrand and P. Zhang, Distance in graphs - Taking the long view, AKCE J. GraphsCombin. 1 (2004) 1-13.
5. F. Buckley, F. Harary, Distance in graphs, Addison-Wesley Pub. Co., 1990.
6. Garey, M.R., Johnson, D.S, Computers and Intractability: A guide to the Theory of NP-Completeness, W. H. Freeman, 1st ed. (1979).
7. G. Chartrand, Garry L. Johns and Songlin Tian, Detour Distance in Graphs, Annals of Discrete Mathematics, Volume 55, 1993, Pages 127136. doi:10.1016/S0167-5060(08)70381-9. [DOI:10.1016/S0167-5060(08)70381-9]
8. T. H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stein, Introduction To Algorithms, MIT Press , 2001.
9. A. Ghosh, S. Boyd and A. Saberi, Minimizing Effective Resistance of a Graph, Proc. 17th Internat. Sympos. Math. Th. Network and Systems, Kyoto, Japan, July 24-28, 2006. pp. 1185-1196.
10. F. Harary, R.A. Melter, On the metric dimension of a graph, Ars Combin., 2 (1976), pp.191-195.
11. Ho, Hamiltonian-laceability of star graphs, Networks, 36 (4) (2000), pp. 225-232. https://doi.org/10.1002/1097-0037(200012)36:4<225::AID-NET3>3.0.CO;2-G [DOI:10.1002/1097-0037(200012)36:43.0.CO;2-G]
12. S. Y. Hsieh and C. N. Kuo, Hamiltonian-connectivity and strongly Hamiltonianlaceability of folded hypercubes, Computers & Mathematics with Applications, 53(7)(2007), pp. 1040-1044. [DOI:10.1016/j.camwa.2006.10.033]
13. O. Michael, J. P. Albertson, and Michael E. Young, Disjoint homometric sets in graphs, Ars Mathematica Contemporanea , 4(1), 14, 2011. [DOI:10.26493/1855-3974.174.027]
14. O. Ore, Theory of Graphs, A.M.S. Colloquium Publications, No. 38, American Math. Soc., Providence, R.I., 1962. [DOI:10.1090/coll/038]
15. O.Ore, Hamiltonian connected graphs, J. Math Pures Appl., 42(1963), 21-27. 18. Joseph A. Gallian, A Dynamic Survey of Graph Labeling, The Electronic Journal of Combinatorics, 18.(2015) #DS6.
16. Tseng, I.L., Chen, H.W., Lee, C.I, Obstacle-aware longest-path routing with parallel milp solvers, Proceedings of WCECS-ICCS, Vol. 2. pp. 827831 (2010).
17. D. Portugal, R. Rocha, Msp algorithm: Multi-robot patrolling based on territory allocation using balanced graph partitioning, Proceedings of SAC 2010. pp. 12711276 (2010). [DOI:10.1145/1774088.1774360]
18. K. Schmidt, E. G. Schmidt, A longest-path problem for evaluating the worst-case packet delay of switched ethernet, Proceedings of SIES2010. pp. 205208 (2010). [DOI:10.1109/SIES.2010.5551398]
19. P. J. Slater, Leaves of trees, Proc. 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla, 1975), Congressus Numerantium, no. 14, Utilitas Math., Winnipeg, Manitoba, 1975, pp. 549559.
20. P. J. Slater and Richard A Gibbs, Distinct distance set in a graph, Discrete Mathematics, 93(1991), 155-165. [DOI:10.1016/0012-365X(91)90251-V]
21. G. Simmons, Almost all n-dimensional rectangular lattices are Hamilton laceable, Congressus Numerantium, 21 (1978), pp. 103-108. 20. S.Y. Hsieh, G.H. Chen, C.W.
22. W.Y., Wong, T.P. Lau, I. King, Information retrieval in p2p networks using genetic algorithm, Proceedings of the 14th Int. World Wide Web Conference, Special interest tracks and posters. pp. 922923 (2005). [DOI:10.1145/1062745.1062799]

Add your comments about this article : Your username or Email:

© 2020 All Rights Reserved | Iranian Journal of Mathematical Sciences and Informatics

Designed & Developed by : Yektaweb