Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
resolving set; metric dimension; zero forcing set; zero forcing number; line graph; wheel graph; bouquet of circles
resolving set; metric dimension; zero forcing set; zero forcing number; line graph; wheel graph; bouquet of circles
Summary:
Zero forcing number has recently become an interesting graph parameter studied in its own right since its introduction by the “AIM Minimum Rank–Special Graphs Work Group”, whereas metric dimension is a well-known graph parameter. We investigate the metric dimension and the zero forcing number of some line graphs by first determining the metric dimension and the zero forcing number of the line graphs of wheel graphs and the bouquet of circles. We prove that $Z(G) \le 2Z(L(G))$ for a simple and connected graph $G$. Further, we show that $Z(G) \le Z(L(G))$ when $G$ is a tree or when $G$ contains a Hamiltonian path and has a certain number of edges. We compare the metric dimension with the zero forcing number of a line graph by demonstrating a couple of inequalities between the two parameters. We end by stating some open problems.
References:
[1] Bailey, R. F., Cameron, P. J.: Base size, metric dimension and other invariants of groups and graphs. Bull. Lond. Math. Soc. 43 209-242 (2011). DOI 10.1112/blms/bdq096 | MR 2781204 | Zbl 1220.05030
[2] F. Barioli, W. Barrett, S. Butler, S. M. Ciobă, D. Cvetković, S. M. Fallat, C. Godsil, W. Haemers, L. Hogben, R. Mikkelson, S. Narayan, O. Pryporova, I. Sciriha, W. So, D. Stevanović, H. van der Holst, K. Vander Meulen, A. W. Wehe (AIM Minimum Rank-- Special Graphs Work Group): Zero forcing sets and the minimum rank of graphs. Linear Algebra Appl. 428 1628-1648 (2008). MR 2388646
[3] Barioli, F., Barrett, W., Fallat, S. M., Hall, H. T., Hogben, L., Shader, B., Driessche, P. van den, Holst, H. van der: Zero forcing parameters and minimum rank problems. Linear Algebra Appl. 433 401-411 (2010). MR 2645093
[4] Berman, A., Friedland, S., Hogben, L., Rothblum, U. G., Shader, B.: An upper bound for the minimum rank of a graph. Linear Algebra Appl. 429 1629-1638 (2008). MR 2444348 | Zbl 1144.05314
[5] Buczkowski, P. S., Chartrand, G., Poisson, C., Zhang, P.: On $k$-dimensional graphs and their bases. Period. Math. Hung. 46 9-15 (2003). DOI 10.1023/A:1025745406160 | MR 1975342 | Zbl 1026.05033
[6] Cáceres, J., Hernando, C., Mora, M., Pelayo, I. M., Puertas, M. L., Seara, C., Wood, D. R.: On the metric dimension of Cartesian products of graphs. SIAM J. Discrete Math. 21 423-441 (2007). DOI 10.1137/050641867 | MR 2318676 | Zbl 1139.05314
[7] Chartrand, G., Eroh, L., Johnson, M. A., Oellermann, O. R.: Resolvability in graphs and the metric dimension of a graph. Discrete Appl. Math. 105 99-113 (2000). DOI 10.1016/S0166-218X(00)00198-0 | MR 1780464 | Zbl 0958.05042
[8] Chartrand, G., Zhang, P.: The theory and applications of resolvability in graphs: a survey. Proceedings of the Thirty-{F}ourth Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congr. Numerantium 160 47-68 (2003). MR 2049102 | Zbl 1039.05029
[9] Chilakamarri, K. B., Dean, N., Kang, C. X., Yi, E.: Iteration index of a zero forcing set in a graph. Bull. Inst. Comb. Appl. 64 57-72 (2012). MR 2919232 | Zbl 1251.05149
[10] Edholm, C. J., Hogben, L., Huynh, M., LaGrange, J., Row, D. D.: Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph. Linear Algebra Appl. 436 4352-4372 (2012). MR 2917414 | Zbl 1241.05076
[11] Eroh, L., Kang, C. X., Yi, E.: A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs. arXiv:1408.5943.
[12] Eroh, L., Kang, C. X., Yi, E.: On zero forcing number of graphs and their complements. arXiv:1402.1962.
[13] Fallat, S. M., Hogben, L.: The minimum rank of symmetric matrices described by a graph: a survey. Linear Algebra Appl. 426 558-582 (2007). MR 2350678 | Zbl 1122.05057
[14] Fallat, S. M., Hogben, L.: Variants on the minimum rank problem: a survey II. arXiv: 1102.5142v1.
[15] Feng, M., Xu, M., Wang, K.: On the metric dimension of line graphs. Discrete Appl. Math. 161 802-805 (2013). DOI 10.1016/j.dam.2012.10.018 | MR 3027968 | Zbl 1262.05069
[16] Garey, M. R., Johnson, D. S.: Computers and Intractability. A Guide to the Theory of NP-completeness. A Series of Books in the Mathematical Sciences Freeman, San Francisco (1979). MR 0519066 | Zbl 0411.68039
[17] Harary, F., Melter, R. A.: On the metric dimension of a graph. Ars Comb. 2 191-195 (1976). MR 0457289 | Zbl 0349.05118
[18] Hernando, C., Mora, M., Pelayo, I. M., Seara, C., Wood, D. R.: Extremal graph theory for metric dimension and diameter. Electron. J. Comb. (electronic only) 17 Research paper R30, 28 pages (2010). MR 2595490 | Zbl 1219.05051
[19] Hogben, L., Huynh, M., Kingsley, N., Meyer, S., Walker, S., Young, M.: Propagation time for zero forcing on a graph. Discrete Appl. Math. 160 1994-2005 (2012). DOI 10.1016/j.dam.2012.04.003 | MR 2927529 | Zbl 1246.05056
[20] Iswadi, H., Baskoro, E. T., Salman, A. N. M., Simanjuntak, R.: The metric dimension of amalgamation of cycles. Far East J. Math. Sci. (FJMS) 41 19-31 (2010). MR 2682501 | Zbl 1194.05033
[21] Khuller, S., Raghavachari, B., Rosenfeld, A.: Landmarks in graphs. Discrete Appl. Math. 70 217-229 (1996). DOI 10.1016/0166-218X(95)00106-2 | MR 1410574 | Zbl 0865.68090
[22] Llibre, J., Todd, M.: Periods, Lefschetz numbers and entropy for a class of maps on a bouquet of circles. J. Difference Equ. Appl. 11 1049-1069 (2005). DOI 10.1080/10236190500331230 | MR 2179503 | Zbl 1162.37303
[23] Massey, W. S.: Algebraic Topology: An Introduction. Graduate Texts in Mathematics 56. Springer, New York (1981). MR 0448331
[24] Poisson, C., Zhang, P.: The metric dimension of unicyclic graphs. J. Comb. Math. Comb. Comput. 40 17-32 (2002). MR 1887964 | Zbl 0990.05040
[25] Row, D. D.: A technique for computing the zero forcing number of a graph with a cut-vertex. Linear Algebra Appl. 436 4423-4432 (2012). MR 2917419 | Zbl 1241.05086
[26] Sebö, A., Tannier, E.: On metric generators of graphs. Math. Oper. Res. 29 383-393 (2004). DOI 10.1287/moor.1030.0070 | MR 2065985 | Zbl 1082.05032
[27] Shanmukha, B., Sooryanarayana, B., Harinath, K. S.: Metric dimension of wheels. Far East J. Appl. Math. 8 217-229 (2002). MR 1944130 | Zbl 1032.05044
[28] Slater, P. J.: Dominating and reference sets in a graph. J. Math. Phys. Sci. 22 445-455 (1988). MR 0966610 | Zbl 0656.05057
[29] Slater, P. J.: Leaves of trees. Proc. 6th Southeast. Conf. Comb., Graph Theor., Comput. F. Hoffman et al. Florida Atlantic Univ., Boca Raton, Congr. Numerantium 14 549-559 (1975). MR 0422062 | Zbl 0316.05102
[30] Whitney, H.: Congruent graphs and the connectivity of graphs. Am. J. Math. 54 150-168 (1932). DOI 10.2307/2371086 | MR 1506881 | Zbl 0003.32804
Search
Partner of
