|
| |
|
|
A179272
|
|
Sharp upper bound on Rosgen overlap number n-vertex graph with n => 14, formula abused here for nonnegative integers.
|
|
2
|
|
|
|
-1, -2, -1, -1, 1, 2, 5, 7, 11, 14, 19, 23, 29, 34, 41, 47, 55, 62, 71, 79, 89, 98, 109, 119, 131, 142, 155, 167, 181, 194, 209, 223, 239, 254, 271, 287, 305, 322, 341, 359, 379, 398, 419, 439, 461, 482, 505, 527, 551, 574, 599, 623, 649, 674, 701, 727, 755, 782
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
Cranston's abstract: An overlap representation} of a graph G assigns sets to vertices so that vertices are adjacent if and only if their assigned sets intersect with neither containing the other. The overlap number phi(G) (introduced by Rosgen) is the minimum size of the union of the sets in such a representation. We prove the following: (1) An optimal overlap representation of a tree can be produced in linear time, and its size is the number of vertices in the largest subtree in which the neighbor of any leaf has degree 2.
(2) If delta(G) => 2 and G /= K_3, then phi(G) <= |E(G)|-1, with equality when G is connected and triangle-free and has no star-cutset. (3) If G is an n-vertex plane graph with n => 5, then phi(G) <= 2n-5, with equality when every face has length 4 and there is no star-cutset. (4) If G is an n-vertex graph with n => 14, then phi(G) <= floor(n^2/4 - n/2 - 1), and this is sharp (for even n, equality holds when G arises from K_(n/2,n/2) by deleting a perfect matching).
|
|
|
LINKS
|
Daniel W. Cranston, Nitish Korula, Timothy D. LeSaulnier, Kevin Milans, Christopher Stocker, Jennifer Vandenbussche, Douglas B. West, Overlap Number of Graphs, arXiv:1007.0804 [math.CO], Jul 06 2010.
|
|
|
FORMULA
|
a(n) = floor(n^2/4 - n/2 - 1).
a(n) = +2*a(n-1) -2*a(n-3) +a(n-4). G.f.: ( 1-3*x^2+x^3 ) / ( (1+x)*(x-1)^3 ). [R. J. Mathar, Jul 08 2010]
E.g.f.: (3*exp(-x) - (11 + 2*x - 2*x^2)*exp(x))/8.
a(n) = (2*n^2 - 4*n + 3*(-1)^n - 11)/8. (End)
b(n) = a(n-1) = floor ((n^2)/4 - 5/4) defines an even function for the sequence. - Hartmut F. W. Hoft, Nov 02 2016
|
|
|
EXAMPLE
|
a(0) = floor(((0^2)/4) - (0/2) - 1) = floor(0 - 0 - 1) = -1.
a(1) = floor(((1^2)/4) - (1/2) - 1) = floor((1/4) - (1/2) - 1) = floor(-5/4) = -2.
a(2) = floor(((2^2)/4) - (2/2) - 1) = floor(1 - 1 - 1) = -1.
a(3) = floor(((3^2)/4) - (3/2) - 1) = floor(9/4 - 3/2 - 1) = floor(-1/4) = -1.
a(4) = floor(((4^2)/4) - (4/2) - 1) = floor(16/4 - 4/2 - 1) = floor(1) = 1.
a(5) = floor(((5^2)/4) - (5/2) - 1) = floor(16/4 - 5/2 - 1) = floor(11/4) = 2.
a(6) = floor(((6^2)/4) - (6/2) - 1) = floor(36/4 - 6/2 - 1) = floor(5) = 5.
|
|
|
MATHEMATICA
|
Table[Ceiling[n/2] (2 + Ceiling[n/2] - Mod[n, 2]) - 1, {n, -3, 54}]; (* Fred Daniel Kline, Jun 24 2016 *)
CoefficientList[Series[(1 - 3 x^2 + x^3) / ((1 + x) (x - 1)^3), {x, 0, 60}], x] (* Vincenzo Librandi, Nov 07 2016 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
sign,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
