scientific article; zbMATH DE number 4095501

From MaRDI portal
Publication:3822192





An enumeration problem for bicyclic graphs is considered. The bicyclic graph is defined as a connected and unlabeled graph having exactly two adjacent cycles with one node in common. The main results are the following. Theorem 2.1. Let \(U_{m,n}^{(x)}\) be the counting series of bicyclic graphs having cycles of lengths \(m\) and \(n\) with \(m/n\). Then \((1- T(x))U_{m,n}(x)=Z[\Gamma_{m,n},T(x)]\), where the cycle index corresponding to the permutation group \(\Gamma_{m,n}\) is given by \[ Z(\Gamma_{m,n}) = \frac14 \begin{cases} S_1^{m+n-1} + S_1^{n+1} S_2^{(m-2)/2} + S_1^{m+1} S_2^{(n-2)/2} + S_1^3 S_2^{(m+n-4)/2}, &\text{\(m,n\) both even,} \\ S_1^{m+n-1} + S_1^{n} S_2^{(m-1)/2} + S_1^{m+1} S_2^{(n-2)/2} + S_1^2 S_2^{(m+n-3)/2}, &\text{\(m\) odd, \(n\) even,} \\ S_1^{m+n-1} + S_1^{n} S_2^{(m-1)/2} + S_1^{m} S_2^{(n-1)/2} + S_1 S_2^{(m+n-2)/2}, &\text{\(m,n\) odd,} \end{cases} \] \(T(x)=x+x^ 2+2x^ 3+4x^ 4+\ldots\), \(S_1\) and \(S_2\) are indeterminates, is the counting series for rooted trees. Theorem 2.2. The counting series \(V_ m(x)\) for bicyclic graphs having exactly two cycles of length \(m\) is given by \[ \begin{multlined} 4(1-T(x))(1-T(x^2)) V_ m(x) = \\ \begin{cases} (1-T(x^2))[T^{2m-1}(2) + T(x)T^{m-1}(x^2)] + 2(1-T(x))[T(x)+T(x^2)] T^{m-1}(x^2),&\text{\(m\) odd,} \\ (1-T(x^2))[T^{2m-1}(2) + T^3(x)T^{m-2}(x^2)] + 2(1-T(x))[T(x)+T(x^2)] T^{m-1}(x),&\text{\(m\) even,} \end{cases} \end{multlined} \]











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3822192)