login
Number of labeled star-like graphs on n vertices.
0

%I #12 Jan 04 2019 04:50:52

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

%N Number of labeled star-like graphs on n vertices.

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

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

%H V. Bina, <a href="https://insis.vse.cz/zp/index.pl?prehled=vyhledavani;podrobnosti_zp=32066;zp=32066;dinfo_jazyk=3">Multidimensional probability distributions: Structure and learning</a>, Ph.D. Thesis. Fac. of Management, University of Economics in Prague (2011)

%o # R code

%o library(igraph)

%o bits <- function(x, n) { # decodes binary representation of graphs

%o list <- NULL

%o while (x > 0) {

%o list <- c(list, x %% 2)

%o x <- x %/% 2

%o }

%o while (length(list) < n) {list <- c(list,0)}

%o return(list)

%o }

%o n<-5 # number of vertices

%o edges <- choose(n,2)

%o models <- 0:(2^edges-1) # all graphs on n vertices

%o mat <- matrix(rep(0,n^2),ncol=n) #adjacency matrix

%o nstar <- 0

%o for (m in models) {

%o mat[lower.tri(mat)] <- bits(m,hran)

%o l <- maximal.cliques(graph.adjacency(mat,mode="lower"))

%o aux <- factor(unlist(l))

%o l <- lapply(l,setdiff, levels(aux)[tabulate(aux) == 1])

%o l <- lapply(l,setdiff,l[[which.max(unlist(lapply(l,length)))]])

%o if (sum(unlist(lapply(l,length))) < 1) nstar <- nstar + 1

%o }

%o nstar

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

%K nonn

%O 1,2

%A _Vladislav Bina_, Feb 25 2012