cp's OEIS Frontend

A339123 Number of 2-connected multigraphs with n edges and rooted at two indistinguishable vertices and have no decomposition into parallel components rooted at the two distinguished vertices.

%I A339123 #33 Dec 21 2020 07:51:38
%S A339123 0,0,0,0,1,4,24,123,661,3527
%N A339123 Number of 2-connected multigraphs with n edges and rooted at two indistinguishable vertices and have no decomposition into parallel components rooted at the two distinguished vertices.
%C A339123 Connected multigraphs rooted at vertices A and Z can be considered as resistor networks with 1-ohm-resistors per edge and total resistance measured between A and Z.
%C A339123 The networks counted here are a subset of the networks counted by A338999. Due to the 3-connectedness with respect to the two distinguished vertices none of these resistor networks is a parallel combination.
%C A339123 For a resistor network to be effective, one has to avoid dead ends. A dead end is a subgraph which becomes isolated from the distinguished vertices by the removal of one of its vertices. Since the multigraph is 2-connected, there are no dead ends. Another consequence of the 2-connectedness is, that the resistor network is not a series combination (like Fig. 5 in the example).
%C A339123 Karnofsky states in the addendum: "A graph has no dangling parts that don't affect the effective resistance if and only if it is 2-connected. A new idea is that the essential graphs to generate are 2-connected ones with minimal order (edges per node) 3". In this sequence there is no restriction w.r.t. the degree.
%C A339123 So the networks with n resistors counted by a(n) are neither parallel nor serial combinations, but they form networks which Karnofsky described as "h-graphs" (see A338487). The number of different resistance values is the same as for the respective networks in A338487.
%C A339123 Let us write Net = (E,V,A,Z) to denote the network consisting of E = set of edges, V = set of vertices, A and Z the distinguished vertices in V. Two networks (E1,V1,A1,Z1) and (E2,V2,A2,Z2) are counted only once, if there exists a bijection b: V1 -> V2 which sends E1 to E2 and {A1,Z1} to {A2,Z2}. Thus symmetrical networks w.r.t. A and Z are counted only once.
%D A339123 Technology Review's Puzzle Corner, How many different resistances can be obtained by combining 10 one ohm resistors? Oct 3, 2003.
%H A339123 Allan Gottlieb, <a href="https://cs.nyu.edu/~gottlieb/tr/overflow/2003-oct-3-more.html">Oct 3, 2003 addendum (Karnofsky)</a>.
%H A339123 Joel Karnofsky, <a href="http://cs.nyu.edu/~gottlieb/tr/overflow/2003-dec-2.pdf">Solution of problem from Technology Review's Puzzle Corner Oct 3, 2003</a>, Feb 23 2004.
%e A339123 .
%e A339123 a(6) = 4, because the last of these 5 networks (Fig. 5) is not 2-connected: when the middle vertex is removed, then A and Z are part of two separated subgraphs.
%e A339123 .
%e A339123           A              A              A              A              A
%e A339123         // \            / \            d \            / \            /|
%e A339123        //   \          /___\          /   \          /   \          / |
%e A339123        o-----o        o --- o        o-----o        o--o--o        o--o--o
%e A339123         \   /          \   /          \   /          \   /            | /
%e A339123          \ /            \ /            \ /            \ /             |/
%e A339123           Z              Z              Z              Z              Z
%e A339123 .
%e A339123        Fig. 1         Fig. 2         Fig. 3         Fig. 4         Fig. 5
%e A339123 .
%e A339123 Figures 1 to 4 correspond to N1, N2, N4 and N5 in the example section of A338487.
%e A339123 .
%Y A339123 Cf. A338487, A338999, A339205.
%K A339123 nonn,more
%O A339123 1,6
%A A339123 _Rainer Rosenthal_, Nov 24 2020