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))$?
Classifying graphs by patterns in their adjacency matrices
1
$\begingroup$
graph-theory
-
1Interesting 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. – 2012-06-20
-
0What is a "true element" of an adjacency matrix? – 2012-06-20
-
0@Qiaochu, I'm guessing those would be the ones, which would make the zeros "false elements". – 2012-06-20
-
1You 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.) – 2012-06-20
-
0@DayLateDon That's wasn't a glitch--I was indeed clicking the button repeatedly. From now on I will try to click less often. – 2012-06-20