Checking graph properties in linear time given only the adjacency matrix

Question

I came across a problem concerning graphs. Let's define a rake graph.

A n-vertex graph is a rake when it meets certain conditions:

1. there is a vertex of degree 1 in the graph
2. this vertex is connected to a vertex of degree 2
3. this second vertex is connected to another vertex of degree n-2 other vertices may or may not be connected to each other.

I have been given an adjacency matrix for a graph of n vertices. My task is to check if the graph represented by the given matrix is a "rake" or not. The catch is that is has to be done in linear time.

I've tried like everything. It's easy to do when you have adjacency list, but how do I make it take O(n) time with the matrix given?

Answer 1

Okay I seem to have found an answer! There indeed is a linear time algorithm solving this problem, because the problem I presented is called in the world of science checking if a graph is a scorpion graph!

Here you can find the algorithm I'd been looking for. http://www.cs.cornell.edu/courses/cs681/2007fa/Handouts/scorpion.pdf

Thanks for help!