Results 1 to 4 of 4

Math Help - A problem on Graph theory and algorithms

  1. #1
    Junior Member Sarasij's Avatar
    Joined
    Jun 2011
    From
    India
    Posts
    42
    Thanks
    2

    A problem on Graph theory and algorithms

    The problem is as follows:
    ---------------------------------------------------------------------------------------------------------------------------------
    Let G be a connected graph.

    For a vertex x of G we denote by G−x the graph formed by removing x and all edges incident on x from G. G is said to be good if there are at
    least two distinct vertices x,y in G such that both G − x and G − y are connected.

    (i) Show that for any subgraph H of G, H is good if and only if G is good.

    (ii) Given a good graph, devise a linear time algorithm to find two such vertices.

    (iii) Show that there exists a graph G such that we cannot find three distinct vertices
    u1,u2,u3such that each of G − u1,G − u2, and G − u3 is connected.
    ---------------------------------------------------------------------------------------------------------------------------------
    I have approached to some extent. Here is what I've done:

    If G is a connected graph then we can easily find its spanning tree and then removing any two leaves x and y from the tree one at a time gives us 2 another graphs G − x and G − y such that they are both connected.

    "Hence any connected graph G is a good graph."

    1. I'm stuck on how to solve part (i).

    2. I have designed the algorithm for the part(ii) which extracts the spanning tree from G and then finds two such leaves x and y. Clearly
    it is linear in terms of #vertices(=n) & #edges(=m) i.e. O(n+m)

    3. I have also solved the third part with a graph as follows:

    O------------------O-----------------O

    In the above graph G we denote three vertices as u1, u2, u3. The edges are (u1,u2) and (u2,u3). Clearly G − u2 is not connected.

    Please help me in solving part(i).

    Please help guys...

    Thanks in advance!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Dec 2011
    Posts
    27
    Thanks
    1

    Re: A problem on Graph theory and algorithms

    Show that for any subgraph H of G, H is good if and only if G is good.

    As written this claim is false. (Unless you define subgraph differently than what I am assuming)
    Counter: Let G be P_5 (a path on 5 vertices). Then clearly G is good. Let H be a subgraph created by removing a single vertex of degree 2 in G. Then H is disconnected and cannot be good. Hence the claim fails.

    This is true if you say: for any connected subgraph H of G, H is good if and only if G is good. But you already proved a stronger statement than this, that all connected graphs are good.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member Sarasij's Avatar
    Joined
    Jun 2011
    From
    India
    Posts
    42
    Thanks
    2

    Re: A problem on Graph theory and algorithms

    Yes you are right...anyways thanks for pointing the counter eg ...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    May 2012
    From
    slovenia
    Posts
    14

    Re: A problem on Graph theory and algorithms

    How to prove that Hamming graph H(d,3) has a diameter d?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 19th 2011, 02:29 AM
  2. Graph Theory Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 18th 2010, 08:36 PM
  3. Help with Graph theory problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 18th 2010, 09:53 PM
  4. Graph Theory problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 9th 2009, 12:50 PM
  5. Graph theory Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 16th 2009, 08:18 AM

Search Tags


/mathhelpforum @mathhelpforum