A208356 Number of labeled star-like graphs on n vertices.

1, 2, 8, 61, 762, 13204, 300155, 8950176

Offset

1,2

Comments

Graph G is called star-like if and only if one of its clique trees forms a star.

The first seven terms published in the Bina Ph.D. thesis.

Links

Table of n, a(n) for n=1..8.

V. Bina, Multidimensional probability distributions: Structure and learning, Ph.D. Thesis. Fac. of Management, University of Economics in Prague (2011)

Prog

# R code
library(igraph)
bits <- function(x, n) { # decodes binary representation of graphs
  list <- NULL
  while (x > 0) {
     list <- c(list, x %% 2)
     x <- x %/% 2
  }
  while (length(list) < n) {list <- c(list, 0)}
  return(list)
}
n<-5 # number of vertices
edges <- choose(n, 2)
models <- 0:(2^edges-1) # all graphs on n vertices
mat <- matrix(rep(0, n^2), ncol=n) #adjacency matrix
nstar <- 0
for (m in models) {
    mat[lower.tri(mat)] <- bits(m, hran)
    l <- maximal.cliques(graph.adjacency(mat, mode="lower"))
    aux <- factor(unlist(l))
    l <- lapply(l, setdiff, levels(aux)[tabulate(aux) == 1])
    l <- lapply(l, setdiff, l[[which.max(unlist(lapply(l, length)))]])
    if (sum(unlist(lapply(l, length))) < 1) nstar <- nstar + 1
}
nstar

Crossrefs

Cf. A179534, A006125, A058862 (sub- and superclasses)

Sequence in context: A188324 A368450 A370913 * A188489 A085657 A005215

Adjacent sequences: A208353 A208354 A208355 * A208357 A208358 A208359

Keyword

nonn

Author

Vladislav Bina, Feb 25 2012

Status

approved