-labelling of graphs with few ’s

详细信息    查看全文

• 作者：Má ; rcia R. Cerioli^a ; ^{cerioli@cos.ufrj.br" class="auth_mail" title="E-mail the corresponding author} ; Nicolas A. Martins^b ; ^{nicolasam@lia.ufc.br" class="auth_mail" title="E-mail the corresponding author} ; Daniel F.D. Posner^a ; ^{posner@cos.ufrj.br" class="auth_mail" title="E-mail the corresponding author} ; Rudini Sampaio^b ; ^{rudini@lia.ufc.br" class="auth_mail" title="E-mail the corresponding author}
• 关键词：L(2 ; 1)L(2 ; 1)-labelling ; Primeval decomposition ; (q ; q&minus ; 4)(q ; q&minus ; 4)-graphs
• 刊名：Discrete Optimization
• 出版年：2016
• 出版时间：May 2016
• 年：2016
• 卷：20
• 期：Complete
• 页码：1-10
• 全文大小：598 K

文摘

Given a simple graph G$G$, an 6240178af1003611a3" title="Click to view the MathML source">L(2,1)$L(2,1)$-labelling (or λ$\lambda$-labelling) of G$G$ is a function c:V(G)→N$c:V\left(G\right)\to \mathbb{N}$ such that |c(x)−c(y)|≥2$|c\left(x\right)-c\left(y\right)|\ge 2$, if x$x$ and y$y$ are neighbors and |c(x)−c(y)|≥1$|c\left(x\right)-c\left(y\right)|\ge 1$ if x$x$ and y$y$ have a common neighbor. The span of a labelling is the difference of the smallest and largest labels used. An 6240178af1003611a3" title="Click to view the MathML source">L(2,1)$L(2,1)$-span of a graph G$G$, denoted by λ(G)$\lambda \left(G\right)$, is a minimum span over all 6240178af1003611a3" title="Click to view the MathML source">L(2,1)$L(2,1)$-labellings of G$G$. The problem of determining if λ(G)≤k$\lambda \left(G\right)\le k$ is NP-Complete for any k≥4$k\ge 4$. In this paper, we obtain a linear time algorithm to compute λ(G)$\lambda \left(G\right)$ for any (q,q−4)$(q,q-4)$-graph with q$q$ fixed. Another important topic regarding the λ$\lambda$-labelling is to bound the λ$\lambda$-chromatic number of a graph by some function of it. Griggs and Yeh conjectured that λ(G)≤Δ²$\lambda \left(G\right)\le {\Delta }^2$ for any graph G$G$ with maximum degree Δ≥2$\Delta \ge 2$. They also proved that the greedy algorithm for the problem uses at most Δ²+Δ${\Delta }^2+\Delta$. Furthermore we prove that the Griggs–Yeh conjecture is true for P₄$P_4$-sparse graphs, P₄$P_4$-laden graphs and all (q,q−4)$(q,q-4)$-graphs with at least 3q/2$3q/2$ vertices.