McSorley, John P. Counting structures in the Möbius ladder. (English) Zbl 0957.05057 Discrete Math. 184, No. 1-3, 137-164 (1998). Summary: The Möbius ladder, \(M_n\), is a simple cubic graph on \(2n\) vertices. We present a technique which enables us to count exactly many different structures of \(M_n\), and somewhat unifies counting in \(M_n\). We also provide new combinatorial interpretations of some sequences, and ask some questions concerning extremal properties of cubic graphs. Cited in 6 Documents MSC: 05C30 Enumeration in graph theory 05C35 Extremal problems in graph theory Keywords:Möbius ladder; cubic graph; counting; extremal properties Software:OEIS PDFBibTeX XMLCite \textit{J. P. McSorley}, Discrete Math. 184, No. 1--3, 137--164 (1998; Zbl 0957.05057) Full Text: DOI Online Encyclopedia of Integer Sequences: a(2*n) = 2*a(2*n-1), a(2*n+1) = 2*a(2*n)-1. a(1) = 1, a(2) = 0; for n > 2, a(n) = n*Fibonacci(n-2) (with the convention Fibonacci(0)=0, Fibonacci(1)=1). Number of forests in Moebius ladder M_n. Number of strong edge-subgraphs in Moebius ladder M_n. Number of forests with no isolated vertices in Moebius ladder M_n. Number of single component edge-subgraphs in Moebius ladder M_n. Number of single component forests in Moebius ladder M_n. Number of strong single-component edge-subgraphs in Moebius ladder M_n. Number of spanning trees in a Moebius ladder M_n with 2n vertices. Number of restricted forests in Moebius ladder M_n. a(n) is number of cycles in Moebius ladder M_n. Number of paths in Moebius ladder M_n. Number of (undirected) Hamiltonian paths in n-Moebius ladder. a(n) = ((5+sqrt(5))/2)^n + ((5-sqrt(5))/2)^n. Number of matchings in Moebius ladder M_n. Number of maximum matchings in the n-Moebius ladder M_n. Number of elementary edge-subgraphs in Moebius ladder M_n. Number of strong elementary edge-subgraphs in Moebius ladder M_n. Number of strong restricted edge-subgraphs in Moebius ladder M_n. References: [1] Biggs, N., Algebraic Graph Theory (1993), Cambridge Univ. Press: Cambridge Univ. Press Cambridge [2] Biggs, N. L.; Damerell, R. M.; Sands, D. A., Recursive families of graphs, J. Combin. Theory, Ser. B, 12, 123-131 (1972) · Zbl 0215.05504 [3] Comtet, L., Advanced Combinatorics: The Art of Finite and Infinite Expansions (1974), D. Reidel Publ. Co: D. Reidel Publ. Co Boston [4] Entringer, R. C.; Slater, P. J., On the maximum number of cycles in a graph, Ars Combin., 11, 289-294 (1981) · Zbl 0469.05043 [5] Guy, R. K., Graphs and the strong law of small numbers, (Alavi, Y.; etal., Graph Theory, Combinatorics, and Applications: Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs. Graph Theory, Combinatorics, and Applications: Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs, Western Michigan University (1991), Wiley: Wiley New York), 597-614, 2 vols · Zbl 0841.05095 [6] Harary, F.; Palmer, E. M., Graphical Enumeration (1973), Academic Press: Academic Press New York and London · Zbl 0266.05108 [7] Hosoya, H.; Harary, F., On the matching properties of three fence graphs, J. Math. Chem., 12, 211-218 (1993) [8] Sedlacek, J., On the skeletons of a graph or digraph, (Guy, R. K.; etal., Combinatorial Structures and their Applications (1970), Gordon and Breach: Gordon and Breach New York), 387-391 · Zbl 0247.05142 [9] Sloane, N. J.A.; Plouffe, S., The Encyclopedia of Integer Sequences (1995), Academic Press: Academic Press San Diego · Zbl 0845.11001 [10] Stanley, R. P., (Enumerative Combinatorics, vol. 1 (1986), Wadsworth & Brooks/Cole: Wadsworth & Brooks/Cole California) · Zbl 0608.05001 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.