Results 1 to 2 of 2

Math Help - Graph Theory Questions

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    3

    Graph Theory Questions

    1. There are two vertices A and B which are both adjacent to the same list of vertices. It's not important whether or not they are adjacent to each other (they may or may not be). Assume there is a third vertex C. Prove that if A is adjacent to the same vertices as B and B is adjacent to the same vertices as C, that A is adjacent to the same vertices as C.

    I know this is pretty obvious when just thinking about it, but I'm not really sure how to formally prove it with a valid argument. Any suggestions?


    2. You are given an adjacency matrix Y for a graph, Y^2 for the graph, and the degrees of each vertex in a graph. How can you use those to determine if every neighbor of some vertex A is also a neighbor of B? Do this testing in constant time.

    I'm not really sure how to approach this one because I don't know the exact properties of adjacency matrices and what they can be used for.


    Any help is appreciated.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,798
    Thanks
    1691
    Awards
    1
    For the first one, do you know about components is a graph?
    \mathbb{C}_A is the set of all vertices, X, such that there is a path from A to X.
    Thus \mathbb{C}_A is a maximal connected subgraphs.
    If B \in \mathbb{C}_A  \cap \mathbb{C}_C  \Rightarrow \quad \mathbb{C}_A  = \mathbb{C}_B  = \mathbb{C}_C .

    I am not quite clear as to what you are expected to do in #2.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09:59 AM
  2. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 03:30 AM
  3. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  4. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 25th 2010, 11:15 PM
  5. Graph theory questions
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 11th 2008, 11:37 AM

Search Tags


/mathhelpforum @mathhelpforum