2
$\begingroup$

I am not very familiar with graph theory, but I need some results for my work. Thus, the question is, whether the following has already been studied and where I can find it. Let $G=(V,E)$ be an graph and let $b$ be its first Betti number. We choose $b$ directed cycles in $G$, which form a homology basis. Further, we write $\tau_j\subseteq E$ for the set of edges in the $j$-th cycle. To every edge $e$ we associate an indeterminant $T_{e}$. Now consider the $b\times b$-matrix with entries $$a_{jk}=(-1)^{\epsilon(j,k)}\sum_{e\in\tau_j\cap\tau_k}T_e,$$ where $\epsilon(j,k)$ is $0$ if the $j$-th and the $k$-th cycle have the same direction on their intersection, and $1$ otherwise. I think, one can always choose the cycles such that $\epsilon(j,k)$ is always $0$.

Has a matrix like this been studied in graph theory, especially its determinant and its adjugate? This should be possible by elementary combinatoric, but it would be nice to have a reference and maybe there are more known interesting facts.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

For a connected $G$, in the case of the cycles being chosen in the usual way --- one for each edge of $G$ outside a spanning tree $\Theta$ of $G$, this matrix can be identified with a submatrix of $A^\top A$, for $A$ the oriented incidence matrix of $G$. That is, $A$ is an $|V|\times |E|$ matrix of the map $\mathbb{R}E\to \mathbb{R}V$ given by $$ A_{ve}=\begin{cases} 0 & v\not\in e\\ 1 &e=(vv')\\-1 &e=(v'v)\end{cases}. $$ Choosing the ordering of $E$ so that the edges outside $\Theta$ come first, the matrix in question is the $b\times b$ submatrix of $A^\top A$ formed by its 1st $b$ rows and columns.

Note that $A^\top A-2I$ is some kind of $1,-1$-adjacency matrix of the directed line graph of $G$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thank you. That is exactly the case, I am interested in. $\endgroup$
    – Robert Wilms
    Commented Mar 31, 2015 at 11:22
  • $\begingroup$ Please double-check. The diagonal entries in particular look different to me, and perhaps either $A$ or $A^\top$ should be prefilled with $\pm T_{e}$ rather than $\pm 1$. $\endgroup$
    – Dima Pasechnik
    Commented Mar 31, 2015 at 11:41
  • $\begingroup$ Yes, it looks different. But I think, this works, if one starts with the $b\times |E|$ matrix $$a_{j,e}=\begin{cases}0&e\notin \tau_j\\ \sqrt{T_e}&e\in\tau_j\end{cases}$$ and if the cycles are chosen to have the same directions on their intersections. Can I always choose a spanning tree, such that the fundamental base of cycles satisfies this? $\endgroup$
    – Robert Wilms
    Commented Mar 31, 2015 at 12:25
  • $\begingroup$ I don't see how you can choose orientation of cycles independently. You can choose orientations for edges, but that's all, no? $\endgroup$
    – Dima Pasechnik
    Commented Mar 31, 2015 at 13:07
  • $\begingroup$ I mean, I have an undirected graph and I choose cycles and for every cycle an orientation. The orientation of the cycles induces orientations for the edges, but these orientations depends on the cycle, thus two different cycles can induce two different orientations on the same edge, let's call this case a bad choice of orientations for the cycles. Now there are spanning trees, such that there are only bad choices of orientations for the fundamental cycles. Are there always spanning trees, such that there are good choices of orientations? $\endgroup$
    – Robert Wilms
    Commented Mar 31, 2015 at 14:10
2
$\begingroup$

This is to answer a question that arose in the discussion of the 1st answer. Namely, we would like to know whether there always exists an orientation of $G$ s.t. its fundamental cycles are "coherent", in the sense that if two cycles have a common edge then its orientation equals the orientations of the cycles.

This is certainly possible if $G$ admits a spanning path $P$ (a.k.a. Hamiltonian path): take a walk on $P$ from one end to the other, and orient each edge in $P$ accordingly; this gives a total order $<$ on $V$, and each (directed) edge $(uv)$ in $P$ satisfies $u<v$ in this order; orient each edge $(ab)$ outside $P$ in the opposite direction, i.e. $a>b$.

While not every connected graph has a spanning path, it does have a rooted normal spanning tree $P$, also known as depth-first-search (DFS) tree, also known as Trémaux tree. For $P$ (i.e. you have a partial order $<$ on $V$ induced by $P$), and for every (undirected) edge $(ab)$ of $G$, one has that either $a<b$ or $b<a$. Now, just in the case of the spanning path, orient the edges outside $P$ in the opposite direction to the one for the edges in $P$; this induces an orientation on every fundamental cycle of $G$ (such cycles are in 1-to-1 correspondence with edges outside $P$).

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .