Results 1 to 3 of 3

Math Help - Graph theory problem

  1. #1
    Junior Member
    Joined
    Dec 2006
    Posts
    43

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by buckaroobill View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,649
    Thanks
    1596
    Awards
    1
    Quote Originally Posted by ThePerfectHacker View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory Problem #2
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 20th 2010, 03:44 AM
  2. Graph Theory Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 18th 2010, 08:36 PM
  3. Graph theory Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 16th 2009, 08:18 AM
  4. A graph theory problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 15th 2009, 11:08 AM
  5. Help with Graph Theory problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 2nd 2008, 10:08 PM

Search Tags


/mathhelpforum @mathhelpforum