Scribd Logo
Upload

Welcome to Scribd!

  • 25 views

    π. Prove that π is an automorphism of G if and only if P A = AP - (7 marks)

    Uploaded by

    Baranikumar
    The document discusses properties of graphs and their relationship to eigenvalues, automorphisms, and reconstructability from subgraphs. Specifically: 1) It relates the adjacency matrix A of a graph G to automorphisms of G through permutation matrices. 2) It shows properties of eigenvectors of A that are preserved by automorphisms of G. 3) It uses these properties to relate simple eigenvalues and the order of automorphisms when all eigenvalues are simple. 4) It provides an upper bound on the number of simple eigenvalues in terms of the cycle structure of automorphisms. 5) It discusses when a graph G is a Cayley graph in terms of its automorphism group,

    Copyright:

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

    π. Prove that π is an automorphism of G if and only if P A = AP - (7 marks)

    Uploaded by

    Baranikumar
    25 views2 pages
    The document discusses properties of graphs and their relationship to eigenvalues, automorphisms, and reconstructability from subgraphs. Specifically: 1) It relates the adjacency matrix A of a graph G to automorphisms of G through permutation matrices. 2) It shows properties of eigenvectors of A that are preserved by automorphisms of G. 3) It uses these properties to relate simple eigenvalues and the order of automorphisms when all eigenvalues are simple. 4) It provides an upper bound on the number of simple eigenvalues in terms of the cycle structure of automorphisms. 5) It discusses when a graph G is a Cayley graph in terms of its automorphism group,

    Original Description:

    Maths pg material for reference

    Original Title

    Msc material

    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 discusses properties of graphs and their relationship to eigenvalues, automorphisms, and reconstructability from subgraphs. Specifically: 1) It relates the adjacency matrix A of a graph G to automorphisms of G through permutation matrices. 2) It shows properties of eigenvectors of A that are preserved by automorphisms of G. 3) It uses these properties to relate simple eigenvalues and the order of automorphisms when all eigenvalues are simple. 4) It provides an upper bound on the number of simple eigenvalues in terms of the cycle structure of automorphisms. 5) It discusses when a graph G is a Cayley graph in terms of its automorphism group,

    Copyright:

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

    π. Prove that π is an automorphism of G if and only if P A = AP - (7 marks)

    Uploaded by

    Baranikumar
    The document discusses properties of graphs and their relationship to eigenvalues, automorphisms, and reconstructability from subgraphs. Specifically: 1) It relates the adjacency matrix A of a graph G to automorphisms of G through permutation matrices. 2) It shows properties of eigenvectors of A that are preserved by automorphisms of G. 3) It uses these properties to relate simple eigenvalues and the order of automorphisms when all eigenvalues are simple. 4) It provides an upper bound on the number of simple eigenvalues in terms of the cycle structure of automorphisms. 5) It discusses when a graph G is a Cayley graph in terms of its automorphism group,

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 2

    Section B

    4. Let G be a graph on n vertices and let A be the adjacency matrix of G.


    Let π be a permutation of V (G) and P the permutation matrix representing
    π. Prove that π is an automorphism of G if and only if P A = AP . [7 marks]
    Suppose, from now on, that π is an automorphism of G. Show that if x
    is an eigenvector of A corresponding to the eigenvalue λ, then P x is also an
    eigenvector of A corresponding to λ. [3 marks]
    Deduce that if λ is a simple eigenvalue of A and x is a corresponding
    eigenvector with real components, then P x = ±x. [7 marks]
    Hence show that if all eigenvalues of G are simple, then every non-trivial
    automorphism of G has order 2. [7 marks]
    Suppose now that the permutation π has s cycles of odd length and t
    cycles of even length, when written as a product of disjoint cycles. Prove
    that the number of simple eigenvalues of G is at most s + 2t. [10 marks]

    5. (a) Show that if the automorphism group of a graph G contains a sub-


    permutation group Γ acting regularly on V (G) then G is a Cayley graph of
    Γ with respect to some S ⊆ Γ with S = S −1 . [10 marks]
    (b) Let Γ be a finite group and S ⊆ Γ a generating set of Γ with S = S −1 .
    Let G be the Cayley graph of Γ with respect to S. Show that if φ is an
    automorphism of Γ such that φ(S) = S, then φ is also an automorphism of
    the graph G. [7 marks]
    (c) Now let G be any graph, and let Γ =Aut(G). Suppose Γ is abelian
    and acts transitively on V (G). Show that Γ is an elementary abelian 2-
    group. [You may assume that if an abelian subgroup of SY (the group of all
    permutations on Y ) acts transitively on Y then it also acts regularly.] [7
    marks]
    (d) Let G be a connected cubic Cayley graph Cay(Γ, S) of an abelian
    group Γ, and suppose that G has order 2n which is greater than 8. Show
    that the elements of S are of the form α, β, β −1 where the order of α is 2 and
    that of β is greater than two. Show also that the order of β is either n or
    2n. [10 marks]

    6. (a) Let G be a graph without isolated vertices. Show that the deck of G
    is uniquely determined from the edge-deck of G.
    [Any form of Kelly’s Lemma, if required, may be quoted without proof.] [12
    marks]
    (b) Assuming that the minimum degree δ of a graph G is reconstructible
    from its edge-deck, show that a graph G is edge-reconstructible in each of
    the following cases.
    (i) G contains two adjacent vertices both of degree δ; [2 marks]

    (ii) G contains a (δ + 1)-vertex adjacent to two δ-vertices; [5 marks]

    (iii) G contains a triangle with one δ-vertex and two (δ + 1)-vertices. [3


    marks]

    (c) A graph is said to have property EAk if G − A 6' G − B for any


    two distinct subsets A, B of E(G) with |A| = |B| = k. Prove that if G
    has property EA3 then it can be reconstructed from any two edge-deleted
    subgraphs in its edge-deck. [12 marks]

    You might also like