# Edge-to-edge incidence structure of a graph

The Incidence matrix of a graph $G=(V,E)$ with $n=|V|$ numbered vertices $v_i$ and $m=|E|$ numbered edges $e_j$ is defined as the $n\times m$-matrix $M=(M_{ij})$ defined by $$M_{ij}=\begin{cases}1 & \text{v_i is an endpoint of e_j,}\\0& \text{else.}\end{cases}$$

I was thinking about a related structure, for which I could find very little information in the literature. The notion of two edges being coincident if they share a vertex suggests the definition of the coincidence matrix $Q_{ij}$, which is the $m\times m$-matrix defined by

$$Q_{ij}=\begin{cases}0 & i=j,\\1 & \text{e_i and e_j are coincident,}\\0& \text{else.}\end{cases}$$ I choose to define the diagonal entries $Q_{ii}$ as zero, even though 1 or 2 seem equally natural choices to me.

Now, unlike with incidence matrices, there is now no one-to-one correspondence between a graph and its coincidence matrix. For example the triangle graph and the star graph with three leaves both have three edges and give rise to the coincidence matrix $$Q=\left(\begin{array}{ccc}0 & 1 & 1\\ 1 & 0 & 1\\ 1& 1 & 0\end{array}\right)$$ I suppose this ambiguity could be resolved by not restricting attention to the graph associated to $Q$ (viewed as an adjacency matrix) but considering hypergaphs or simplicial complexes instead.

Question 1: What information about the graph $G$ is contained in its coincidence matrix $Q$?

I noticed that for random Bernoulli graphs, the corresponding coincidence matrices appeared to have repeated eigenvalue $-2$.

Question 2: How are the spectral properties of $G$ related to the spectral properties of $Q$?

Question 3: What are good references to read about the notion of coincidence matrix / (hyper-)graph / complex defined above?

• The coincidence matrix corresponds to the adjacency matrix of the line graph of $G$ right? In which case Whitney isomorphism theorem answers your first question. – Countingstuff Feb 20 '18 at 10:57
• Thank you. Line graph was the key word I was missing. – Eckhard Feb 21 '18 at 7:53