Total-neighbor-distinguishing coloring by sums of fractals of generalized Sierpiński graphs
Miguel Palma, Carlos Arturo Rodriguez Palma, Simone Dantas · Journal of Combinatorial Optimization · 2026
Abstract The Total-Neighbor-Distinguishing Index by Sums of a graph G ( $$\textrm{TNDI}_{\sum }(G)$$ TNDI ∑ ( G ) ) is the smallest positive integer for which there exists a total coloring such that the sum of the color assigned to a vertex and the colors of all its incident edges is distinct, for every pair of adjacent vertices u and w . Pilsniak and Wozniak (2015) introduced this notion and conjectured that $$\textrm{TNDI}_{\sum }$$ TNDI ∑ is less than or equal to the maximum degree plus 3. In 2011, Gravier et al. introduced the concept of generalized Sierpiński graphs, denoted S ( n , G ), which extends the notion of Sierpiński graphs given by Hinz et al. (2017) by replacing the complete graph in their definition with any graph G . In this paper, we verify that S ( n , G ) graphs satisfy the $$\textrm{TNDI}_{\sum }$$ TNDI ∑ Conjecture, when G is a bipartite graph, a path, a cycle, a star or a complete graph. Furthermore, we determine the $$\textrm{TNDI}_{\sum }(S(n,G))$$ TNDI ∑ ( S ( n , G ) ) when G is a complete bipartite, a path, a cycle, a star or a regular bipartite graph. Remarkably, these colorings also satisfy the corresponding conjecture for the Adjacent-Vertex-Distinguishing Total Coloring (AVDTC), and the $$\textrm{TNDI}_{\sum }$$ TNDI ∑ of these graphs coincides with their AVDTC chromatic number. Moreover, we show that the $$\textrm{TNDI}_{\sum }$$ TNDI ∑ Conjecture is satisfied for the graph classes of the regularizations $$+S_p^n$$ + S p n and $$++S_p^n$$ + + S p n of Sierpiński graphs $$S_p^n$$ S p n , which contributes to proving that the conjecture holds for their respective fractals as well.