cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-4 of 4 results.

A357357 Length of the longest induced cycle in the n X n grid graph.

Original entry on oeis.org

0, 4, 8, 12, 16, 20, 32, 40, 50, 62, 76, 90, 104, 120, 140, 160, 180
Offset: 1

Views

Author

Pontus von Brömssen, Sep 25 2022

Keywords

Examples

			For 2 <= n <= 6, a longest induced cycle is the one going around the border of the grid, so a(n) = 4*(n-1).
Longest induced cycles for 6 <= n <= 8:
  X X X X X X   X X X X X X X   X X X X X X X X
  X . . . . X   X . . . . . X   X . . . . . . X
  X . . . . X   X . X X X . X   X . X X X . X X
  X . . . . X   X . X . X . X   X . X . X . X .
  X . . . . X   X . X . X . X   X . X . X . X X
  X X X X X X   X . X . X . X   X . X . X . . X
                X X X . X X X   X . X . X . . X
                                X X X . X X X X

Links

Crossrefs

Main diagonal of A360915.
Cf. A000937, A297664, A331968, A357358, A360914 (number of longest induced cycles).

Formula

a(n) <= A331968(n)+1.
a(n) = 2*n^2/3 + O(n) (Beluhov 2023). - Pontus von Brömssen, Jan 30 2023

Extensions

a(9)-a(12) from Elijah Beregovsky, Nov 24 2022
a(13) from Elijah Beregovsky, Nov 25 2022
a(14)-a(17) from Andrew Howroyd, Feb 26 2023

A360913 Array read by antidiagonals: T(m,n) is the number of maximum induced cycles in the grid graph P_m X P_n.

Original entry on oeis.org

1, 2, 2, 3, 1, 3, 4, 1, 1, 4, 5, 1, 7, 1, 5, 6, 1, 17, 17, 1, 6, 7, 1, 31, 90, 31, 1, 7, 8, 1, 8, 284, 284, 8, 1, 8, 9, 1, 40, 9, 1398, 9, 40, 1, 9, 10, 1, 120, 163, 10, 10, 163, 120, 1, 10, 11, 1, 8, 1329, 382, 23, 382, 1329, 8, 1, 11, 12, 1, 64, 128, 6098, 190, 190, 6098, 128, 64, 1, 12
Offset: 2

Views

Author

Andrew Howroyd, Feb 26 2023

Keywords

Comments

A maximum induced cycle is an induced cycle of longest length.

Examples

			Array begins:
=========================================
m\n| 2  3   4    5    6   7    8    9 ...
---+-------------------------------------
2  | 1  2   3    4    5   6    7    8 ...
3  | 2  1   1    1    1   1    1    1 ...
4  | 3  1   7   17   31   8   40  120 ...
5  | 4  1  17   90  284   9  163 1329 ...
6  | 5  1  31  284 1398  10  382 6098 ...
7  | 6  1   8    9   10  23  190  388 ...
8  | 7  1  40  163  382 190 2100   80 ...
9  | 8  1 120 1329 6098 388   80 6840 ...
  ...

Links

  • Eric Weisstein's World of Mathematics, Grid Graph.

Crossrefs

Main diagonal is A360914.
Cf. A360196 (induced cycles), A360915 (lengths), A360916, A360918.

Formula

T(m,n) = T(n,m).

A360917 Array read by antidiagonals: T(m,n) is the number of vertices in the longest induced path in the grid graph P_m X P_n.

Original entry on oeis.org

1, 2, 2, 3, 3, 3, 4, 5, 5, 4, 5, 6, 7, 6, 5, 6, 8, 9, 9, 8, 6, 7, 9, 11, 11, 11, 9, 7, 8, 11, 14, 14, 14, 14, 11, 8, 9, 12, 16, 17, 17, 17, 16, 12, 9, 10, 14, 18, 20, 21, 21, 20, 18, 14, 10, 11, 15, 20, 22, 24, 24, 24, 22, 20, 15, 11, 12, 17, 22, 25, 27, 29, 29, 27, 25, 22, 17, 12
Offset: 1

Views

Author

Andrew Howroyd, Feb 26 2023

Keywords

Comments

Equivalently, T(m,n) is the maximum number of unit squares of a snake-like polyomino in an m X n rectangle.

Examples

			Array begins:
==============================================
  m\n|  1  2  3  4  5  6  7  8  9 10 11 12 ...
-----+----------------------------------------
   1 |  1  2  3  4  5  6  7  8  9 10 11 12 ...
   2 |  2  3  5  6  8  9 11 12 14 15 17 18 ...
   3 |  3  5  7  9 11 14 16 18 20 22 24 26 ...
   4 |  4  6  9 11 14 17 20 22 25 28 30 33 ...
   5 |  5  8 11 14 17 21 24 27 30 34 37 40 ...
   6 |  6  9 14 17 21 24 29 32 36 40 44 47 ...
   7 |  7 11 16 20 24 29 33 38 42 46 50 55 ...
   8 |  8 12 18 22 27 32 38 42 48 52 57 62 ...
   9 |  9 14 20 25 30 36 42 48 53 58 64 70 ...
  10 | 10 15 22 28 34 40 46 52 58 64 71 77 ...
  11 | 11 17 24 30 37 44 50 57 64 71 77 86 ...
  12 | 12 18 26 33 40 47 55 62 70 77 86 92 ...
  ...

Links

Crossrefs

Main diagonal is A331968.
Cf. A360199, A360915, A360916 (maximum induced paths), A360920.

Formula

T(m,n) = T(n,m).
T(m,n) = 2*m*n/3 + O(m+n) (Beluhov 2023, Proposition 3). - Pontus von Brömssen, May 08 2023

A360920 Array read by antidiagonals: T(m,n) is the maximum number of vertices in an induced tree in the grid graph P_m X P_n.

Original entry on oeis.org

1, 2, 2, 3, 3, 3, 4, 5, 5, 4, 5, 6, 7, 6, 5, 6, 8, 9, 9, 8, 6, 7, 9, 12, 12, 12, 9, 7, 8, 11, 14, 15, 15, 14, 11, 8, 9, 12, 16, 18, 19, 18, 16, 12, 9, 10, 14, 18, 21, 22, 22, 21, 18, 14, 10, 11, 15, 21, 24, 26, 26, 26, 24, 21, 15, 11, 12, 17, 23, 27, 30, 31, 31, 30, 27, 23, 17, 12
Offset: 1

Views

Author

Andrew Howroyd, Feb 26 2023

Keywords

Examples

			Array begins:
===============================================
  m\n|  1  2  3  4  5  6  7  8  9 10 11  12 ...
-----+-----------------------------------------
   1 |  1  2  3  4  5  6  7  8  9 10 11  12 ...
   2 |  2  3  5  6  8  9 11 12 14 15 17  18 ...
   3 |  3  5  7  9 12 14 16 18 21 23 25  27 ...
   4 |  4  6  9 12 15 18 21 24 27 30 33  36 ...
   5 |  5  8 12 15 19 22 26 30 34 37 41  44 ...
   6 |  6  9 14 18 22 26 31 35 39 44 48  52 ...
   7 |  7 11 16 21 26 31 36 41 46 51 56  61 ...
   8 |  8 12 18 24 30 35 41 46 52 58 63  69 ...
   9 |  9 14 21 27 34 39 46 52 59 65 71  78 ...
  10 | 10 15 23 30 37 44 51 58 65 72 79  86 ...
  11 | 11 17 25 33 41 48 56 63 71 79 87  94 ...
  12 | 12 18 27 36 44 52 61 69 78 86 94 102 ...
  ...

Links

Crossrefs

Main diagonal is A360921.
Cf. A360915, A360917, A360918 (maximum induced trees).

Formula

T(m,n) = T(n,m).
Showing 1-4 of 4 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.