Counting claw-free cubic graphs

被引：10

作者：

Palmer, Edgar M. ^{[1
]}

Read, Ronald C. ^{[2
]}

Robinson, Robert W. ^{[3
]}

机构：

[1] Department of Mathematics, Michigan State University, East Lansing

[2] Dept. of Combinatorics Optimization, Faculty of Mathematics, University of Waterloo, Waterloo

[3] Department of Computer Science, University of Georgia, Athens, GA 30602-7404

来源：

| 2003年 / Society for Industrial and Applied Mathematics Publications卷 / 16期

关键词：

Claw-free graph; Cubic graph; Exponential generating function; Labeled graph counting; P-recursive sequence;

D O I：

10.1137/S0895480194274777

中图分类号：

学科分类号：

摘要：

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.

引用

页码：65 / 73

页数：8

共 17 条

[1]

Chae G., Palmer E.M., Robinson R.W., Computing the number of claw-free cubic graphs with given connectivity

[2]

Chae G., Palmer E.M., Robinson R.W., Computing the number of labeled general cubic graphs

[3]

Char B., Geddes K.O., Gonnet G.H., Monagan M.B., Watt S.M., Maple Reference Manual, 5th Ed., (1988)

[4]

Gessel I.M., Symmetric functions and P-recursiveness, J. Combin. Theory Ser. A, 53, pp. 257-285, (1990)

[5]

Goulden I.P., Jackson D.M., Labelled graphs with small vertex degrees and P-recursiveness, SIAM J. Algebraic Discrete Methods, 7, pp. 60-66, (1986)

[6]

Gropp H., Enumeration of regular graphs 100 years ago, Discrete Math., 101, pp. 73-85, (1992)

[7]

Harary F., Palmer E.M., Graphical enumeration, (1973)

[8]

McKay B.D., Palmer E.M., Read R.C., Robinson R.W., The asymptotic number of claw-free cubic graphs, Discrete Math.

[9]

Plummer M.D., Extending matchings in claw-free graphs, Discrete Math., 125, pp. 301-307, (1994)

[10]

Plummer M.D., 2-extendability in two classes of claw-free graphs, Graph Theory, Combinatorics, and Algorithms, pp. 905-922, (1995)

← 1 2 →