login
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.
1
0, 0, 0, 0, 1, 4, 24, 123, 661, 3527
OFFSET
1,6
COMMENTS
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.
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.
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).
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.
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.
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.
REFERENCES
Technology Review's Puzzle Corner, How many different resistances can be obtained by combining 10 one ohm resistors? Oct 3, 2003.
EXAMPLE
.
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.
.
A A A A A
// \ / \ d \ / \ /|
// \ /___\ / \ / \ / |
o-----o o --- o o-----o o--o--o o--o--o
\ / \ / \ / \ / | /
\ / \ / \ / \ / |/
Z Z Z Z Z
.
Fig. 1 Fig. 2 Fig. 3 Fig. 4 Fig. 5
.
Figures 1 to 4 correspond to N1, N2, N4 and N5 in the example section of A338487.
.
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Rainer Rosenthal, Nov 24 2020
STATUS
approved