Eulerian and Hamiltonian properties of Gallai and anti-Gallai middle graphs

Abstract

The Gallai middle graph ΓM(G) of a graph G = (V, E) is the graph whose vertex set is V ∪ E and two edges ei, ej ∈ E are adjacent in ΓM(G), if they are adjacent edges of G and do not lie on a same triangle in G, or if ei = uv ∈ E then ei is adjacent to u and v in ΓM(G). The anti-Gallai middle graph ∆M(G) of a graph G = (V, E) is the graph whose vertex set is V ∪ E and two edges ei, ej ∈ E are adjacent in ∆M(G) if they are adjacent in G and lie on a same triangle in G, or if ei = uv ∈ E then ei is adjacent to u and v in ∆M(G). In this paper, we investigate Eulerian and Hamiltonian properties of Gallai and anti-Gallai middle graphs.