|
|
A309379
|
|
Number of unordered pairs of 4-colorings of an n-wheel that differ in the coloring of exactly one vertex.
|
|
2
|
|
|
36, 0, 108, 120, 444, 840, 2124, 4536, 10332, 22440, 49260, 106392, 229500, 491400, 1048716, 2228088, 4718748, 9961320, 20971692, 44040024, 92274876, 192937800, 402653388, 838860600, 1744830684, 3623878440, 7516193004, 15569256216, 32212254972, 66571992840
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
3,1
|
|
COMMENTS
|
Please refer to the Wikipedia page on n-wheel graphs linked here; an n-wheel graph has n-1 peripheral nodes and one central node, thus having n total nodes.
|
|
LINKS
|
Prateek Bhakta, Benjamin Brett Buckner, Lauren Farquhar, Vikram Kamat, Sara Krehbiel, Heather M. Russell, Cut-Colorings in Coloring Graphs, Graphs and Combinatorics, (2019) 35(1), 239-248.
|
|
FORMULA
|
G.f.: 12*x^3*(3 - 9*x + 6*x^2 + 4*x^3 - 2*x^4)/((1 - x)*(1 + x)^2*(1 - 2*x)^2). - Andrew Howroyd, Aug 27 2019
|
|
EXAMPLE
|
Case n=4: The 4-wheel graph is isomorphic to the complete graph on 4 vertices. Each vertex must be colored differently and it is not possible to change the color of just one vertex and still leave a valid coloring, so a(4) = 0.
Case n=5: The peripheral nodes can colored using one of the patterns 1212, 1213 or 1232. In the case of 1212, colors can be selected in 24 ways and any vertex including the center vertex can be flipped to the unused color giving 24*5 = 120. In the case of 1213 or 1232, colors can be selected in 24 ways and two vertices can have a color change giving 24*2*2 = 96. Since we are counting unordered pairs, a(5) = (120 + 96)/2 = 108.
(End)
|
|
PROG
|
(PARI) Vec(12*(3 - 9*x + 6*x^2 + 4*x^3 - 2*x^4)/((1 - x)*(1 + x)^2*(1 - 2*x)^2) + O(x^30)) \\ Andrew Howroyd, Aug 27 2019
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|