Maximum cardinality neighbourly sets in quadrilateral free graphs

Neighbourly set of a graph is a subset of edges which either share an end point or are joined by an edge of that graph. The maximum cardinality neighbourly set problem is known to be NP-complete for general graphs. Mahdian (Discret Appl Math 118:239–248, 2002) proved that it is in polynomial time for quadrilateral-free graphs and proposed an (O(n^{11})) algorithm for the same, here n is the number of vertices in the graph, (along with a note that by a straightforward but lengthy argument it can be proved to be solvable in (O(n^5)) running time). In this paper we propose an (O(n^2)) time algorithm for finding a maximum cardinality neighbourly set in a quadrilateral-free graph.