Metric dimension and zero forcing number of two families of line graphs

Linda Eroh; Cong X. Kang; Eunjeong Yi

Mathematica Bohemica (2014)

  • Volume: 139, Issue: 3, page 467-483
  • ISSN: 0862-7959

Abstract

top
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 ) ≤ 2 Z ( L ( G ) ) for a simple and connected graph G . Further, we show that Z ( G ) ≤ 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.

How to cite

top

Eroh, Linda, Kang, Cong X., and Yi, Eunjeong. "Metric dimension and zero forcing number of two families of line graphs." Mathematica Bohemica 139.3 (2014): 467-483. <http://eudml.org/doc/262049>.

@article{Eroh2014,
abstract = {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.},
author = {Eroh, Linda, Kang, Cong X., Yi, Eunjeong},
journal = {Mathematica Bohemica},
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},
language = {eng},
number = {3},
pages = {467-483},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Metric dimension and zero forcing number of two families of line graphs},
url = {http://eudml.org/doc/262049},
volume = {139},
year = {2014},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 139
IS - 3
SP - 467
EP - 483
AB - 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.
LA - eng
KW - 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
UR - http://eudml.org/doc/262049
ER -

References

top
  1. Bailey, R. F., Cameron, P. J., 10.1112/blms/bdq096, Bull. Lond. Math. Soc. 43 209-242 (2011). (2011) Zbl1220.05030MR2781204DOI10.1112/blms/bdq096
  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). (2008) MR2388646
  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). (2010) MR2645093
  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). (2008) Zbl1144.05314MR2444348
  5. Buczkowski, P. S., Chartrand, G., Poisson, C., Zhang, P., 10.1023/A:1025745406160, Period. Math. Hung. 46 9-15 (2003). (2003) Zbl1026.05033MR1975342DOI10.1023/A:1025745406160
  6. Cáceres, J., Hernando, C., Mora, M., Pelayo, I. M., Puertas, M. L., Seara, C., Wood, D. R., 10.1137/050641867, SIAM J. Discrete Math. 21 423-441 (2007). (2007) Zbl1139.05314MR2318676DOI10.1137/050641867
  7. Chartrand, G., Eroh, L., Johnson, M. A., Oellermann, O. R., 10.1016/S0166-218X(00)00198-0, Discrete Appl. Math. 105 99-113 (2000). (2000) Zbl0958.05042MR1780464DOI10.1016/S0166-218X(00)00198-0
  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). (2003) Zbl1039.05029MR2049102
  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). (2012) Zbl1251.05149MR2919232
  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). (2012) Zbl1241.05076MR2917414
  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). (2007) Zbl1122.05057MR2350678
  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., 10.1016/j.dam.2012.10.018, Discrete Appl. Math. 161 802-805 (2013). (2013) Zbl1262.05069MR3027968DOI10.1016/j.dam.2012.10.018
  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). (1979) Zbl0411.68039MR0519066
  17. Harary, F., Melter, R. A., On the metric dimension of a graph, Ars Comb. 2 191-195 (1976). (1976) Zbl0349.05118MR0457289
  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). (2010) Zbl1219.05051MR2595490
  19. Hogben, L., Huynh, M., Kingsley, N., Meyer, S., Walker, S., Young, M., 10.1016/j.dam.2012.04.003, Discrete Appl. Math. 160 1994-2005 (2012). (2012) Zbl1246.05056MR2927529DOI10.1016/j.dam.2012.04.003
  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). (2010) Zbl1194.05033MR2682501
  21. Khuller, S., Raghavachari, B., Rosenfeld, A., 10.1016/0166-218X(95)00106-2, Discrete Appl. Math. 70 217-229 (1996). (1996) Zbl0865.68090MR1410574DOI10.1016/0166-218X(95)00106-2
  22. Llibre, J., Todd, M., 10.1080/10236190500331230, J. Difference Equ. Appl. 11 1049-1069 (2005). (2005) Zbl1162.37303MR2179503DOI10.1080/10236190500331230
  23. Massey, W. S., Algebraic Topology: An Introduction. Graduate Texts in Mathematics 56, Springer, New York (1981). (1981) MR0448331
  24. Poisson, C., Zhang, P., The metric dimension of unicyclic graphs, J. Comb. Math. Comb. Comput. 40 17-32 (2002). (2002) Zbl0990.05040MR1887964
  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). (2012) Zbl1241.05086MR2917419
  26. Sebö, A., Tannier, E., 10.1287/moor.1030.0070, Math. Oper. Res. 29 383-393 (2004). (2004) Zbl1082.05032MR2065985DOI10.1287/moor.1030.0070
  27. Shanmukha, B., Sooryanarayana, B., Harinath, K. S., Metric dimension of wheels, Far East J. Appl. Math. 8 217-229 (2002). (2002) Zbl1032.05044MR1944130
  28. Slater, P. J., Dominating and reference sets in a graph, J. Math. Phys. Sci. 22 445-455 (1988). (1988) Zbl0656.05057MR0966610
  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). (1975) Zbl0316.05102MR0422062
  30. Whitney, H., 10.2307/2371086, Am. J. Math. 54 150-168 (1932). (1932) Zbl0003.32804MR1506881DOI10.2307/2371086

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.