1. ## Graph theory problem

i am having trouble with this problem so any help would be appreciated!

A dominance digraph is one with no loops in which, for any two distinct vertices Pi and Pj, there is either an edge from Pi to Pj or an edge from Pj to Pi, but not both.

Suppose that A is a square matrix with each entry equal to 0 or to 1. Prove that A is the adjacency matrix for a dominance digraph if and only if A + the transposition of A has all main diagonal entries equal to 0, and all other entries equal to 1.

2. Originally Posted by buckaroobill
A dominance digraph is one with no loops in which, for any two distinct vertices Pi and Pj, there is either an edge from Pi to Pj or an edge from Pj to Pi, but not both.
Why said "Pi to Pj" or "Pj to Pi" if there is one then you have the other .

Anyways.
Suppose that A is a square matrix with each entry equal to 0 or to 1. Prove that A is the adjacency matrix for a dominance digraph if and only if A + the transposition of A has all main diagonal entries equal to 0, and all other entries equal to 1.
The entries in the main diagnol are a_ii meaning v_i is related to v_i. By related I mean there exists an edge and by v_i I mean the i-th vertex.
Thus, any entry in the main diagnol is a_ii meaning , "is v_i related by v_i"? The answer is no, because that would imply there is an edge from v_i to v_i which is not the case heir because we are not considered looped graphs. Hence everything is zero in the main diagnol. Now, everything else is 1 because because v_i and v_j and i not equal to j we have an edge, as stated in the conditions of the problem. Thus, everything else outside the main diagnol is 1.

3. Originally Posted by ThePerfectHacker
Why said "Pi to Pj" or "Pj to Pi" if there is one then you have the other .
No, that is not the case. This is a digraph, that is a directed graph, There is a directed edge from P_i to P_j or the other way but not both.
The graph having no loops will not have any ones on the diagonal of the adjacency matrix; thus the transpose will not either. For the off diagonal entries for any j<>k there will be a 1 in the (j,k) position and a 0 in the (k,j) position or the other way round. Thus adding A+(A^T) we get a matrix in which the diagonal is all zeros and each other entry is a one.