TITLE

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

AUTHOR(S)
Hocquard, H.; Przybyło, J.
PUB. DATE
November 2017
SOURCE
Graphs & Combinatorics;Nov2017, Vol. 33 Issue 6, p1459
SOURCE TYPE
DOC. TYPE
Article
ABSTRACT
A proper edge k-colouring of a graph $$G=(V,E)$$ is an assignment $$c:E\rightarrow \{1,2,\ldots ,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)$$ for every edge uv of G. We denote by $$\chi '_{\Sigma }(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)$$ colours are needed for this goal. In this paper we prove that $$\chi '_\Sigma (G) \le \Delta (G)+1$$ for any graph G without isolated edges, with $$\mathrm{mad}(G)<3$$ and $$\Delta (G) \ge 6$$ .
ACCESSION #
126308058

## Related Articles

• Vertex Equitable Labeling of Cycle and Star Related Graphs. Jeyanthi, P.; Maheswari, A.; Vijayalaksmi, M. // Journal of Scientific Research;2015, Vol. 7 Issue 3, p33

Let G be a graph with p vertices and q edges and A = 0,1,2,..., A vertex labeling f: V (G) -> A induces an edge labeling f* defined by f*(uv) = f(u) + f(v) for all edges uv. For aâˆˆ A, let vf (a) be the number of vertices v with f(v) = a. A graph G is said to be vertex equitable if there...

• The proof of a conjecture concerning acyclic molecular graphs with maximal Hosoya index and diameter 4. Huiqing Liu // Journal of Mathematical Chemistry;Mar2008, Vol. 43 Issue 3, p1199

The Hosoya index of a graph is defined as the total number of the matchings of the graph. In this paper, we solve a conjecture in Ou, J. Math. Chem, DOI: 10.1007/S10910-006-9199-1 concerning acyclic molecular graphs with maximal Hosoya index and diameter 4.

• On (k,kn-k2-2k-1)-Choosability of n-Vertex Graphs. Charoenpanitseri, Wongsakorn // International Journal of Mathematics & Mathematical Sciences;5/12/2015, Vol. 2015, p1

A (k,t)-list assignment L of a graph G is a mapping which assigns a set of size k to each vertex v of G and |â‹ƒvâˆˆV(G)â€L(v)|=t. A graph G is (k,t)-choosable if G has a proper coloring f such that f(v)âˆˆL(v) for each (k,t)-list assignment L. In 2011, Charoenpanitseri et al....

• Some Results on Vertex Version and Edge Versions of Modified Schultz Index. Azari, Mahdieh // International Journal of Mathematical Combinatorics;2016, Vol. 2, p65

Let G1 and G2 be two simple connected graphs with disjoint vertex sets V(G1) and V(G2), respectively. For given vertices a1 G V(G1) and a2 âˆˆ V(G2), a splice of âˆˆ1 and G2 by vertices a1 and a2 is defined by identifying the vertices a1 and a2 in the union of G1 and G2 and a link of G1...

• A note on the augmented Zagreb index of cacti with fixed number of vertices and cycles. Ali, Akbar; Bhatti, Akhlaq A. // Kuwait Journal of Science;2016, Vol. 43 Issue 4, p11

Recent studies show that augmented Zagreb index ( AZI ) possess the best correlating ability among various well known topological indices for predicting the certain physicochemical properties of particular types of molecules. Hence, it is meaningful to study the mathematical properties of AZI...

• Vertex-Disjoint Cycles of Order Eight with Chords in a Bipartite Graph. QINGSONG ZOU; HONGYU CHEN; GUOJUN LI // Bulletin of the Malaysian Mathematical Sciences Society;2013, Vol. 36 Issue 1, p255

Let G = (V1,V2;E) be a bipartite graph with âˆ£ V1 âˆ£=âˆ£ V2 âˆ£= 4k, where k is a positive integer. In this paper, it is proved that if the minimum degree of G is at least 3k+1, then G contains k vertex-disjoint cycles of order eight such that each of them has at least two chords.

• SOME RESULTS ON THE SPLITTING SIGNED GRAPHS ...(S). ACHARYA, MUKTI; JAIN, RASHMI; KANSAL, SANGITA // Journal of Combinatorics & System Sciences;2014, Vol. 39 Issue 1/4, p23

A signed graph (or, in short, sigraph) S = (Su, s) consists of an underlying graph Su := G = (V, E) and a function Ïƒ : E(Su) â†’ {+, -}, called the signature of S. A marking of S is a function Î¼: V(S) â†’ {+, -}. The canonical marking of a signed graph S, denoted mÎ¼;Ïƒ, is...

• On 3-Regular Bipancyclic Subgraphs of Hypercubes. Borse, Y. M.; Shaikh, S. R. // International Journal of Combinatorics;5/5/2015, Vol. 2015, p1

The n-dimensional hypercube Qn is bipancyclic; that is, it contains a cycle of every even length from 4 to 2n. In this paper, we prove that Qnâ€‰â€‰(nâ‰¥3) contains a 3-regular, 3-connected, bipancyclic subgraph with l vertices for every even l from 8 to 2n except 10.

• The Minimum Equitable Domination Energy of a Graph. Rajendra, P.; Rangarajan, R. // International Journal of Mathematical Combinatorics;Sep2015, Vol. 3, p62

A subset D of V is called an equitable dominating set [8] if for every v âˆˆ V -D there exists a vertex u âˆˆ D such that uv âˆˆ E(G) and |deg(u) - deg(v)| â‰¤ 1, where deg(u) denotes the degree of vertex u and deg(v) denotes the degree of vertex v. Recently, The minimum covering...

• Further Properties of Trees with Minimal Atom-Bond Connectivity Index. Jianping Liu; Jinsong Chen // Abstract & Applied Analysis;2014, p1

Let G = (V, E) be a graph the atom-bond connectivity (ABC) index is defined as the sum of weights ((du + dv - 2 ) /dudv)1/2 over all edges uv of G, where du denotes the degree of a vertex u of G. In this paper, we determined a few structural features of the trees with minimal ABC index also we...

Share