Hamiltonicity Of Complements Of Total Graphs

For a graph G, the total graph T(G) of G is the graph with vertex setV (G)∪E(G) in which the vertices x and y are joined by an edge if x and y areadjacent or incident in G. Let G--- be the complements of total graphs T(G).In this thesis, we concentrate on the hamiltonicity of the complements of totalgraphs T(G) of simple graphs G.Wu Baoyindureng and Meng Jixiang in (Basic properties of total transfor-mation graphs, J. Math. Study 34(2)(2001) 109-116) established some basicproperties of G--- for a graph G. They proved that G--- is connected if andonly if G is neither a star nor a triangle. They also prove that if G is neithera star nor a triangle, then diam(G---)≤3. Harary and Nash-Williams in (Oneulerian and hamiltonian graphs and line graphs, Canad. Math. Bull. 8(1965)701-709) proved that L(G) is hamiltonian if and only if G has a closed trail in-cident with each edge. We call the complement of line graph of a graph G, thejump graph of G adopting the notion in (Subgraph distances in graphs definedby edge transfers, Discrete Math. 170(1997) 63-79). Wu and Meng in (Hamilto-nian jump graphs, Discrete Math. 289(2004) 95-106) give a simple su?cient andnecessary condition for a graph G whose J(G) is hamiltonian. Motivated fromthe results above, we prove thatκ(G---)≥δ(G---) ? 1 and further establishthat G--- is hamiltonian if and only if G is not isomorphic to any graph in{K_1,r| r≥1}∪{K_1,s+K₁| s≥1}∪{K₁,t+e| t≥2}∪{K₃,K₃+K₁,K₃+2K₁,K₄}.Finally, we give a simple su?cient and necessary condition for a graph G whoseG--- has a perfect matching.