Edge and vertex spaces

In the mathematical discipline of graph theory the edge space for a finite undirected edge labeled graph is vector space structure on the edge set of the graph, making it possible to use linear algebra for studying the graph.

Definition

Let $G:=(V,E)$ be a finite undirected edge labeled graph with $n$ edges. The edge space ${\mathcal {E}}(G)$ is an $n$ dimensional vector space over $\mathbb {Z} _{2}:=\lbrace 0,1\rbrace$ defined as follows

• elements of the vector space are subsets of the power set of $E$
• vector addition is defined as the symmetric difference: $U+V:=U\triangle V\qquad U,V\in {\mathcal {E}}(G)$
• $0\cdot U:=\emptyset \qquad U\in {\mathcal {E}}(G)$
• $1\cdot U:=U\qquad U\in {\mathcal {E}}(G)$

The set of edges $\lbrace \lbrace e_{1}\rbrace ,\ldots ,\lbrace e_{n}\rbrace \rbrace$ forms a canonical basis for ${\mathcal {E}}(G)$.

Properties

The incidence matrix $H$ for a graph $G$ defines a linear transformation

$H:{\mathcal {E}}(G)\to {\mathcal {V}}(G)$

between the edge space and the vertex space of $G$. It maps each edge to its two incident vertices. Let $vu$ be the edge between $v$ and $u$ then

$H(vu)=v+u$

The cycle space and the cut space are linear subspaces of the edge space.

See also

• vertex space
• cycle space
• cut space