0
$\begingroup$

How can you get the degree distribution of a graph from the following formulas, and also determine if those graphs are directed or not ? :

where $\delta$ represents the Kronecker delta

a) $A_{ij} = \delta_{i,j+1}$ for $j< N$ , and $A_{iN} = 0.$

b) $A_{ij} = 1$ for all $i,j \in {1,.....,N}$

I tried to represent those graphs with a $3$ node graph to begin but for the first graph I get an adjacency matrix where the diagonal is all made of $1$ and the rest $0$ which is impossible.

Do you have any ideas ?

$\endgroup$
2
$\begingroup$

Start by looking at a small example of each graph, say the case $N=4$. The second one is easy: the adjacency matrix is

$$\begin{array}{cc} &v_1\;\;v_2\;\;v_3\;\;v_4\\ \begin{array}{c}v_1\\v_2\\v_3\\v_4\end{array}&\begin{bmatrix} 1&1&\color{red}1&1\\ 1&1&1&1\\ \color{blue}1&1&1&1\\ 1&1&1&1 \end{bmatrix} \end{array}$$

Here the red $1$ indicates that there is an edge from $v_1$ to $v_3$, and the blue $1$ shows an edge from $v_3$ to $v_1$. In fact, you can see that all of the off-diagonal entries come in symmetric pairs, so the graph is not directed. (It’s the complete graph on $4$ vertices, plus a loop at each vertex.)

For the first one we have to work a little harder. For $j<N$ we have

$$A_{ij}=\delta_{i,j+1}=\begin{cases} 1,&\text{if }i=j+1\\ 0,&\text{otherwise}\;, \end{cases}\tag{1}$$

and we have $A_{iN}=0$ for all $i$. That last clause means that the last column of the adjacency matrix is all $0$, and it turns out that $(1)$ puts $1$s on the first subdiagonal, the diagonal immediately under the main diagonal: those are the positions whose row numbers are $1$ more than their column numbers. If $N=4$, for instance, we have $A_{21}=A_{32}=A_{43}=1$, and every other entry in the matrix is $0$. Thus, the matrix is

$$\begin{array}{cc} &v_1\;\;v_2\;\;v_3\;\;v_4\\ \begin{array}{c}v_1\\v_2\\v_3\\v_4\end{array}&\begin{bmatrix} 0&0&0&0\\ 1&0&0&0\\ 0&1&0&0\\ 0&0&1&0 \end{bmatrix} \end{array}$$

There are no $1$s that are symmetrically placed on opposite sides of the main diagonal, so there are no vertices $v_i$ and $v_j$ with an edge from $v_i$ to $v_j$ and also an edge from $v_j$ to $v_i$; thus, this graph is directed. Can you sketch and identify it? It has a very simple shape.

Now just generalize from $4$ to $N$. The degree distributions can easily be found once you identify the graphs. Alternatively, note that if the graph is directed, the row for $v_i$ shows edges leaving $v_i$, and the column for $v_i$ shows edges entering $v_i$, and a very similar idea gives you the degrees if the graph is undirected.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.