# zbMATH — the first resource for mathematics

Neighbor sum distinguishing index. (English) Zbl 1272.05047
Summary: We consider proper edge colorings of a graph $$G$$ using colors of the set $$\{1,\dots ,k\}$$. Such a coloring is called neighbor sum distinguishing if for any pair of adjacent vertices $$x$$ and $$y$$ the sum of colors taken on the edges incident to $$x$$ is different from the sum of colors taken on the edges incident to $$y$$. The smallest value of $$k$$ in such a coloring of $$G$$ is denoted by $$\mathrm{ndi}_\Sigma (G)$$. In the paper we conjecture that for any connected graph $$G\neq C_5$$ of order $$n\geq 3$$ we have $$\mathrm{ndi}_\Sigma (G)\leq\Delta (G)+2$$. We prove this conjecture for several classes of graphs. We also show that $$\mathrm{ndi}_\Sigma (G)\leq 7\Delta (G)/2$$ for any graph $$G$$ with $$\Delta (G)\geq 2$$ and $$\mathrm{ndi}_\Sigma (G)\leq 8$$ if $$G$$ is cubic.

##### MSC:
 05C15 Coloring of graphs and hypergraphs
Full Text:
##### References:
  Akbari, S.; Bidkhori, H.; Nosrati, N., R-strong edge colorings of graphs, Discrete. Math., 306, 3005-3010, (2006) · Zbl 1112.05035  Bondy J.A., Murty U.S.R.: Graph Theory with Applications. Macmillan, London (1976) · Zbl 1226.05083  Balister, PN.; Győri, E.; Lehel, L.; Schelp, R.H., Adjacent vertex distinguishing edge-colorings, SIAM. J. Discrete. Math., 21, 237-250, (2007) · Zbl 1189.05056  Dénes, J., Keedwell, A.D.: Transversal and Complete Mappings, In: Latin Squares. New Developments in the Theory and Applications, Elsevier, Amsterdam (1991) · Zbl 1075.05034  Edwards, K.; Horňák, M.; Woźniak, M., On the neighbour-distinguishing index of a graph, Graphs. Combin., 22, 341-350, (2006) · Zbl 1107.05032  Hatami, H., Is a bound on the adjacent vertex distinguishing edge chromatic number, J. Combin. Theory. Ser B., 95, 246-256, (2005) · Zbl 1075.05034  Mahéo, M., Saclé, J-F.: Some results on (Σ, $$p$$, $$g$$)-valuation of connected graphs, Rapport de Recherche 1497, Université de Paris-Sud, Centre d’Orsay (2008) · Zbl 1189.05056  Zhang, Z.; Liu, L.; Wang, J., Adjacent strong edge coloring of graph, Appl. Math. Lett., 15, 623-626, (2005) · Zbl 1008.05050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.