Scribd Logo
Upload

Welcome to Scribd!

  • 5 views

    SGSDGSDSFGSRGRSGRGSR

    Uploaded by

    dreamivory29
    The document is an exam paper for an advanced graph theory course. It contains 6 questions with 2 parts each about graph theory topics like independent dominating sets, transitive permutation groups, Cayley graphs, and properties of graph eigenvalues and characteristic polynomials.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    SGSDGSDSFGSRGRSGRGSR

    Uploaded by

    dreamivory29
    5 views2 pages
    The document is an exam paper for an advanced graph theory course. It contains 6 questions with 2 parts each about graph theory topics like independent dominating sets, transitive permutation groups, Cayley graphs, and properties of graph eigenvalues and characteristic polynomials.

    Original Title

    sgsdgsdsfgsrgrsgrgsr

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document is an exam paper for an advanced graph theory course. It contains 6 questions with 2 parts each about graph theory topics like independent dominating sets, transitive permutation groups, Cayley graphs, and properties of graph eigenvalues and characteristic polynomials.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    5 views2 pages

    SGSDGSDSFGSRGRSGRGSR

    Uploaded by

    dreamivory29
    The document is an exam paper for an advanced graph theory course. It contains 6 questions with 2 parts each about graph theory topics like independent dominating sets, transitive permutation groups, Cayley graphs, and properties of graph eigenvalues and characteristic polynomials.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 2

    Reg.

    No

    MANIPAL UNIVERSITY, MANIPAL


    FOURTH SEMESTER M.SC (APPLIED MATHEMATICS & COMPUTING) END SEMESTER
    EXAMINATION –MAY 2011
    SUB : ADVANCED GRAPH THEORY

    (REVISED CREDIT SYSTEM)


    Time : 3 Hrs. Max.Marks : 50

    Note : Answer any FIVE full questions.

    1A. Define an independent dominating set in a graph G. Show that every Claw –
    free graph has an independent dominating set of size  (G).

    1B. Define the graphs J (v, k,i). Find its order and size. Show that if v  k  i then
    J(v, k, i)  J (v, v – k, v – 2k +i)

    (5+5)

    2A. Let G be a transitive permutations group on V and let x be a point in V.


    Then show that G is primitive if and only if Gx is a maximal sub group
    of G.

    2B. Let D be a directed graph such that the in valency and out valency of any
    vertex are equal. Then show that D is strongly connected if and only if it is
    weakly connected.

    (5+5)

    3A. Define Cayley graph and show that the Cayley graph X (G,C) is vertex
    transitive.

    3B. Let X be a graph on n vertices with connectivity K . Suppose A and B are


    fragments of X and A B . If A Bˆ , then show that A B is a fragment.

    (5+5)

    Page 1 of 2
    4A. Let G be a group and S be a connector set. Show that the C(G,S) is
    connected iff S is a generating set G.

    4B. Let G be a graph on n vertices columns j1, j2 .........., jk of Q (G) are linearly
    independent iff the corresponding edges of G induce acyclic graph.

    (5+5)

    5A. Define a path a matrix Pn. Let G be a tree with vertex set {1,2, ....,n}. Let Q
    be the incidence matrix of G and let Qn be the reduced incidence matrix
    obtained by deleting the row n of Q . Show that Qn1 Pn .

    5B. Show that the complete graph on n vertices is completely determined by


    its eigen values.

    (5+5)

    6A. Let G be a graph and PG() be the characteristic polynomial of G. Let x1 be


    a vertex of degree 1 in G and x2 be the vertex adjacent to x1. Let G1 be the
    induced subgraph obtained from G by deleting the vertex x1. If x1 and x2 are
    deleted the induced subgraph G2 is obtained. Then show that
    PG PG 1 PG 2 .

    6B. For n  1, show that the eigenvalues of Pn are


    k
    2cos , k = 1, 2, ......,n .
    n 1

    (5+5)

    ********

    Page 2 of 2

    You might also like