The "square root" of a graph?

Question

The number $f(n)$ of graphs on the vertex set $\{1,\dots,n\}$, allowing loops but not multiple edges, is $2^{{n+1\choose 2}}$, with exponential generating function $F(x)=\sum_{n\geq 0} 2^{{n+1\choose 2}}\frac{x^n}{n!}$. Consider $$ \sqrt{F(x)} = 1+x+3\frac{x^2}{2!}+23\frac{x^3}{3!} +393\frac{x^4}{4!}+13729\frac{x^5}{5!}+\cdots. $$ It's not hard to see that the coefficients 1,1,3,23,393,13729,$\dots$ are positive integers. This is A178315 in OEIS. Do they have a combinatorial interpretation?

More generally, we can replace $2^{{n+1\choose 2}}$ with $\sum_G t_1^{c_1(G)} t_2^{c_2(G)}\cdots$, where $G$ ranges over the same graphs on $\{1,\dots,n\}$, and where $c_i(G)$ is the number of connected components of $G$ with $i$ vertices. Now we will get polynomials in the $t_i$'s with positive integer coefficients, the first four being $$ t_1 $$ $$ t_1^2+2t_2 $$ $$ t_1^3+6t_1t_2+16t_3 $$ $$ t_1^4+12t_1^2t_2+64t_1t_3+12t_2^2+304t_4. $$ Again we can ask for a combinatorial interpretation of the coefficients.

Note. What happens if we don't allow loops, so we are looking at $\sqrt{\sum_{n\geq 0}2^{{n\choose 2}}\frac{x^n}{n!}}$? Now the coefficient of $\frac{x^n}{n!}$ is equal to the coefficient of $\frac{x^n}{n!}$ in $\sqrt{F(x)}$, divided by $2^n$, which in general is not an integer. Hence it makes more sense combinatorially to allow loops.

Answer 1

There is a fixed-point-free involution on these graphs which I will call loop-switching, given by adding a loop to every vertex that doesn't have one while simultaneously deleting the loops from all vertices that do. Then $\sqrt{F(x)}$ counts equivalence classes of graphs, where two graphs are in the same class if one can be obtained from the other by loop-switching a subset of its connected components. This follows from $\sqrt{F(x)} = \exp \frac{\log F(x)}{2}$ where $\log F(x)$ counts connected graphs and clearly on those the equivalence classes have size exactly 2. This also nicely explains why allowing loops is important here, and should work the same way in the multivariate version.

I guess to turn this into a "proper" combinatorial interpretation of $\sqrt{F(x)}$ as counting some class of structures of which a graph is formed from exactly two, one could somehow choose a canonical representative of each equivalence class on connected graphs. It seems like there is no good way to do this, however, since in some of those classes the two graphs are isomorphic.

Answer 2

These numbers count balanced signed graphs (without loops). A signed graph is a graph in which every edge has a sign, either positive or negative. It is balanced if every cycle has an even number of negative edges.

We will use the following lemma of Harary [Frank Harary, On the notion of balance of a signed graph, Michigan Math. J. 2 (1953/54), 143–146 (1955), Theorem 3]. I'll omit the proof, which is not difficult.

A signed graph is balanced if and only if it is possible to color the vertices in black and white so that every positive edge joins two vertices of the same color and every negative edge joins two vertices of opposite colors.

I'll call these colored graphs bicolored balanced signed graphs. It is easy to see that every connected bicolored balanced signed graph corresponds to exactly two balanced signed graphs

The number of bicolored balanced signed graphs on $[n]:=\{1,2,\dots,n\}$ is $2^{\binom{n+1}2}=2^n\cdot 2^{\binom n2}$. To see this, we construct all bicolored balanced signed graphs on $[n]$ in the following way: We start with an arbitrary graph on $[n]$. Then we color the vertices arbitrarily in black and white. Finally we make edges between vertices of the same color positive edges and we make edges between vertices of opposite colors negative edges. There are $2^{\binom n2}$ graphs on $[n]$ and $2^n$ ways of coloring the vertices of each graph in black and white, so there are $2^n\cdot 2^{\binom n2}$ bicolored balanced signed graphs.

The exponential generating function for bicolored balanced signed graphs is thus $F(x)$. So by the exponential formula, the exponential generating function for connected bicolored balanced signed graphs is $\log F(x)$. Since each connected balanced signed graph has two colorings, the exponential generating function for connected balanced signed graphs is $\tfrac12\log F(x)$, and by the exponential formula again, the exponential generating function for balanced sign graphs is $\sqrt{F(x)}$.

The same approach shows that the polynomials in the $t_i$ count balanced signed graphs where each component with $i$ vertices is weighted $t_i$.

It is curious that the enumeration of unlabeled balanced signed graphs was accomplished by Harary and Palmer in 1967 [F. Harary and E. M. Palmer, On the number of balanced signed graphs, Bulletin of Mathematical Biophysics 29 (1967), 759–765] but the considerably easier enumeration of labeled balanced signed graphs did not appear, as far as I know, until much later [F. Ardila, F. Castillo, Federico, and M. Henley, The arithmetic Tutte polynomials of the classical root systems, Int. Math. Res. Not. IMRN 2015, no. 12, 3830–3877].

There is another interpretation for the coefficients of $\sqrt{F(x)}$ which is less natural but easier to see: they count graphs on $[n]$ with loops allowed in which the least vertex in each component has a loop.