Domination Number,feedback Vertex Number And Wiener Index Of Complements Of Line Graphs

In general,determining the feedback vertex number τ(G)and the domination number Υ(G)of a claw-free graph G(even for a line graph L(G))is NP-hard.In contrast,the situation become different for the complement of line graphs.In this paper,it is shown that Υ(G)≤<3 for a claw-free G with α(G)≥3,and thus deter-mining the domination number of the complements of a claw-free G with α(G)≥3 is polynomial,where a(G)is the independence number of G.Furthermore,if a graph G is not a star,has no isolated vertex and isolated edge,then 2≤7(J(G))≤3,where J(G)is the complement of the line graph L(G)of G.If a graph G is not a star,and has no isolated vertex,τ(J(G))=n-△((G)-1,provided △(G)≥6.For the case when △(G)≤5,τ(J(G))is also given.There by,we are able to show that,determining τ(J(G))is polynomial.The Wiener index W(G)of G is the sum of the distances between all pairs of vertices in G.In this paper,we determine the Wiener index of J(G),where J(G)is connected.