Correo Electrónico
DNINFOA - SIA
Bibliotecas
Convocatorias
Identidad U.N.
Publicado
Independence numbers of some double vertex graphs and pair graphs
Números de independencia de algunas gráficas de vértice doble y gráficas de pares
DOI:
https://doi.org/10.15446/recolma.v58n1.117433Palabras clave:
Double vertex graphs, pair graphs, independence number (en)Grafos de vértice doble, grafos de pares, número de independencia (es)
Descargas
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.
Las propiedades combinatorias del grafo de vértice doble de un grafo han sido ampliamente estudiadas desde los años 90. Sin embargo, sólo se conocen pocos resultados sobre el número de independencia de dichos grafos. En este artículo obtenemos los números de independencia de los grafos de vértice doble de las los grafos abanico y rueda. También obtenemos los números de independencia de los grafos de pares, que es un tipo de generalización de los grafos de vértice doble, de algunas familias de grafos.
Referencias
[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 Francisco, CA, 1989), SIAM, Philadelphia, PA, 1991, pp. 472-485.
[3] Y. Alavi, D. R. Lick, and J. Liu, Survey of double vertex graphs, Graphs Combin. 18 (2002), no. 4, 709-715.
[4] H. de Alba, W. Carballosa, D. Duarte, and L. M. Rivera, Cohenmacaulayness of triangular graphs, Bull. Math. Soc. Sci. Math. Roumanie 60 (108) (2017), no. 2, 103-112.
[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 (2020), no. 3, 387-403.
[6] A. Alzaga, R. Iglesias, and R. Pignol, Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements, J. Combin. Theory Ser. B 100 (2010), no. 6, 671-682.
[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.
[8] A. R. Barghi and I. Ponomarenko, Non-isomorphic graphs with cospectral symmetric powers, Electron. J. Combin. 16 (2009), no. 1, Research Paper 120, 14.
[9] C. Beaula, O. Venugopal, and N. Padmapriya, Graph distance of vertices in double vertex graphs, Int J. Pure Appl. Math. 118 (2018), no. 23, 343-351.
[10] W. Carballosa, R. Fabila-Monroy, J. Lea˜nos, and L. M. Rivera, Regularity and planarity of token graphs, Discuss. Math. Graph Theory 37 (2017), no. 3, 573-586.
[11] G. Chartrand, D. Erwin, M. Raines, and P. Zhang, Orientation distance graphs, J. Graph Theory 36 (2001), no. 4, 230-241.
[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, 365-380.
[14] C. Fischbacher and S. Stolz, Droplet states in quantum xxz spin systems on general graphs, J. Math. Phys. 59 (2018), no. 5, 051901.
[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 Appl. Math. 247 (2018), 327-340.
[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 Press, New York (1972), 85-103.
[19] J. Leaños and A. L. Trujillo-Negrete, The connectivity of token graphs, submitted, Graphs Combin. 32 (2018), no. 4, 777-790.
[20] L. M. Rivera and A. L. Trujillo-Negrete, Hamiltonicity of token graphs of fan graphs, Art Discr. Appl. Math 1 (2018), #P07, 5.
[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.
