A291297 -id:A291297 - cp's OEIS frontend

A291742 Number of maximal independent vertex sets in the n-Fibonacci cube graph.

2, 2, 3, 7, 22, 123, 2281, 221074, 300492228

Offset: 1

Andrew Howroyd, Aug 30 2017

The size of the smallest set, the independent domination number, is given by A291297.

			Case n=1: The vertices are 0, 1. Each singleton vertex set is a maximal independent set, so a(1) = 2.
Case n=2: The vertices are 00, 01, 10. Maximal independent sets are {00} and {01, 10}, so a(2) = 2.
Case n=3: The vertices are 000, 001, 010, 100, 101. Maximal independent sets are {000, 101}, {010, 101}, {001, 010, 100}, so a(3)=3.

Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
Eric Weisstein's World of Mathematics, Fibonacci Cube Graph
Wikipedia, Fibonacci cube

Cf. A291297, A291573.

from itertools import combinations, product
from networkx import empty_graph, find_cliques
def A291742(n):
    v = tuple(int(q,2) for q in (''.join(p) for p in product('01',repeat=n)) if '11' not in q)
    G = empty_graph(v)
    e = tuple((a,b) for a, b in combinations(v,2) if (lambda m: (m&-m)^m if m else 1)(a^b))
    G.add_edges_from(e)
    return sum(1 for c in find_cliques(G)) # Chai Wah Wu, Jan 14 2024

a(9) from Pontus von Brömssen, Mar 06 2020

A321684 Independent domination number of the n X n grid graph.

Original entry on oeis.org

0, 1, 2, 3, 4, 7, 10, 12, 16, 21, 24, 30, 35, 40, 47, 53, 60, 68, 76, 84, 92, 101, 111, 121, 131, 141, 152, 164, 176, 188, 200, 213, 227, 241, 255, 269, 284, 300, 316, 332, 348, 365, 383, 401, 419, 437, 456, 476, 496, 516, 536, 557, 579, 601, 623, 645, 668

Offset: 0

Andrey Zabolotskiy, Jan 14 2019

Colin Barker, Table of n, a(n) for n = 0..1000
Simon Crevals, Patric R. J. Östergård, Independent domination of grids, Discrete Math., 338 (2015), 1379-1384.
Index entries for linear recurrences with constant coefficients, signature (2,-1,0,0,1,-2,1).

Cf. A104519, A075324, A299029, A279404, A291297.

ogf := (-41*x^6 + 47*x^5 - x^3 - x^2 + 41*x - 47)/((x - 1)^3*(x^4 + x^3 + x^2 + x + 1)): ser := series(ogf, x, 44):
(0,1,2,3,4,7,10,12,16,21,24,30,35,40), seq(coeff(ser, x, n), n=0..42); # Peter Luschny, Jan 14 2019

concat(0, Vec(x*(1 + 2*x^4 - x^5 - x^6 + 2*x^7 + x^8 - 4*x^9 + 3*x^10 - 2*x^12 + x^13 + x^14 - 2*x^15 + 2*x^16 - 2*x^18 + x^19) / ((1 - x)^3*(1 + x + x^2 + x^3 + x^4)) + O(x^40))) \\ Colin Barker, Jan 14 2019

For n >= 14, a(n) = floor((n+2)^2 / 5 - 4).
a(n) = A104519(n+2), the domination number of the n X n grid graph, for all n except for n = 9, 11.
From Colin Barker, Jan 14 2019: (Start)
G.f.: x*(1 + 2*x^4 - x^5 - x^6 + 2*x^7 + x^8 - 4*x^9 + 3*x^10 - 2*x^12 + x^13 + x^14 - 2*x^15 + 2*x^16 - 2*x^18 + x^19) / ((1 - x)^3*(1 + x + x^2 + x^3 + x^4)).
a(n) = 2*a(n-1) - a(n-2) + a(n-5) - 2*a(n-6) + a(n-7) for n > 20.
(End)

A291298 Connected domination number of Fibonacci cube Gamma_n.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 10, 14, 22

Offset: 1

N. J. A. Sloane, Aug 30 2017

Jernej Azarija, S. Klavzar, Y. Rho, S. Sim, On domination-type invariants of Fibonacci cubes and hypercubes, Preprint 2016; See Table 3.
Jernej Azarija, S. Klavzar, Y. Rho, S. Sim, On domination-type invariants of Fibonacci cubes and hypercubes, Ars Mathematica Contemporanea, 14 (2018) 387-395. See Table 3.
Eric Weisstein's World of Mathematics, Connected Domination Number.
Eric Weisstein's World of Mathematics, Fibonacci Cube Graph.

Cf. A291294, A291295, A291296, A291297, A291299, A291300, A298115.

cp's OEIS Frontend

A291742 Number of maximal independent vertex sets in the n-Fibonacci cube graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Extensions

A321684 Independent domination number of the n X n grid graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

A291298 Connected domination number of Fibonacci cube Gamma_n.

Views

Author

Keywords

Links

Crossrefs