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 \ncong C_n$, then $Aut(G) \cong Aut(L(S(G)))$ (as abstract groups), where $C_n$ 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