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?

  • 3
    $\begingroup$ 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. $\endgroup$ – Countingstuff Feb 20 '18 at 10:57
  • $\begingroup$ Thank you. Line graph was the key word I was missing. $\endgroup$ – Eckhard Feb 21 '18 at 7:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.