Closed Walks and Edge Addition

Question

If $G$ is a simple graph with adjacency matrix $A$, then $c_k(G):=\mbox{tr}A^k$ gives the number of closed walks in $G$ of length $k$. Let $G'$ denote the graph obtained from $G$ by adding an edge between any two vertices (no multiple edges allowed). Then one should have $c_k(G)\leq c_k(G')$. My question is the following. Is it true that $c_k(H)\leq c_k(G)$ implies $c_k(H')\leq c_k(G')$ ? It feels like it should be true but cannot seem to prove this fact. Any references would be appreciated.

Edit: Graphs $G$ and $H$ have the same order and are connected.

Answer 1

This does not hold in general. Let's set $k=3$ and consider the following counterexample:

Here, $c_3(H) = 6$ (there are $3$ closed walks per triangle), which is strictly less than $c_3(G) = 9$.

The only possible edge we can add to $H$ is the one showed with a dashed line (this way $H$ turns into a $K_4$). And there are several edges that we can add to $G$, but all of them accomplish the same: Connect one vertex of one triangle to another.

Then $c_3(H') = 12$, because there will be $3$ small triangles and $1$ large one, a total of $4$ triangles, and there are still $3$ closed walks per triangle subgraph. But $c_3(G')$ doesn't change, there are no new closed walks of length $3$.

So $c_3(H) < c_3(G)$, but $c_3(H') > c_3(G')$.

Answer 2

I think that your conjecture is false.

For example, let $H$ be a cycle of length $6$ and $G$ a cycle of length $7$. And let $H', G'$ be $H,G$ with the addition of one edge (say, for example, $(1,3)$)

Unless I've made a mistake this is a counterexample to the conjecture: $c_7(H) = 0$ and $c_7(G) = 14$, but $c_7(G') = 350$ and $c_7(H') = 434$. So the order flips after the addition of an edge.

My guess is that for "most" graphs and "most" lengths your conjecture holds, though.

Answer 3

I have given an answer yesterday, but the question was since augmented with two other requirements.

If we require $G$ and $H$ to be of the same order and to both be connected, then there is still a counterexample:

Here, $|V(G)| = |V(H)| = 6$, and let us consider the case of $k=3$ again.

It is generally true that

$$\# \{ \text{walks of length } 3 \} = 3 \cdot \# \{ \text{triangles of length }3\}$$

(Or if we consider walks in the opposite direction different, then it's $6 \cdot \# \{ \text{triangles of length } 3\}$; however, this won't change the result, as it will simply multiply every value by a factor of $2$.)

Then

• $c_3(H) = 12$, because there are $4$ triangles in it.
• $c_3(G) = 15$, because the $K_4$ contains $4$ triangles, and one extra was appended to it, making it contain $5$ triangles in total.
• $c_3(H') = 24$, because the $4$ triangles remain, but we actually created $4$ new triangles with the new edge, so it contains a total of $8$ triangles.
• $c_3(G') = 18$, because the $5$ triangles remain, and we only created one new one, since the new edge connects to a vertex that had a degree of $1$, so no other triangles get created; making it have a total of $6$ triangles.

So even though $H, G, H'$, and $G'$ are all connected graphs with $|V(H)| = |V(G)|$ and $|V(H')| = |V(G')|$, we were still able to find a counterexample where

• $c_3(H) < c_3(G)$, but
• $c_3(H') > c_3(G')$.