Jernej Azarija - cp's OEIS frontend

A247181 Total domination number of the n-hypercube graph.

2, 2, 4, 4, 8, 14, 24, 32, 64, 124

Offset: 1

Jernej Azarija, Nov 22 2014

a(n) = size of smallest subset S of vertices of the n-cube Q_n such that every vertex of Q_n has a neighbor in S.

Proof for first formula can be found in the Verstraten link. - Kamiel P.F. Verstraten, Jun 10 2015

			a(1) = 2 since the complete graph on two vertices can only be totally dominated by taking both vertices.

J. Azarija, M. A. Henning and S. Klavžar (Total) Domination in Prisms, arXiv:1606.08143 [math.CO], 2016.
Jernej Azarija, S. Klavzar, Y. Rho, and S. Sim, On domination-type invariants of Fibonacci cubes and hypercubes, Preprint 2016; See Table 4.
Jernej Azarija, S. Klavzar, Y. Rho, and S. Sim, On domination-type invariants of Fibonacci cubes and hypercubes, Ars Mathematica Contemporanea, 14 (2018) 387-395. See Table 4.
M. Henning and A. Yeo, Total domination in graphs, Springer, 2013.
Kamiel P. F. Verstraten, A Generalization of the Football Pool Problem, Master's Thesis, Tilburg University, 2014.
Eric Weisstein's World of Mathematics, Hypercube Graph
Eric Weisstein's World of Mathematics, Total Domination Number

Cf. A000983 (half), A323515 (number of sets).

a(n) = 2*A000983(n-1), at least if 2<=n<=9. - Omar E. Pol, Nov 22 2014. This formula is true for all n>=2 (see Azarija-Henning-Klavžar paper). - Omar E. Pol, Jul 01 2016

a(n) = A230014(n,1), at least if 1<=n<=9. - Omar E. Pol, Nov 23 2014. This formula is true for all n>=1 (in accordance with the above comment). - Omar E. Pol, Jul 01 2016

a(10) from Jernej Azarija, Jun 30 2016

A245762 Maximal number of edges in a C_4 free subgraph of the n-cube.

Original entry on oeis.org

1, 3, 9, 24, 56, 132

Offset: 1

Jernej Azarija, Jul 31 2014

This is related to the famous conjecture of Erdős (see Erdős link).

			a(2) = 3 since the 2-cube is the 4-cycle and one needs to remove a single edge to get rid of all 4-cycles.

M. R. Emamy, K. P. Guan and I. J. Dejter, On fault tolerance in a 5-cube. Preprint.
H. Harborth and H. Nienborg, Maximum number of edges in a six-cube without four-cycles, Bulletin of the ICA 12 (1994) 55-60

Thomas Bloom, Subgraphs of the cube without a 2k-cycle, Erdős Problems.
P. Brass, H. Harborth and H. Nienborg, On the maximum number of edges in a c4-free subgraph of qn, J. Graph Theory 19 (1995) 17-23
F. R. K. Chung, Subgraphs of a hypercube containing no small even cycles, J. Graph Theory 16 (1992) 273-286
Manfred Scheucher and Paul Tabatabai, Python Script

a(6) from Manfred Scheucher and Paul Tabatabai, Jul 23 2015

A236525 Number of simple non-bipartite graphs on n nodes.

Original entry on oeis.org

0, 0, 1, 4, 21, 121, 956, 12043, 273549, 11999689, 1018965561, 165090921457, 50502028840240, 29054155623249635, 31426485969192461828, 64001015704512693244004, 245935864153532444460997784, 1787577725145611678835828915650, 24637809253125004523074706811821299

Offset: 1

Jernej Azarija, Jan 29 2014

nonn

			a(3) = 1 since the only non-bipartite graph on 3 vertices is the triangle.

Andrew Howroyd, Table of n, a(n) for n = 1..50

Cf. A000088, A033995.

def a(n): return len([G for G in graphs(n) if not G.is_bipartite()])

a(n) = A000088(n) - A033995(n).

More terms from Joerg Arndt, Feb 01 2014

A182290 Maximal number of connected graphs of order n having distinct numbers of spanning trees.

Original entry on oeis.org

1, 1, 2, 5, 16, 65, 386, 3700, 55784, 1134526, 27053464

Offset: 1

Jernej Azarija, Jun 27 2012

a(n) grows asymptotically faster than sqrt(n)*exp(2*Pi*sqrt(n/log(n))/sqrt(3)).

			a(3) = 2 since any connected graph on 3 vertices can either have 1 spanning tree (any tree) or 3 (triangle).

Jernej Azarija, Counting graphs with different numbers of spanning trees through the counting of prime partitions (preprint, 2012).
Jernej Azarija, Maximal class of simple graphs of order n with mutually distinct number of spanning trees, (Mathoverflow).
J. Sedlacek, On the number of spanning trees of finite graphs, Cas. Pro. Pest Mat., Vol. 94 (1969) 217-221.

# needs the package nauty:
len( set([g.spanning_trees_count() for g in graphs.nauty_geng('-c ' + str(n)) ]))

a(11) from Jernej Azarija, Sep 07 2012

A182258 Least number k such that there exists a simple graph on k vertices having precisely n spanning trees.

Original entry on oeis.org

3, 4, 5, 6, 7, 4, 5, 10, 5, 5, 13, 6, 6, 4, 7, 8, 7, 5, 5, 22, 8, 5, 9, 8, 7, 6, 6, 6, 9, 6, 7, 10, 6, 6, 7, 10, 7, 5, 7, 8, 7, 7, 5, 7, 11, 6, 7, 7, 7, 6, 8, 6, 6, 6, 8, 8, 8, 6, 6, 9, 7, 6, 8, 6, 8, 7, 6, 8, 9, 7, 7, 9, 5, 7, 9, 9, 7, 7, 6

Offset: 3

Jernej Azarija, Apr 21 2012

nonn

The only fixed points for a(n) are 3, 4, 5, 6, 7, 10, 13, 22.
If n > 25 and n != 2 (mod 3) then a(n) <= (n+9)/4.
If n > 5 and n = 2 (mod 3) then a(n) <= (n+4)/3. [corrected by Jukka Kohonen, Feb 16 2022]
It is conjectured that a(n) = o(log(n)).
a(mn) <= a(m)+a(n)-1, by joining two graphs with m and n spanning trees at a single common vertex. - Jukka Kohonen, Feb 17 2022

			a(100000000) = 10 since K_10 has 100000000 spanning trees.
From _Jukka Kohonen_, Feb 17 2022: (Start)
a(47) = 11 since the following graph has 47 spanning trees:
    o-o-o-o
   /       \
  o--o---o--o
   \       /
    o--o--o
(End)

Jukka Kohonen, Table of n, a(n) for n = 3..10000
Jernej Azarija, MathOverflow: Minimal graphs with a prescribed number of spanning trees
Jernej Azarija and Riste Škrekovski, Euler's idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees, Mathematica Bohemica, Vol. 138 (2013), No. 2, 121--131.
Dick Lipton, The Inverse Spanning Tree Problem
Ladislav Nebeský, On the minimum number of vertices and edges in a graph with a given number of spanning trees, Časopis pro pěstování matematiky 98 (1973), 95-97.
J. Sedláček, On the minimal graph with a given number of spanning trees, Canad. Math. Bull. 13 (1970) 515-517.

a(14)-a(46) from Jukka Kohonen, Feb 16 2022

a(47)-a(81) from Jukka Kohonen, Feb 17 2022

cp's OEIS Frontend

User: Jernej Azarija

A247181 Total domination number of the n-hypercube graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A245762 Maximal number of edges in a C_4 free subgraph of the n-cube.

Views

Author

Keywords

Comments

Examples

References

Links

Extensions

A236525 Number of simple non-bipartite graphs on n nodes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Sage

Formula

Extensions

A182290 Maximal number of connected graphs of order n having distinct numbers of spanning trees.

Views

Author

Keywords

Comments

Examples

Links

Programs

Sage

Extensions

A182258 Least number k such that there exists a simple graph on k vertices having precisely n spanning trees.

Views

Author

Keywords

Comments

Examples

Links

Extensions