Several Special Gallai Graphs

Let G be a graph with E(G)? 0.The Gallai graph Gal(G)of a graph G has the edges of G as its vertices,and two distinct vertices e and f of Gal(G)are adjacent in Gal(G)if the edges e and f of G are adjacent in G but do not span a triangle in G.Clearly,the Gallai graph Gal(G)is a spanning subgraph of the well-known line graph L(G)of G.In this paper,we characterize those graphs whose Gallai graphs are cycles and complete k-partite graphs,respectively.We proved two conclusions:The Gallai graph Gal(G)of a graph G is a cycle if and only if G is F1,F3,F5 or Ck(k?4)(see Fig.2);The graph G is simple,the Gallai graph Gal(G)of G is a complete k-partite graph if and only if G is k-star(k? 2),P4 or C4.Chartrand and Kronk characterized the graphs satisfing that every linear forest can be extended to a Hamiltonian path in 1968.In the rest of this paper,we give a characterization for the graphs in which every linear forest can be extended to a Hamiltonian cycle.We give a new proof by avioding the result of Chartrand and Kronk.