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.

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Akbari, S.; Bidkhori, H.; Nosrati, N., R-strong edge colorings of graphs, Discrete. Math., 306, 3005-3010, (2006) · Zbl 1112.05035
[2] Bondy J.A., Murty U.S.R.: Graph Theory with Applications. Macmillan, London (1976) · Zbl 1226.05083
[3] 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
[4] 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
[5] 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
[6] 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
[7] 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
[8] 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.