L(p,q)-labeling of sparse graphs |
| |
Authors: | Clément Charpentier Mickaël Montassier André Raspaud |
| |
Institution: | 1. LaBRI, Université de Bordeaux, 351, cours de la Libération, 34405, Talence cedex, France
|
| |
Abstract: | Let p and q be positive integers. An L(p,q)-labeling of a graph G with a span s is a labeling of its vertices by integers between 0 and s such that adjacent vertices of G are labeled using colors at least p apart, and vertices having a common neighbor are labeled using colors at least q apart. We denote by λ p,q (G) the least integer k such that G has an L(p,q)-labeling with span k. The maximum average degree of a graph G, denoted by $\operatorname {Mad}(G)$ , is the maximum among the average degrees of its subgraphs (i.e. $\operatorname {Mad}(G) = \max\{\frac{2|E(H)|}{|V(H)|} ; H \subseteq G \}$ ). We consider graphs G with $\operatorname {Mad}(G) < \frac{10}{3}$ , 3 and $\frac{14}{5}$ . These sets of graphs contain planar graphs with girth 5, 6 and 7 respectively. We prove in this paper that every graph G with maximum average degree m and maximum degree Δ has: λ p,q (G)≤(2q?1)Δ+6p+10q?8 if $m < \frac{10}{3}$ and p≥2q. λ p,q (G)≤(2q?1)Δ+4p+14q?9 if $m < \frac{10}{3}$ and 2q>p. λ p,q (G)≤(2q?1)Δ+4p+6q?5 if m<3. λ p,q (G)≤(2q?1)Δ+4p+4q?4 if $m < \frac{14}{5}$ . We give also some refined bounds for specific values of p, q, or Δ. By the way we improve results of Lih and Wang (SIAM J. Discrete Math. 17(2):264–275, 2003). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|