Independence numbers of some double vertex graphs and pair graphs

• Autores: Paloma Jimenez Sepulveda, Luis Manuel Rivera
• Localización: Revista Colombiana de Matemáticas, ISSN-e 0034-7426, Vol. 58, Nº. 1, 2024, págs. 47-65
• Idioma: varios idiomas
• Títulos paralelos:
  • Números de independencia de algunas gráficas de vértice doble y gráficas de pares
• Enlaces
  • Texto completo
• Resumen

  • The combinatorial properties of the double vertex graph of a graph have been widely studied since the 90’s. However only very few results are know about the independence number of such graphs. In this paper we obtain the independence numbers of the double vertex graphs of fan graphs and wheel graphs. Also we obtain the independence numbers of the pair graphs, that is a kind of generalization of the double vertex graphs, of some families of graphs.

• Referencias bibliográficas
  • [1] Y. Alavi, M. Behzad, P. Erdös, and D. R. Lick, Double vertex graphs, J. Combin. Inform. System Sci. 16 (1991), no. 1, 37-50.
  • [2] Y. Alavi, M. Behzad, and J. E. Simpson, Planarity of double vertex graphs, Graph theory, combinatorics, algorithms, and applications (San...
  • [3] Y. Alavi, D. R. Lick, and J. Liu, Survey of double vertex graphs, Graphs Combin. 18 (2002), no. 4, 709-715. DOI: https://doi.org/10.1007/s003730200055
  • [4] H. de Alba, W. Carballosa, D. Duarte, and L. M. Rivera, Cohenmacaulayness of triangular graphs, Bull. Math. Soc. Sci. Math. Roumanie 60...
  • [5] H. de Alba, W. Carballosa, J. Leaños, and L. M. Rivera, Independence and matching numbers of some token graphs, Australas J. Combin. 76...
  • [6] A. Alzaga, R. Iglesias, and R. Pignol, Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements, J. Combin. Theory...
  • [7] K. Audenaert, C. Godsil, G. Royle, and T. Rudolph, Symmetric squares of graphs, J. Combin. Theory Ser. B 97 (2007), no. 1, 74-90. DOI:...
  • [8] A. R. Barghi and I. Ponomarenko, Non-isomorphic graphs with cospectral symmetric powers, Electron. J. Combin. 16 (2009), no. 1, Research...
  • [9] C. Beaula, O. Venugopal, and N. Padmapriya, Graph distance of vertices in double vertex graphs, Int J. Pure Appl. Math. 118 (2018), no....
  • [10] W. Carballosa, R. Fabila-Monroy, J. Lea˜nos, and L. M. Rivera, Regularity and planarity of token graphs, Discuss. Math. Graph Theory...
  • [11] G. Chartrand, D. Erwin, M. Raines, and P. Zhang, Orientation distance graphs, J. Graph Theory 36 (2001), no. 4, 230-241. DOI: https://doi.org/10.1002/1097-0118(200104)36:4<230::AID-JGT1008>3.3.CO;2-R
  • [12] J. Deepalakshmi and G. Marimuthu, Characterization of token graphs, J. Eng. Technol. 6 (2017), no. 4, 310-317.
  • [13] R. Fabila-Monroy, D. Flores-Peñaloza, C. Huemer, F. Hurtado, J. Urrutia, and D. R.Wood, Token graphs, Graphs Combin. 28 (2012), no. 3,...
  • [14] C. Fischbacher and S. Stolz, Droplet states in quantum xxz spin systems on general graphs, J. Math. Phys. 59 (2018), no. 5, 051901. DOI:...
  • [15] J. M. Gómez Soto, J. Leaños, L. M. Ríos Castro, and L. M. Rivera, The packing number of the double vertex graph of the path graph, Discrete...
  • [16] J. Jacob, W. Goddard, and R. Laskar, Double vertex graphs and complete double vertex graphs, Congr. Numer. 188 (2007), 161-174.
  • [17] G. L. Johns, Generalized distance in graphs, Ph.d. dissertation, Western Michigan University, 1988.
  • [18] R. Karp, Reducibility among combinatorial problems, in: Complexity of computer computations, (E. Miller and J. W. Thatcher, eds.) Plenum...
  • [19] J. Leaños and A. L. Trujillo-Negrete, The connectivity of token graphs, submitted, Graphs Combin. 32 (2018), no. 4, 777-790. DOI: https://doi.org/10.1007/s00373-018-1913-9
  • [20] L. M. Rivera and A. L. Trujillo-Negrete, Hamiltonicity of token graphs of fan graphs, Art Discr. Appl. Math 1 (2018), #P07, 5. DOI: https://doi.org/10.26493/2590-9770.1244.720
  • [21] R. Rudolph, Constructing physically intuitive graph invariants, arXiv:quant-ph/0206068 (2002), 1-4.
  • [22] N. J. A. Sloane, The on-line encyclopedia of integer sequences, 2017. DOI: https://doi.org/10.1090/noti1734