LAUSR.org creates dashboard-style pages of related content for over 1.5 million academic articles. Sign Up to like articles & get recommendations!

On the Neighbour Sum Distinguishing Index of Graphs with Bounded Maximum Average Degree

Photo by ledoc from unsplash

A proper edge k-colouring of a graph $$G=(V,E)$$G=(V,E) is an assignment $$c:E\rightarrow \{1,2,\ldots ,k\}$$c:E→{1,2,…,k} of colours to the edges of the graph such that no two adjacent edges are associated… Click to show full abstract

A proper edge k-colouring of a graph $$G=(V,E)$$G=(V,E) is an assignment $$c:E\rightarrow \{1,2,\ldots ,k\}$$c:E→{1,2,…,k} of colours to the edges of the graph such that no two adjacent edges are associated with the same colour. A neighbour sum distinguishing edge k-colouring, or nsd k-colouring for short, is a proper edge k-colouring such that $$\sum _{e\ni u}c(e)\ne \sum _{e\ni v}c(e)$$∑e∋uc(e)≠∑e∋vc(e) for every edge uv of G. We denote by $$\chi '_{\Sigma }(G)$$χΣ′(G) the neighbour sum distinguishing index of G, which is the least integer k such that an nsd k-colouring of G exists. By definition at least maximum degree, $$\Delta (G)$$Δ(G) colours are needed for this goal. In this paper we prove that $$\chi '_\Sigma (G) \le \Delta (G)+1$$χΣ′(G)≤Δ(G)+1 for any graph G without isolated edges, with $$\mathrm{mad}(G)<3$$mad(G)<3 and $$\Delta (G) \ge 6$$Δ(G)≥6.

Keywords: sum; sum distinguishing; neighbour sum; edge; distinguishing index

Journal Title: Graphs and Combinatorics
Year Published: 2017

Link to full text (if available)


Share on Social Media:                               Sign Up to like & get
recommendations!

Related content

More Information              News              Social Media              Video              Recommended



                Click one of the above tabs to view related content.