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

Hocquard, H.; Przybyło, J.
November 2017
Graphs & Combinatorics;Nov2017, Vol. 33 Issue 6, p1459
Academic Journal
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$$ .


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...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics