EULERIAN AND HAMILTONIAN PROPERTIES OF GALLAI AND ANTI-GALLAI MIDDLE GRAPHS

EULERIAN AND HAMILTONIAN PROPERTIES OF GALLAI AND ANTI-GALLAI MIDDLE GRAPHS

S. Goyal, D. Jain

[PDF]

Abstract

The Gallai middle graph I_M(G) of a graph G = (V;E) is the graph whose vertex set is V [ E and two edges ei; ej 2 E are adjacent in I_M(G), if they are adjacent edges of G and do not lie on a same triangle in G, or if ei = uv 2 E then ei is adjacent to u and v in I_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 2 E are adjacent in  M(G) if they are adjacent in G and lie on a same triangle in G, or if ei = uv 2 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.

Keywords

Euler graph, Hamiltonian graph, Gallai middle graph, anti-Gallai middle graph.