4
$\begingroup$

Question: Let $G$ be a strongly connected directed graph on $n$ vertices with Laplacian $L(G)$. Then $L(G)$ has one zero eigenvalue $\lambda_1=0$ and $n-1$ nonzero eigenvalues $\lambda_2,\ldots,\lambda_{n}$. Suppose the nonzero eigenvalues have constant absolute value, i.e., $|\lambda_2|=|\lambda_3|=\cdots=|\lambda_{n}|$. Can we say anything about the structure of $G$?

My thoughts: I conjecture that this implies $G$ has constant outdegree. I have a reason to believe this. There is a family of regular digraphs which satisfy the property, the doubly regular digraphs defined in this paper.

Improve this question
$\endgroup$
2
  • $\begingroup$ Can you tell which Laplacian you have taken? $\endgroup$
    – mukhujje
    Commented Sep 8 at 9:47
  • $\begingroup$ $L(G)_{ij} = deg^+ (v_i)$ if $i=j$ and $-a_{ij}$ if $i\neq j$. In other words $L(G)=D(G)-A(G)$ where $D(G)$ is the diagonal matrix with outdegrees and $A$ is the adjacency matrix. $\endgroup$
    – Aditya Bandekar
    Commented Sep 8 at 21:07

1 Answer 1

Reset to default
5
$\begingroup$

This is false.

Run this code in SageMath; you can do this at sagecell.sagemath.org if you do not have SageMath already installed on your own computer.

h = DiGraph('DKCYW?')
print(h.laplacian_matrix().eigenvalues())
print(h.out_degree_sequence())
h.plot()

In any case, here is the output that should see:

enter image description here

How did I find it?

I used the list of digraphs from Brendan McKay's website, altered the format so that SageMath can read them, and then just looked at what happened.

Warning

SageMath uses Brendan McKay's graph6 format for undirected graphs to represent a graph as string of printable characters (each character stores 6 bits of the adjacency matrix). Although Brendan also has a similar format for directed graphs, SageMath uses its own slightly different one.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Great find! How did you find this counterexample? If it was with another Sage script, it may be useful for the answer to include its source as well, so you can "teach to fish". $\endgroup$
    – Federico Poloni
    Commented Sep 9 at 6:20
  • 1
    $\begingroup$ @FedericoPoloni Good point, I have added some extra information. $\endgroup$
    – Gordon Royle
    Commented Sep 9 at 6:40
  • $\begingroup$ Thanks for the counterexample. I'll accept the answer. I would still be interested in knowing if there is anything positive we could say about digraphs which satisfy the property if anyone knows. $\endgroup$
    – Aditya Bandekar
    Commented Sep 9 at 17:51
  • $\begingroup$ @AdityaBandekar There are not very many (small) digraphs that do have this property and lots of them look somewhat similar so it might be worth staring at a bunch of pictures to see if anything stands out. $\endgroup$
    – Gordon Royle
    Commented Sep 9 at 20:08

You must log in to answer this question.

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