|
|
A357779
|
|
Maximum number of edges in a 6-degenerate graph with n vertices.
|
|
2
|
|
|
0, 1, 3, 6, 10, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 75, 81, 87, 93, 99, 105, 111, 117, 123, 129, 135, 141, 147, 153, 159, 165, 171, 177, 183, 189, 195, 201, 207, 213, 219, 225, 231, 237, 243, 249, 255, 261, 267, 273, 279
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
A maximal 6-degenerate graph can be constructed from a 6-clique by iteratively adding a new 6-leaf (vertex of degree 6) adjacent to six existing vertices.
This is also the number of edges in a 6-tree with n>6 vertices. (In a 6-tree, the neighbors of a newly added vertex must form a clique.)
|
|
REFERENCES
|
Allan Bickle, Fundamentals of Graph Theory, AMS (2020).
J. Mitchem, Maximal k-degenerate graphs, Util. Math. 11 (1977), 101-106.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = C(n,2) for n < 8.
a(n) = 6*n-21 for n > 5.
|
|
EXAMPLE
|
For n < 8, the only maximal 6-degenerate graph is complete.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|