[seqfan] rooted and weighted cubic graphs

Richard J. Mathar mathar at mpia-hd.mpg.de
Fri Nov 2 12:34:18 CET 2018


For the number of bicolored cubic graphs
(trivalent, connected, undirected, unlabeled graphs without loops, without
multi-edges) on n vertices, where m vertices carry one color
and n-m vertices the other, I get the symmetric array

n=2: 0,0,0
n=4: 1,1,1,1,1
n=6: 2,2,5,5,5,5,2,2
n=8: 5,10,31,46,63,46,31,10,5
n=10: 19,64,248,542,931,1052,931,542,248,64,19

for 0<=m<=n. By the handshake lemma no such graphs exist for odd n.
The first and last entry for each n is A002851, the number
of connected simple cubic graphs. 
[I generated the simple cubic graphs with Meringer's genreg program, generated
the Automorphism group and Cycle Index for each graph, added graphs with
common vertex number, and substituted x_i => 1+x^i to get the generating functions.]
The second column and first subdiagonal is 1,2,10,64,..., the number of rooted
cubic graphs. Is this sequence already in the OEIS, perhaps with an unrelated
description? I doubt it, because there are no known recurrences for A002851.

For the number of signed cubic graphs
(trivalent, connected, undirected, unlabeled graphs without loops, without
multi-edges) on n vertices, where each edge is labeled either + or -,
I get the symmetric array

n=2: 0
n=4: 1,1,2,3,2,1,1
n=6: 2,3,8,16,21,21,16,8,3,2
n=8: 5,14,57,152,313,474,551,474,313,152,57,14,5
n=10: 19,91,491,1806,5034,10604,17318,22033,22033,17318,10604,5034,1806,491,91,19
for 0<=m<=3*n/2

The first and last entry for each n is A002851, the number
of cubic graphs. 
The second column and first subdiagonal is 1,3,14,91.. the number of weighted
cubic graphs where the weight is one more than the number of vertices
(also: the number of edge-rooted cubic graphs). Can anyone confirm these?

For the number of weighted cubic graphs on 4 nodes (the tetrahedron)
with weight w I get A026810(w).
For the number of weighted cubic graphs on 6 nodes
with weight w I get 2, 2, 7, 12, 26, 41, 76, 113, 183, 264, 393, 543, 768, 1024,..
(offset w>=6) with a simple rational o.g.f.
For the number of weighted cubic graphs on 8 nodes
with weight w I get 5, 10, 41, 98, 257, 537, 1131, 2116, 3893, 6665, 11177, 
    17867, 28011, 42419, 63145
(offset w>=8) with a simple rational o.g.f.

Richard



More information about the SeqFan mailing list