×

\(L(p,q)\)-labelling of planar graphs with high maximum degree. (Chinese. English summary) Zbl 1158.05336

Summary: J.R. Griggs and R.K.-C. Yeh [SIAM J. Discrete Math. 5, No.4, 586–595 (1992; Zbl 0767.05080)]conjectured that \(\lambda(G;2,1) \leq \Delta^2\) for any simple graph. The \(L(p, q)\)-labelling number on planar graphs with high maximum degree is considered. It is proved that \(\lambda(G;p, q) \leq (2q-1)\Delta+6(p-q)\) for \(h_1\)-graph and \(\lambda(G;p, q) \leq (2q-1)\Delta+8p-6q-1\) for \(h_2\)-graph.

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
05C35 Extremal problems in graph theory

Citations:

Zbl 0767.05080
PDFBibTeX XMLCite