The generating function of Whitworth runs |
| |
Authors: | CJ Liu |
| |
Institution: | Department of Mathematics, Statistics and Computer Science, Marquette University, Milwaukee, WI 53233, U.S.A. |
| |
Abstract: | Let G be a graph. The number of ways of selecting k vertices in G such that the subgraph induced by the k selected vertices containing l edges may be considered as Whitworth runs. For two arbitrary graphs G1 and G2 we show that the generating function of G1 can be written as a sum of the generating function of G2. As an application we derive a difference equation satisfied by the generating function of a line graph and that of a cycle graph. Two independent solutions in the closed-form are found. One is equivalent to the Whitworth bracelet problem with two colors. Furthermore, a line and a cycle graph and a two-line graph have been studied. We show that all solutions can be written as a sum of the solutions for single-line cases. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|