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.

0, 0, 0, 0, 1, 4, 24, 123, 661, 3527

Offset: 1

Author

Rainer Rosenthal, Nov 24 2020

Keywords

• nonn
• more

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.

Examples

			.
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.
.
		

References

• Technology Review's Puzzle Corner, How many different resistances can be obtained by combining 10 one ohm resistors? Oct 3, 2003.

Links

• Allan Gottlieb, Oct 3, 2003 addendum (Karnofsky).
• Joel Karnofsky, Solution of problem from Technology Review's Puzzle Corner Oct 3, 2003, Feb 23 2004.

Crossrefs

Cf. A338487, A338999, A339205.