GATE CSE
First time here? Checkout the FAQ!
x
0 votes
60 views

A fan of order $n$ is a graph on the vertices $\{0, 1, \dots, n\}$ with 2n − 1 edges defined as follows: vertex 0 is connected by an edge to each of the other $n$ vertices, and vertex $i$ is connected by an edge to vertex $i + 1$, for $1 \leq i \leq n − 1$.

Let $f_n$ denote the number of spanning trees of the fan of order $n$.

  1. Calculate $f_4$.
  2. Write a recurrence for $f_n$.
  3. Solve for fn using ordinary generating fuctions.
asked in Graph Theory by Veteran (73.4k points)   | 60 views

Please log in or register to answer this question.

Top Users Jan 2017
  1. Debashish Deka

    9830 Points

  2. sudsho

    5596 Points

  3. Bikram

    5330 Points

  4. Habibkhan

    5202 Points

  5. Vijay Thakur

    4508 Points

  6. Arjun

    4458 Points

  7. Sushant Gokhale

    4410 Points

  8. saurabh rai

    4236 Points

  9. santhoshdevulapally

    3896 Points

  10. Kapil

    3848 Points

Monthly Topper: Rs. 500 gift card

19,469 questions
24,254 answers
54,159 comments
20,400 users