2002/01/01 by Edgar M. Palmer, Ronald C. Read, Robert W. Robinson · 1 citation
Mathematics · Computer Science · #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics #Polynomial and algebraic computation #Mathematics #Enumeration #Combinatorics #Discrete mathematics #Exponential function #Recurrence relation #Homogeneous #Sequence (biology) #Claw #Chordal graph #Cubic graph #Graph #Mathematical analysis #Line graph
paper · doi:10.1137/s0895480194274777
openalex publication_date 2002/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
Let Hn be the number of claw-free cubic graphs on 2n labeled nodes. Combinatorial reductions are used to derive a second order, linear homogeneous differential equation with polynomial coefficients whose power series solution is the exponential generating function for Hn. This leads to a recurrence relation for Hn which shows Hn to be P-recursive and which enables the sequence to be computed efficiently. Thus the enumeration of labeled claw-free cubic graphs can be added to the handful of known counting problems for regular graphs with restrictions which have been proved P-recursive.