Search

A proper total $k$-colouring of a graph $G=(V,E)$ is an assignment $c : V \cup E\to \{1,2,\ldots,k\}$ of colours to the edges and the vertices of $G$ such that no two adjacent edges or vertices and no edge and its end-vertices are associated with the same colour. A total neighbour sum distinguishing $k$-colouring, or tnsd $k$-colouring for short, is a proper total $k$-colouring such that $\sum_{e\ni u}c(e)+c(u)\neq \sum_{e\ni v}c(e)+c(v)$ for every edge $uv$ of $G$. We denote by $\chi''_{\Sigma}(G)$ the total neighbour sum distinguishing index of $G$, which is the least integer $k$ such that a tnsd edge $k$-colouring of $G$ exists. It has been conjectured that $\chi''_{\Sigma}(G) \leq \Delta(G) + 3$ for every graph $G$. In this paper we confirm this conjecture for any graph $G$ with ${\rm mad}(G), Comment: 10 pages. arXiv admin note: text overlap with arXiv:1508.06112

A radio labeling of a graph $G$ is a mapping $f: V(G) \rightarrow \{0, 1, 2, \ldots\}$ such that $|f(u)-f(v)|\geq d + 1 - d(u,v)$ for every pair of distinct vertices $u, v$ of $G$, where $d$ is the diameter of $G$ and $d(u,v)$ the distance between $u$ and $v$ in $G$. The radio number of $G$ is the smallest integer $k$ such that $G$ has a radio labeling $f$ with $\max\{f(v) : v \in V(G)\} = k$. We give a necessary and sufficient condition for a lower bound on the radio number of trees to be achieved, two other sufficient conditions for the same bound to be achieved by a tree, and an upper bound on the radio number of trees. Using these, we determine the radio number for three families of trees., 19 pages, 7 figures. This is the final version accepted in Discrete Applied Mathematics

A \emph{locally irregular graph} is a graph whose adjacent vertices have distinct degrees. We say that a graph $G$ can be decomposed into $k$ locally irregular subgraphs if its edge set may be partitioned into $k$ subsets each of which induces a locally irregular subgraph in $G$. It has been conjectured that apart from the family of exceptions which admit no such decompositions, i.e., odd paths, odd cycles and a special class of graphs of maximum degree $3$, every connected graph can be decomposed into $3$ locally irregular subgraphs. Using a combination of a probabilistic approach and some known theorems on degree constrained subgraphs of a given graph, we prove this to hold for graphs of sufficiently large minimum degree, $\delta(G)\geq 10^{10}$. This problem is strongly related to edge colourings distinguishing neighbours by the pallets of their incident colours and to 1-2-3 Conjecture. In particular, the contribution of this paper constitutes a strengthening of a result of Addario-Berry, Aldred, Dalal and Reed [J. Combin. Theory Ser. B 94 (2005) 237-244]., Comment: 12 pages

An $L(2, 1)$-labeling of a graph $G$ is an assignment of a nonnegative integer to each vertex of $G$ such that adjacent vertices receive integers that differ by at least two and vertices at distance two receive distinct integers. The span of such a labeling is the difference between the largest and smallest integers used. The $\lambda$-number of $G$, denoted by $\lambda(G)$, is the minimum span over all $L(2, 1)$-labelings of $G$. Bodlaender {\it et al.} conjectured that if $G$ is an outerplanar graph of maximum degree $\Delta$, then $\lambda(G)\leq \Delta+2$. Calamoneri and Petreschi proved that this conjecture is true when $\Delta \geq 8$ but false when $\Delta=3$. Meanwhile, they proved that $\lambda(G)\leq \Delta+5$ for any outerplanar graph $G$ with $\Delta=3$ and asked whether or not this bound is sharp. In this paper we answer this question by proving that $\lambda(G)\leq \Delta + 3$ for every outerplanar graph with maximum degree $\Delta=3$. We also show that this bound $\Delta + 3$ can be achieved by infinitely many outerplanar graphs with $\Delta=3$.

Given a finite or infinite graph GG and positive integers l,h1,h2,h3l,h1,h2,h3, an L(h1,h2,h3)L(h1,h2,h3)-labelling of GG with span ll is a mapping f:V(G)→{0,1,2,…,l}f:V(G)→{0,1,2,…,l} such that, for i=1,2,3i=1,2,3 and any u,v∈V(G)u,v∈V(G) at distance ii in GG, |f(u)−f(v)|≥hi|f(u)−f(v)|≥hi. A C(h1,h2,h3)C(h1,h2,h3)-labelling of GG with span ll is defined similarly by requiring |f(u)−f(v)|l≥hi|f(u)−f(v)|l≥hi instead, where |x|l=min{|x|,l−|x|}|x|l=min{|x|,l−|x|}. The minimum span of an L(h1,h2,h3)L(h1,h2,h3)-labelling, or a C(h1,h2,h3)C(h1,h2,h3)-labelling, of GG is denoted by λh1,h2,h3(G)λh1,h2,h3(G), or σh1,h2,h3(G)σh1,h2,h3(G), respectively. Two related invariants, λh1,h2,h3∗(G) and σh1,h2,h3∗(G), are defined similarly by requiring further that for every vertex uu there exists an interval Iumod(l+1) or modl, respectively, such that the neighbours of uu are assigned labels from IuIu and Iv∩Iw=0Iv∩Iw=0 for every edge vwvw of GG. A recent result asserts that the L(2,1,1)L(2,1,1)-labelling problem is NP-complete even for the class of trees. In this paper we study the L(h,p,p)L(h,p,p) and C(h,p,p)C(h,p,p) labelling problems for finite or infinite trees TT with finite maximum degree, where h≥p≥1h≥p≥1 are integers. We give sharp bounds on λh,p,p(T)λh,p,p(T), λh,p,p∗(T), σh,1,1(T)σh,1,1(T) and σh,1,1∗(T), together with linear time approximation algorithms for the L(h,p,p)L(h,p,p)-labelling and the C(h,1,1)C(h,1,1)-labelling problems for finite trees. We obtain the precise values of these four invariants for complete mm-ary trees with height at least 4, the infinite complete mm-ary tree, and the infinite (m+1)(m+1)-regular tree and its finite subtrees induced by vertices up to a given level. We give sharp bounds on σh,p,p(T)σh,p,p(T) and σh,p,p∗(T) for trees with maximum degree Δ≤h/pΔ≤h/p, and as a special case we obtain that σh,1,1(T)=σh,1,1∗(T)=2h+Δ−1 for any tree TT with Δ≤hΔ≤h.

An antimagic labelling of a graph $G$ is a bijection $f:E(G)\to\{1,\ldots,E(G)\}$ such that the sums $S_v=\sum_{e\ni v}f(e)$ distinguish all vertices. A well-known conjecture of Hartsfield and Ringel (1994) is that every connected graph other than $K_2$ admits an antimagic labelling. Recently, two sets of authors (Arumugam, Premalatha, Ba\v{c}a \& Semani\v{c}ov\'a-Fe\v{n}ov\v{c}\'ikov\'a (2017), and Bensmail, Senhaji \& Lyngsie (2017)) independently introduced the weaker notion of a local antimagic labelling, where only adjacent vertices must be distinguished. Both sets of authors conjectured that any connected graph other than $K_2$ admits a local antimagic labelling. We prove this latter conjecture using the probabilistic method. Thus the parameter of local antimagic chromatic number, introduced by Arumugam et al., is well-defined for every connected graph other than $K_2$ ., Discrete Mathematics & Theoretical Computer Science ; Vol. 20 no. 1 ; 13658050