I suppose you are talking about things like incidence matrices and adjacency matrices (or even lists). You can find these constructions in any graph theory textbook (introductory). Certain operations like squaring them as a matrix can tell you things, and also are a more efficient means of representing them on a computer.

For example, suppose I have a graph G=(V,E), where:

V={1,2,3,4,5}

E={{1,2},{3,5},{4,2}}

For example, an adjacency matrix is described as follows. We say A[i][j]=1 if there is an edge {i,j} in E, and 0 otherwise.

Then the adjacency matrix A for G above is:

A= 0 1 0 0 0

1 0 0 1 0

0 0 0 0 1

0 1 0 0 0

0 0 1 0 0.

Hope this helps! :)

The usual keywords are "algebraic graph theory" or "spectral graph theory". The book of Godsil-Royle is a perfect introduction to this topic.

Daniel/Dello, thanks for your suggestion. What about matroids? One notion I am trying to grasp is the idea of independence.

Chapter 15 in Godsil-Royle's book is devoted to matroids.

I guess I better grab this book - Godsil I read came from Melbourne :-)

Relationship of graph theory with linear algebra or converting graphs into vector spaces, you can find in any book of Discrete Mathematics-Graph Theory.

There are some links for beginning:

GRAPH THEORY

http://math.tut.fi/~ruohonen/GT_English.pdf

Graph Embedding

http://www.informatik.uni-ulm.de/ni/ANNPR10/InvitedTalks/Buh...

Thanks so much Qefsere, that PDF from Finland is probably just what I need for now.

Most courses/texts/etc., tend to use the word "associate" (i.e., "We start with two vector spaces associated with every graph – the cycle space and the cocycle space; from Knauer's Algebraic Graph Theory). Among other reasons, vector spaces excluding the null space consist of linear combinations of vectors (outside of intro matrix/linear algebra texts and sometimes even in these they are defined in terms of fields, specifically in terms of some vector space over a field such as R). That is, while it is easy enough to associate a graph to basis vectors that span some vector space V, the actual space consists of infinitely many elements.

That is a key part of independence, actually. Given some set of vectors, if they span some vector (sub)space then no addition of them or any scalar multiplication of any of them can take you out of that space. Given some set of vectors in R2, for example, they cannot span the "space" of some line unless that line is through the origin (also, if span is taken to mean minimal span of a subspace, which every line is in the space R2, redundancy comes into play).

The relationship between graph theory and linear algebra is algebra. Algebraic structures and representations (and representation theory) all can by crudely and simplistically subsumed under "abstract algebra", and while such a broad definitions misses crucial distinctions, it does provide a foundation for understanding why text on graph theory or linear algebra contain terms, concepts, definitions, propositions, etc., one may find in a text on algebraic topology or Boolean algebra. Whether lattices or Lie groups, algebras are concerned centrally with abstracting away from the algebra we all learned before college to arbitrary alphabets, sets, etc., to create algebraic structures. Graph theory is in many ways a more direct and intuitive method to represent, examine, and investigate algebras (more flexibly than possible using the language of geometry).

It can be basis as a vertex space or vertex set then edge space or edge set is the symmetric difference of the vertex space elements for a particular vector space

Like Daniel mentioned, the canonic way is to build an adjacency matrix.

Adjacency matrices are heavily used in spectral graph theory which deals with the eigenvalues of such graphs. A few theorems worth mentioning:

1. Two graphs are called isospectral or cospectral if the adjacency matrices of the graphs have equal multisets of eigenvalues (ref. Wikipedia).

2. Almost all trees are cospectral (ref. Wikipedia).