|
%I #33 Dec 21 2020 07:51:38
%S 0,0,0,0,1,4,24,123,661,3527
%N 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 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 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 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 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 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 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 Technology Review's Puzzle Corner, How many different resistances can be obtained by combining 10 one ohm resistors? Oct 3, 2003.
%H Allan Gottlieb, <a href="https://cs.nyu.edu/~gottlieb/tr/overflow/2003-oct-3-more.html">Oct 3, 2003 addendum (Karnofsky)</a>.
%H 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 .
%e 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 .
%e A A A A A
%e // \ / \ d \ / \ /|
%e // \ /___\ / \ / \ / |
%e o-----o o --- o o-----o o--o--o o--o--o
%e \ / \ / \ / \ / | /
%e \ / \ / \ / \ / |/
%e Z Z Z Z Z
%e .
%e Fig. 1 Fig. 2 Fig. 3 Fig. 4 Fig. 5
%e .
%e Figures 1 to 4 correspond to N1, N2, N4 and N5 in the example section of A338487.
%e .
%Y Cf. A338487, A338999, A339205.
%K nonn,more
%O 1,6
%A _Rainer Rosenthal_, Nov 24 2020
| 