Results 1 to 6 of 6
Like Tree2Thanks
  • 1 Post By johnsomeone
  • 1 Post By johnsomeone

Math Help - periphery of a graph

  1. #1
    Junior Member
    Joined
    Jan 2010
    Posts
    61
    Thanks
    3

    periphery of a graph

    Let (eccentricity of v) e(v)=Max_{u \in V(G)} d(u,v) and diam(G)= Max_{v \in V(G)} e(v), where V(G) is the set of vertices of G and d(u,v) is the distance between u and v. Let (periphery of G) Pe(G) be the graph induced by the vertices of G that have eccentricity equivalent to diam(G). Now suppose that the graph H has n vertices. Prove that H is Pe(G) if and only if \Delta(H) \le n-2. ( \Delta(H) is the maximum degree in H)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    147

    Re: periphery of a graph

    You need an additional constraint/premise of some kind. It's not true as stated.

    \text{If } K_n \text{ is the complete graph on } n \text{ verticies } (n \ge 2), \text{ then}

    diam(K_n) = 1, \text{ and } e(v) = 1 = diam(K_n) \ \forall \ v \in V(K_n),

    \text{and so } Pe(K_n) = K_n.

    \text{But } \Delta(K_n) = n-1 = |V(K_n)| - 1,

    \text{which contradicts this problem's claim that}

    H = Pe(K_n) (= K_n) \Rightarrow \Delta(H) \le |V(H)| - 2.
    Last edited by johnsomeone; October 26th 2012 at 01:00 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jan 2010
    Posts
    61
    Thanks
    3

    Re: periphery of a graph

    You're right. Assume that no vertex in H has eccentricity 1.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    147

    Re: periphery of a graph

    \text{Let } G \text{ be a connected graph such that } diam(G) > 1 \text{ (i.e connected, not complete, having 3+ verticies.)}

    \text{ASSUME } \exists v \in H = Pe(G) \ni deg_H(v) = |V(H)|-1.

    \text{Since } v \in Pe(G), \exists w \in G \ni e(v) = dist(v, w) = diam(G).

    \text{Since } diam(G) = dist(v, w) \le e(w) \le diam(G),

    \text{have that } e(w) = diam(G), \text{ and so } w \in H.

    \text{But then } v, w \in H, \text{ and so since } deg_H(v) = |V(H)|-1,

    \text{have that } (v,w) \in E(H).

    \text{Since } H \text{ is an induced subgraph of } G, \text{ have that } (v,w) \in E(G).

    \text{But } (v,w) \in E(G) \Rightarrow dist(v, w) = 1 \Rightarrow diam(G) = dist(v, w) = 1, \text{ contrary to the premises.}

    \text{Thus the initial assumption led to a contradiction.}

    \text{Thus } x \in H \Rightarrow deg_H(x) \le |V(H)|-2.

    \text{Therefore } \Delta(Pe(G)) \le |V(Pe(G))|-2.
    Last edited by johnsomeone; October 27th 2012 at 12:43 AM.
    Thanks from xixi
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jan 2010
    Posts
    61
    Thanks
    3

    Re: periphery of a graph

    what about the converse?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    147

    Re: periphery of a graph

    \text{Let } H \text{ be a graph such that } \Delta(H) < |V(H)|-1 \text{ and } |H| > 1.

    \text{Then for all } v \in H \text{ have that } deg_H(v) < |V(H)|-1,

    \text{and so if } v \in H \text{ there exists } w \in H \text{ such that } (v, w) \notin E(H).

    \text{Define } G \text{ by } V(G) = V(H) \cup \{ x \}, E(G) = E(H) \cup \{ (x,v) | v \in V(H) \}.

    \text{Then for all } v \in H \subset G, dist_G(v, x) = 1 \text{ since } (v, x) \in E(G).

    \text{Thus } e_G(x) = 1.

    \text{From before, if } v \in H \subset G, \text{ there exists } w \in H \text{ such that } (v,w) \notin E(H),

    \text{and so by the definition of } E(G), \text{ also have that } (v,w) \notin E(G).

    \text{So for all } v \in H \subset G, \text{ this proves that } e_G(v) > 1, \text{ since } dist_G(v, w) > 1.

    \text{Now, for all } v, w \in H \subset G, \{(v, x), (x, w) \} \subset E(G),

    \text{and so, for all } v, w \in H \subset G, \ dist_G(v, w) \le 2.

    \text{But from that it follows that, for all } v \in H \subset G, e_G(v) \le 2.

    \text{(That conclusion also requires also remembering that } dist(v, x) = 1.)

    \text{So have shown that, for all } v \in H \subset G, 1 < e_G(v) \le 2.

    \text{Therefore, if } v \in G, v \ne x, \text{ then } e_G(v) = 2. \text{ Also, } e_G(x) = 1.

    \text{That proves that } diam(G) = 2, \text{ and so also that } Pe(G) = H,

    \text{since } Pe(G) = \ < \{ v \in V(G) | e_G(v) = diam(G) = 2 \} > \ = \ < H > \ = H.
    Last edited by johnsomeone; October 27th 2012 at 12:32 PM.
    Thanks from xixi
    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, 10:59 AM
  2. Replies: 7
    Last Post: August 5th 2011, 02:30 PM
  3. Replies: 0
    Last Post: September 25th 2010, 06:59 AM
  4. Replies: 1
    Last Post: October 2nd 2009, 10:43 AM
  5. Replies: 1
    Last Post: February 15th 2009, 06:35 AM

Search Tags


/mathhelpforum @mathhelpforum