login
Number of labeled simple graphs covering n vertices with exactly two automorphisms, or with exactly n!/2 graphs obtainable by permuting the vertices.
5

%I #10 Jan 05 2020 12:03:24

%S 0,0,1,3,24,540,13320

%N Number of labeled simple graphs covering n vertices with exactly two automorphisms, or with exactly n!/2 graphs obtainable by permuting the vertices.

%C These are graphs with exactly one involution and no other symmetries.

%H Gus Wiseman, <a href="/A330297/a330297.png">All 9 distinct unlabeled representatives of the a(5) = 540 graphs.</a>

%F a(n) = n!/2 * A330346(n).

%e The a(4) = 24 graphs:

%e {12,13,24} {12,13,14,23}

%e {12,13,34} {12,13,14,24}

%e {12,14,23} {12,13,14,34}

%e {12,14,34} {12,13,23,24}

%e {12,23,34} {12,13,23,34}

%e {12,24,34} {12,14,23,24}

%e {13,14,23} {12,14,24,34}

%e {13,14,24} {12,23,24,34}

%e {13,23,24} {13,14,23,34}

%e {13,24,34} {13,14,24,34}

%e {14,23,24} {13,23,24,34}

%e {14,23,34} {14,23,24,34}

%t graprms[m_]:=Union[Table[Sort[Sort/@(m/.Rule@@@Table[{p[[i]],i},{i,Length[p]}])],{p,Permutations[Union@@m]}]];

%t Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[graprms[#]]==n!/2&]],{n,0,5}]

%Y The non-covering version is A330345.

%Y The unlabeled version is A330346 (not A241454).

%Y Covering simple graphs are A006129.

%Y Covering graphs with exactly one automorphism are A330343.

%Y Graphs with exactly two automorphisms are A330297 (labeled covering), A330344 (unlabeled), A330345 (labeled), and A330346 (unlabeled covering).

%Y Cf. A003400, A006125, A016031, A124059, A143543, A241454, A330098, A330229, A330230, A330231, A330233.

%K nonn,more

%O 0,4

%A _Gus Wiseman_, Dec 12 2019