Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a set $S$, how can we classify different graphs $G(S)$ (tree, connected/disconnected, ...) based on the patterns of the 1's and 0's in their adjacency matrices $M(G(S))$?

share|cite|improve this question
Interesting idea. However, classification based on the "physical" arrangement of elements in the adjacency matrix can be tricky, because that arrangement depends on the correspondence between graph vertices and matrix rows and columns. It's unlikely that any property of "Snake" gameplay persists across reordering of the rows and columns, except in the least-complicated of cases, even when the reordered matrix represents the same graph. – Blue Jun 20 '12 at 4:01
What is a "true element" of an adjacency matrix? – Qiaochu Yuan Jun 20 '12 at 4:18
@Qiaochu, I'm guessing those would be the ones, which would make the zeros "false elements". – Gerry Myerson Jun 20 '12 at 4:45
You might want to avoid clicking the "Post Your Question" button until your thoughts have settled. If the StackExchange software is posting your many in-progress edits without you clicking that button, then report that on "Meta" as a bug, and consider composing your text off-site. That way, the rest of us can avoid commenting on an ever-evolving formulation of your question. (My reference to "'Snake' gameplay" is going to seem odd to people who read the question in its current form. Actually, I'm somewhat disappointed that the game element is gone from the question.) – Blue Jun 20 '12 at 5:25
@DayLateDon That's wasn't a glitch--I was indeed clicking the button repeatedly. From now on I will try to click less often. – idonutunderstand Jun 20 '12 at 5:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.