Geodesic
Metric dimension and zero forcing number of two families of line graphs
Mathematica Bohemica, Tome 139 (2014) no. 3, pp. 467-483

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
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.
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.
DOI : 10.21136/MB.2014.143937
Classification : 05C05, 05C12, 05C38, 05C50
Keywords: resolving set; metric dimension; zero forcing set; zero forcing number; line graph; wheel graph; bouquet of circles 
Eroh, Linda; Kang, Cong X.; Yi, Eunjeong. Metric dimension and zero forcing number of two families of line graphs. Mathematica Bohemica, Tome 139 (2014) no. 3, pp. 467-483. doi: 10.21136/MB.2014.143937
@article{10_21136_MB_2014_143937,
     author = {Eroh, Linda and Kang, Cong X. and Yi, Eunjeong},
     title = {Metric dimension and zero forcing number of two families of line graphs},
     journal = {Mathematica Bohemica},
     pages = {467--483},
     year = {2014},
     volume = {139},
     number = {3},
     doi = {10.21136/MB.2014.143937},
     mrnumber = {3269369},
     zbl = {06391466},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2014.143937/}
}
TY  - JOUR
AU  - Eroh, Linda
AU  - Kang, Cong X.
AU  - Yi, Eunjeong
TI  - Metric dimension and zero forcing number of two families of line graphs
JO  - Mathematica Bohemica
PY  - 2014
SP  - 467
EP  - 483
VL  - 139
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2014.143937/
DO  - 10.21136/MB.2014.143937
LA  - en
ID  - 10_21136_MB_2014_143937
ER  - 
%0 Journal Article
%A Eroh, Linda
%A Kang, Cong X.
%A Yi, Eunjeong
%T Metric dimension and zero forcing number of two families of line graphs
%J Mathematica Bohemica
%D 2014
%P 467-483
%V 139
%N 3
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2014.143937/
%R 10.21136/MB.2014.143937
%G en
%F 10_21136_MB_2014_143937

[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 | MR | Zbl

[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

[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

[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 | Zbl

[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 | MR | Zbl

[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 | MR | Zbl

[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 | MR | Zbl

[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 | Zbl

[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 | Zbl

[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 | Zbl

[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 | Zbl

[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 | MR | Zbl

[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 | Zbl

[17] Harary, F., Melter, R. A.: On the metric dimension of a graph. Ars Comb. 2 191-195 (1976). | MR | Zbl

[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 | Zbl

[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 | MR | Zbl

[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 | Zbl

[21] Khuller, S., Raghavachari, B., Rosenfeld, A.: Landmarks in graphs. Discrete Appl. Math. 70 217-229 (1996). | DOI | MR | Zbl

[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 | MR | Zbl

[23] Massey, W. S.: Algebraic Topology: An Introduction. Graduate Texts in Mathematics 56. Springer, New York (1981). | MR

[24] Poisson, C., Zhang, P.: The metric dimension of unicyclic graphs. J. Comb. Math. Comb. Comput. 40 17-32 (2002). | MR | Zbl

[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 | Zbl

[26] Sebö, A., Tannier, E.: On metric generators of graphs. Math. Oper. Res. 29 383-393 (2004). | DOI | MR | Zbl

[27] Shanmukha, B., Sooryanarayana, B., Harinath, K. S.: Metric dimension of wheels. Far East J. Appl. Math. 8 217-229 (2002). | MR | Zbl

[28] Slater, P. J.: Dominating and reference sets in a graph. J. Math. Phys. Sci. 22 445-455 (1988). | MR | Zbl

[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 | Zbl

[30] Whitney, H.: Congruent graphs and the connectivity of graphs. Am. J. Math. 54 150-168 (1932). | DOI | MR | Zbl

Cité par Sources :