Allan Bickle - cp's OEIS frontend

A381565 2-tone chromatic number of a particular class of planar graphs with 3n+3 vertices.

5, 6, 7, 7, 8, 8, 9, 9, 10, 10, 10, 11, 11, 11, 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 21

Offset: 1

Allan Bickle, Feb 27 2025

nonn

The 2-tone chromatic number of a graph G is the smallest number of colors for which G has a coloring where every vertex has two distinct colors, no adjacent vertices have a common color, and no pair of vertices at distance 2 have two common colors.

The graphs are formed by replacing each edge of K_3 by n disjoint paths with length 2, resulting in 3n+3 vertices. These graphs have large 2-tone chromatic number relative to their maximum degree of 2t.

			For n=1, the graph is a 6-cycle, which has a 2-tone 5-coloring -12-34-15-32-14-35-.  Thus a(1) = 5.

Allan Bickle, 2-Tone coloring of joins and products of graphs, Congr. Numer. 217 (2013) 171-190.
Allan Bickle, 2-Tone Coloring of Planar Graphs, Bull. Inst. Combin. Appl. 103 (2025) 114-129.
Allan Bickle and B. Phillips, t-Tone Colorings of Graphs, Utilitas Math, 106 (2018) 85-102.
D. W. Cranston and H. LaFayette, The t-tone chromatic number of classes of sparse graphs, Australas. J. Combin. 86 (2023) 458-476.

Cf. A003057, A351120 (pair coloring).

Cf. A350361 (trees), A350362 (cycles), A350715 (wheels), A366727 (outerplanar), A366728 (square of cycles), A381562 (maximal planar).

a(n) = ceiling(1.5 + sqrt(6*n + 6.25)) for n < 18.

a(n) = ceiling(0.5 + sqrt(6*n + 24.25)) for n > 6.

A381564 2-tone chromatic number of a path with n-2 vertices joined to two adjacent vertices.

Original entry on oeis.org

8, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16

Offset: 4

Allan Bickle, Feb 27 2025

nonn

The 2-tone chromatic number of a graph G is the smallest number of colors for which G has a coloring where every vertex has two distinct colors, no adjacent vertices have a common color, and no pair of vertices at distance 2 have two common colors.

The graphs are maximal planar.

			The central vertices each have two disjoint labels.  All vertices on the path require distinct pairs.
The colorings for small paths are shown below.
  12-34
  12-34-15
  12-34-15-23
  12-34-15-23-14
  12-34-15-23-14-25
  12-34-15-23-14-25-13
  12-34-15-23-14-25-13-24
  12-34-15-23-14-25-13-24-35

Allan Bickle, 2-Tone coloring of joins and products of graphs, Congr. Numer. 217 (2013) 171-190.
Allan Bickle, 2-Tone Coloring of Planar Graphs, Bull. Inst. Combin. Appl. 103 (2025) 114-129.
Allan Bickle and B. Phillips, t-Tone Colorings of Graphs, Utilitas Math, 106 (2018) 85-102.

Cf. A003057, A351120 (pair coloring).

Cf. A350361 (trees), A350362 (cycles), A350715 (wheels), A366727 (outerplanar), A366728 (square of cycles), A381562 (maximal planar), A381563 (double wheels).

a(n) = ceiling((9 + sqrt(8*n - 15))/2) for n > 8.

A381563 2-tone chromatic number of a double wheel graph with n vertices.

Original entry on oeis.org

9, 9, 8, 8, 9, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15

Offset: 5

Allan Bickle, Feb 27 2025

nonn

The 2-tone chromatic number of a graph G is the smallest number of colors for which G has a coloring where every vertex has two distinct colors, no adjacent vertices have a common color, and no pair of vertices at distance 2 have two common colors.

A double wheel has two vertices joined to a all vertices of a cycle.

			The central vertices share exactly one color.  All vertices on the cycle require distinct pairs.
The colorings for small (broken) cycles are shown below.
  -12-34-56-
  -12-34-15-36-
  -12-34-51-23-45-
  -12-34-15-32-14-35-
  -12-34-56-13-24-35-46-
  -12-34-15-23-14-25-13-45-
  -12-34-15-32-14-25-13-24-35-

Allan Bickle, 2-Tone coloring of joins and products of graphs, Congr. Numer. 217 (2013) 171-190.
Allan Bickle, 2-Tone Coloring of Planar Graphs, Bull. Inst. Combin. Appl. 103 (2025) 114-129.
Allan Bickle and B. Phillips, t-Tone Colorings of Graphs, Utilitas Math, 106 (2018) 85-102.

Cf. A003057, A351120 (pair coloring).

Cf. A350361 (trees), A350362 (cycles), A350715 (wheels), A366727 (outerplanar), A366728 (square of cycles), A381562 (maximal planar).

a(n) = A351120(n-2) + 3 = A350715(n-1) + 1.

a(n) = ceiling((7 + sqrt(8*n - 15))/2) for n > 12.

A381562 Minimum 2-tone chromatic number of maximal planar graphs with n vertices.

Original entry on oeis.org

6, 8, 9, 9, 8, 8, 8, 8, 8, 8, 8, 7, 8, 8, 8, 7

Offset: 3

Allan Bickle, Feb 27 2025

nonn

The 2-tone chromatic number of a graph G is the smallest number of colors for which G has a coloring where every vertex has two distinct colors, no adjacent vertices have a common color, and no pair of vertices at distance 2 have two common colors.

For n in {19,22,23,27}, a(n) is either 7 or 8. All larger values are 7.

			For n=3, all 3 vertices get two distinct colors, so a(3) = 6.
For n=4, all 4 vertices get two distinct colors, so a(3) = 8.
For n=5 or 6, the extremal graph is a double wheel.

Allan Bickle, 2-Tone coloring of joins and products of graphs, Congr. Numer. 217 (2013) 171-190.
Allan Bickle, 2-Tone Coloring of Planar Graphs, Bull. Inst. Combin. Appl. 103 (2025) 114-129.
Allan Bickle and B. Phillips, t-Tone Colorings of Graphs, Utilitas Math, 106 (2018) 85-102.

Cf. A003057, A351120 (pair coloring).

Cf. A350361 (trees), A350362 (cycles), A350715 (wheels), A366727 (outerplanar), A366728 (square of cycles).

a(n) = 7 for n > 27.

A375256 Number of pairs of antipodal vertices in the level n Hanoi graph.

Original entry on oeis.org

3, 12, 39, 129, 453, 1677, 6429, 25149, 99453, 395517, 1577469, 6300669, 25184253, 100700157, 402726909, 1610760189, 6442745853, 25770393597, 103080394749, 412319219709, 1649272160253, 6597079203837, 26388297940989, 105553154015229, 422212540563453, 1688850011258877, 6755399743045629

Offset: 1

Allan Bickle, Aug 07 2024

nonn

A level 1 Hanoi graph is a triangle. Level n+1 is formed from three copies of level n by adding edges between pairs of corner vertices of each pair of triangles. This graph represents the allowable moves in the Towers of Hanoi problem with n disks.

Antipodal vertices are a pair of vertices at maximum distance in a graph. The diameter of the level n Hanoi graph is 2^n - 1.

			2 example graphs:
                           o
                          / \
                         o---o
                        /     \
             o         o       o
            / \       / \     / \
           o---o     o---o---o---o
Graph:      H_1           H_2
Since the level 1 Hanoi graph is a triangle, a(1) = 3.

Paolo Xausa, Table of n, a(n) for n = 1..1000
Allan Bickle, Properties of Sierpinski Triangle Graphs, Springer PROMS 448 (2021) 295-303.
A. Hinz, S. Klavzar, and S. Zemljic, A survey and classification of Sierpinski-type graphs, Discrete Applied Mathematics 217 3 (2017), 565-600.
Eric Weisstein's World of Mathematics, Hanoi Graph
Index entries for linear recurrences with constant coefficients, signature (7,-14,8).

Cf. A000225, A029858, A058809 (Hanoi graphs).
Cf. A370933 (antipodal pairs in Sierpiński triangle graphs).
Cf. A193233, A297928.

A375256[n_] := 3*(2^(2*n - 3) + 3*2^(n - 2) - 1);
Array[A375256, 30] (* or *)
LinearRecurrence[{7, -14, 8}, {3, 12, 39}, 30] (* Paolo Xausa, Sep 23 2024 *)

a(n) = 3*(2^(2*n-3)+3*2^(n-2)-1); \\ Michel Marcus, Aug 08 2024

a(n) = 3*(2^(2n-3)+3*2^(n-2)-1).
a(n) = A370933(n+1) - 3.
a(n) = 3*A297928(n-2) for n>=2. - Alois P. Heinz, Sep 23 2024

More terms from Michel Marcus, Aug 08 2024

A370933 Number of pairs of antipodal vertices in the level n>1 Sierpiński triangle graph.

Original entry on oeis.org

6, 15, 42, 132, 456, 1680, 6432, 25152, 99456, 395520, 1577472, 6300672, 25184256, 100700160, 402726912, 1610760192, 6442745856, 25770393600, 103080394752, 412319219712, 1649272160256, 6597079203840, 26388297940992, 105553154015232, 422212540563456, 1688850011258880, 6755399743045632

Offset: 2

Allan Bickle, Aug 07 2024

A level 1 Sierpiński triangle graph is a triangle. Level n+1 is formed from three copies of level n by identifying pairs of corner vertices of each pair of triangles.

Antipodal vertices are a pair of vertices at maximum distance in a graph. The diameter of the level n Sierpiński triangle graph is 2^(n-1).

			3 example graphs:                        o
                                        / \
                                       o---o
                                      / \ / \
                        o            o---o---o
                       / \          / \     / \
             o        o---o        o---o   o---o
            / \      / \ / \      / \ / \ / \ / \
           o---o    o---o---o    o---o---o---o---o
Graph:      S_1        S_2              S_3
For S_2, there are 3 pairs of corners and 3 pairs of a corner and a middle vertex, so a(2) = 6.

Paolo Xausa, Table of n, a(n) for n = 2..1000
Index entries for linear recurrences with constant coefficients, signature (6,-8).
Allan Bickle, Properties of Sierpinski Triangle Graphs, Springer PROMS 448 (2021) 295-303.
A. Hinz, S. Klavzar, and S. Zemljic, A survey and classification of Sierpinski-type graphs, Discrete Applied Mathematics 217 3 (2017), 565-600.
Eric Weisstein's World of Mathematics, Sierpiński Gasket Graph

Cf. A007283, A029858, A067771, A193277, A233774, A233775, A246959, A298202 (Sierpiński triangle graphs).

Cf. A375256 (antipodal pairs in Hanoi graphs).

A370933[n_] := 3*2^(n - 3)*(2^(n - 2) + 3);
Array[A370933, 30, 2] (* or *)
LinearRecurrence[{6, -8}, {6, 15}, 30] (* Paolo Xausa, Sep 23 2024 *)

a(n) = 3*2^(n-3)*(2^(n-2)+3); \\ Michel Marcus, Aug 08 2024

a(n) = 3*2^(n-3)*(2^(n-2)+3).
a(n) = 3*A257273(n-2).
a(n) = A375256(n-1) + 3.

More terms from Michel Marcus, Aug 08 2024

A372027 Maximum second Zagreb index of maximal outerplanar graphs with n vertices.

Original entry on oeis.org

12, 33, 61, 96, 135, 181, 233, 291, 355, 425, 501, 583, 671, 765, 865, 971, 1083, 1201, 1325, 1455, 1591, 1733, 1881, 2035, 2195, 2361, 2533, 2711, 2895, 3085, 3281, 3483, 3691, 3905, 4125, 4351, 4583, 4821, 5065, 5315, 5571, 5833, 6101, 6375, 6655, 6941, 7233, 7531

Offset: 3

Allan Bickle, Apr 16 2024

nonn

The second Zagreb index of a graph is the sum of the products of the degrees over all edges of the graph.

A maximal outerplanar graph has all vertices on the exterior region, and all other regions triangles. The extremal graphs are fans, except when n=6. Then the extremal graph is the triangular grid with degrees 4,4,4,2,2,2.

			The graph K_3 has 3 degree 2 vertices, so a(3) = 3*4 = 12.

Paolo Xausa, Table of n, a(n) for n = 3..10000
Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.
Allan Bickle, Zagreb Indices of Maximal k-degenerate Graphs, Australas. J. Combin. 89 1 (2024) 167-178.
J. Estes and B. Wei, Sharp bounds of the Zagreb indices of k-trees, J Comb Optim 27 (2014), 271-291.
A. Hou, S. Li, L. Song, and B. Wei, Sharp bounds for Zagreb indices of maximal outerplanar graphs, J Comb Optim 22 (2011), 252-269.
Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Cf. A002378, A152811, A371912 (Zagreb indices of maximal k-degenerate graphs).

Cf. A051624, A372025, A372026 (second Zagreb indices of maximal k-degenerate graphs).

LinearRecurrence[{3, -3, 1}, {12, 33, 61, 96, 135, 181, 233}, 50] (* Paolo Xausa, Jan 22 2025 *)

a(n) = 3*n^2 + n - 19 when n is not 3 or 6.
From Chai Wah Wu, Apr 16 2024: (Start)
a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n > 9.
G.f.: x^3*(x^6 - 3*x^5 + 3*x^4 + 2*x^2 + 3*x - 12)/(x - 1)^3. (End)

A372026 Minimum second Zagreb index of maximal 2-degenerate graphs with n vertices.

Original entry on oeis.org

12, 33, 51, 86, 116, 147, 178, 210, 242, 274, 306, 338, 370, 402, 434, 466, 498, 530, 562, 594, 626, 658, 690, 722, 754, 786, 818, 850, 882, 914, 946, 978, 1010, 1042, 1074, 1106, 1138, 1170, 1202, 1234, 1266, 1298, 1330, 1362, 1394, 1426, 1458, 1490, 1522, 1554, 1586, 1618, 1650, 1682, 1714, 1746, 1778, 1810

Offset: 3

Allan Bickle, Apr 16 2024

nonn

The second Zagreb index of a graph is the sum of the products of the degrees over all edges of the graph.

A maximal 2-degenerate graph can be constructed from a 2-clique by iteratively adding a new 2-leaf (vertex of degree 2) adjacent to two existing vertices. The extremal graphs are described in (Bickle 2024).

			The graph K_3 has 3 degree 2 vertices, so a(3) = 3*4 = 12.

Paolo Xausa, Table of n, a(n) for n = 3..10000
Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.
Allan Bickle, Zagreb Indices of Maximal k-degenerate Graphs, Australas. J. Combin. 89 1 (2024) 167-178.
J. Estes and B. Wei, Sharp bounds of the Zagreb indices of k-trees, J Comb Optim 27 (2014), 271-291.
Index entries for linear recurrences with constant coefficients, signature (2,-1).

Cf. A002378, A152811, A371912 (Zagreb indices of maximal k-degenerate graphs).
Cf. A051624, A372025, A372026 (second Zagreb indices of maximal k-degenerate graphs).
Cf. A372027 (second Zagreb index of MOPs).

LinearRecurrence[{2, -1}, {12, 33, 51, 86, 116, 147, 178, 210}, 60] (* Paolo Xausa, Jan 22 2025 *)

a(n) = 32*n-110 for n>8.
From Chai Wah Wu, Apr 16 2024: (Start)
a(n) = 2*a(n-1) - a(n-2) for n > 10.
G.f.: x^3*(x^7 + x^5 - 5*x^4 + 17*x^3 - 3*x^2 + 9*x + 12)/(x - 1)^2. (End)

A372025 Maximum second Zagreb index of maximal 3-degenerate graphs with n vertices.

Original entry on oeis.org

12, 54, 120, 210, 324, 462, 624, 810, 1020, 1254, 1512, 1794, 2100, 2430, 2784, 3162, 3564, 3990, 4440, 4914, 5412, 5934, 6480, 7050, 7644, 8262, 8904, 9570, 10260, 10974, 11712, 12474, 13260, 14070, 14904, 15762, 16644, 17550, 18480, 19434, 20412, 21414, 22440, 23490, 24564, 25662, 26784, 27930

Offset: 3

Allan Bickle, Apr 16 2024

The second Zagreb index of a graph is the sum of the products of the degrees over all edges of the graph.

A maximal 3-degenerate graph can be constructed from a 3-clique by iteratively adding a new 3-leaf (vertex of degree 3) adjacent to three existing vertices. The extremal graphs are 3-stars, so the bound also applies to 3-trees.

			The graph K_3 has 3 degree 2 vertices, so a(3) = 3*4 = 12.

Paolo Xausa, Table of n, a(n) for n = 3..10000
Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.
Allan Bickle, Zagreb Indices of Maximal k-degenerate Graphs, Australas. J. Combin. 89 1 (2024) 167-178.
J. Estes and B. Wei, Sharp bounds of the Zagreb indices of k-trees, J Comb Optim 27 (2014), 271-291.
Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Cf. A002378, A152811, A371912 (Zagreb indices of maximal k-degenerate graphs).
Cf. A051624, A372025, A372026 (second Zagreb indices of maximal k-degenerate graphs).
Cf. A372027 (second Zagreb index of MOPs).

LinearRecurrence[{3, -3, 1}, {12, 54, 120}, 50] (* Paolo Xausa, Jan 22 2025 *)

a(n) = 3*(n-1)^2 + 9*(n-3)*(n-1).
From Chai Wah Wu, Apr 16 2024: (Start)
a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n > 5.
G.f.: x^3*(6*x^2 - 18*x - 12)/(x - 1)^3. (End)
a(n) = 6*A014107(n-1). Sum_{n>=3} 1/a(n) = (1/2+log(2))/9 = 0.1325719... - R. J. Mathar, Apr 22 2024

A371912 Maximum Zagreb index of maximal 3-degenerate graphs with n vertices.

Original entry on oeis.org

12, 36, 66, 102, 144, 192, 246, 306, 372, 444, 522, 606, 696, 792, 894, 1002, 1116, 1236, 1362, 1494, 1632, 1776, 1926, 2082, 2244, 2412, 2586, 2766, 2952, 3144, 3342, 3546, 3756, 3972, 4194, 4422, 4656, 4896, 5142, 5394, 5652, 5916, 6186, 6462, 6744, 7032, 7326, 7626, 7932

Offset: 3

Allan Bickle, Apr 11 2024

The Zagreb index of a graph is the sum of the squares of the degrees over all vertices of the graph.

A maximal 3-degenerate graph can be constructed from a 3-clique by iteratively adding a new 3-leaf (vertex of degree 3) adjacent to three existing vertices. The extremal graphs are 3-stars, so the bound also applies to 3-trees.

			The graph K_3 has 3 degree 2 vertices, so a(3) = 3*4 = 12.

Paolo Xausa, Table of n, a(n) for n = 3..10000
Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.
Allan Bickle, Zagreb Indices of Maximal k-degenerate Graphs, Australas. J. Combin. 89 1 (2024) 167-178.
J. Estes and B. Wei, Sharp bounds of the Zagreb indices of k-trees, J Comb Optim 27 (2014), 271-291.
I. Gutman and K. Das, The first Zagreb index 30 years after, MATCH Commun. Math. Comput. Chem. 50 (2004), 83-92.
A. Hou, S. Li, L. Song, and B. Wei, Sharp bounds for Zagreb indices of maximal outerplanar graphs, J Comb Optim 22 (2011), 252-269.
Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Cf. A002378, A152811, A371912 (Zagreb indices of maximal k-degenerate graphs).

Array[3*(#^2 + # - 8) &, 50, 3] (* Paolo Xausa, Jun 09 2024 *)

a(n) = 3*(n-1)^2 + 9*(n-3).
a(n) = 6*A046691(n-2) for n>2.
a(n) = 6*A060577(n-1) for n>3.
G.f.: 6*x^3*(2 - x^2)/(1 - x)^3. - Stefano Spezia, Apr 12 2024
a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n > 5. - Chai Wah Wu, Apr 16 2024
Sum_{n>=3} 1/a(n) = 19/72 + Pi*tan(Pi*sqrt(33)/2)*sqrt(33)/99 = 0.1865497.... - R. J. Mathar, Apr 22 2024

cp's OEIS Frontend

User: Allan Bickle

A381565 2-tone chromatic number of a particular class of planar graphs with 3n+3 vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A381564 2-tone chromatic number of a path with n-2 vertices joined to two adjacent vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A381563 2-tone chromatic number of a double wheel graph with n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A381562 Minimum 2-tone chromatic number of maximal planar graphs with n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A375256 Number of pairs of antipodal vertices in the level n Hanoi graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A370933 Number of pairs of antipodal vertices in the level n>1 Sierpiński triangle graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A372027 Maximum second Zagreb index of maximal outerplanar graphs with n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A372026 Minimum second Zagreb index of maximal 2-degenerate graphs with n vertices.

Views

Author

Keywords

Comments