Some algebraic properties of the subdivision graph of a graph

Document Type : Original paper

Author

Department of Mathematics, Faculty of Basic Sciences, Lorestan University, Khorramabad, Iran

Abstract

Let G=(V,E) be a connected graph with the vertex-set V and  the edge-set E.    The subdivision graph S(G) of the graph G is obtained from G by adding a vertex in the middle of every edge of G.  In this paper, we investigate some properties of the graphs  S(G) and L(S(G)), where L(S(G)) is the line graph of S(G). We will see that S(G) and  L(S(G))  inherit some  properties of G.    For instance, we show that if G≇Cn, then Aut(G)≅Aut(L(S(G))) (as abstract groups), where Cn is the cycle of order n.

Keywords

Main Subjects

References

[1] N. Biggs, Algebraic Graph Theory, 2nd edn. Cambridge University Press, Cambridge, 1993.
[2] J.A. Bondy and U.S.R. Murty, Graph Theory, Springer, Berlin, 2008.
[3] G. Chartrand, A.M. Hobbs, H.A. Jung, S.F. Kapoor, and C.St.J.A. Nash-Williams, The square of a block is Hamiltonian connected, J. Combin. Theory, Ser. B 16 (1974), no. 3, 290–292.  https://doi.org/10.1016/0095-8956(74)90075-6
[4] H. Fleischner, In the square of graphs, hamiltonicity and pancyclicity, hamiltonian connectedness and panconnectedness are equivalent concepts, Monatsh. Math. 82 (1976), 125–149.  https://doi.org/10.1007/BF01305995
[5] C. Godsil and G.F. Royle, Algebraic Graph Theory, vol. 207, Springer Science & Business Media, 2001.
[6] F. Harary, Graph Theory, CRC Press, 1969.
[7] F. Harary and C.St.J.A. Nash-Williams, On Eulerian and Hamiltonian graphs and line graphs, Canad. Math. Bull. 8 (1965), no. 6, 701–709.  https://doi.org/10.4153/CMB-1965-051-3
[8] A. Heidari and S.M. Mirafzal, Johnson graphs are panconnected, Proc. Math. Sci. 129 (2019), Article number: 79.  https://doi.org/10.1007/s12044-019-0527-3
[9] S.M. Mirafzal, Some other algebraic properties of folded hypercubes, Ars Combin. 124 (2016), 153–159.
[10] S.M. Mirafzal, A new class of integral graphs constructed from the hypercube, Linear Algebra Appl. 558 (2018), 186–194. https://doi.org/10.1016/j.laa.2018.08.027
[11] S.M. Mirafzal, The automorphism group of the bipartite Kneser graph, Proc. Math. Sci. 129 (2019), Article number 34. https://doi.org/10.1007/s12044-019-0477-9
[12] S.M. Mirafzal, On the automorphism groups of connected bipartite irreducible graphs, Proc. Math. Sci. 130 (2020), Article number 57. https://doi.org/10.1007/s12044-020-00589-1
[13] S.M. Mirafzal, Cayley properties of the line graphs induced by consecutive layers of the hypercube, Bull. Malays. Math. Sci. Soc. 44 (2021),  1309–1326. https://doi.org/10.1007/s40840-020-01009-3
[14] S.M. Mirafzal, A note on the automorphism groups of Johnson graphs, Ars Combin. 154 (2021), 245–255.
[15] S.M. Mirafzal, Some remarks on the square graph of the hypercube, Ars Math. Contemp. 23 (2023), no. 2, #P2.06 https://doi.org/10.26493/1855-3974.2621.26f
[16] S.M. Mirafzal and A. Zafari, Some algebraic properties of bipartite Kneser graphs, Ars Combin. 153 (2020), 3–12.
[17] S.M. Mirafzal and M. Ziaee, A note on the automorphism group of the Hamming graph, Trans. Comb. 10 (2021), no. 2, 129–136.  https://doi.org/10.22108/toc.2021.127225.1817
[18] G. Sabidussi, Vertex-transitive graphs, Monatsh. Math. 68 (1964), 426–438.
Communications in Combinatorics and Optimization
Volume 9, Issue 2
June 2024
Pages 297-307

Files

Share

How to cite

Statistics