Cycle polynomials
HTML articles powered by AMS MathViewer
- by F. K. Hwang PDF
- Proc. Amer. Math. Soc. 83 (1981), 215-219 Request permission
Abstract:
Let $G$ be a graph consisting of $m$ vertex-disjoint cycles with possibly different numbers of vertices on each cycle. We want to count the number of ways of selecting $k$ vertices in $G$ such that there are exactly $l$ edges spanned by these $k$ vertices. For $m = 1$, the problem is equivalent to the Whitworth bracelet problem with two colors and a closed-form solution is known. In this paper we show that the solution for the many-cycle case can be written as a sum of the solutions for single-cycle cases.References
-
D. E. Barton and F. N. David, Runs in a ring, Biometrika 45 (1958), 572-578.
- F. N. David and D. E. Barton, Combinatorial chance, Hafner Publishing Co., New York, 1962. MR 0155371
- F. K. Hwang, Blocking probabilities for a class of spiderweb channel graphs, IEEE Trans. Comm. 28 (1980), no. 1, 115–117. MR 558858, DOI 10.1109/TCOM.1980.1094579
- M. A. Stephens, Whitworth runs on a circle, Ann. Inst. Statist. Math. 29 (1977), no. 2, 287–293. MR 461775, DOI 10.1007/BF02532790 K. Takagi, A generalization of optimal channel graphs in multistage link systems, Japanese Elec. Assoc. SE 77-105 (1978), 39-46. (Japanese) —, A comparison of channel graphs for link system design, Trans. IECE Japan 61 (1978), 538-539. W. A. Whitworth, Choice and chance, Deighton Bell, Cambridge, Mass., 1886.
Additional Information
- © Copyright 1981 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 83 (1981), 215-219
- MSC: Primary 05C30; Secondary 05C38
- DOI: https://doi.org/10.1090/S0002-9939-1981-0620017-X
- MathSciNet review: 620017