错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On list (p, 1)-total labellings of special planar graphs and 1-planar graphs

  • Lin Sun,
  • Guanglong Yu,
  • Jianliang Wu

摘要

A (p, 1)-total labelling of a graph G is a mapping f: \(V(G)\cup E(G)\) V ( G ) E ( G ) \(\rightarrow \) \(\{0, 1, \cdots , k\}\) { 0 , 1 , , k } such that \(|f(u)-f(v)|\ge 1\) | f ( u ) - f ( v ) | 1 if \(uv\in E(G)\) u v E ( G ) , \(|f(e_1)-f(e_2)|\ge 1\) | f ( e 1 ) - f ( e 2 ) | 1 if \(e_1\) e 1 and \(e_2\) e 2 are two adjacent edges in G and \(|f(u)-f(e)|\ge p\) | f ( u ) - f ( e ) | p if the vertex u is incident with the edge e. In this paper, we focus on the list version of a (p, 1)-total labelling. Given a family \(L=\{L(u)\subseteq \mathbb {N}:u\in V(G)\cup E(G)\}\) L = { L ( u ) N : u V ( G ) E ( G ) } , an L-list (p, 1)-total labelling of G is a (p, 1)-total labelling f of G such that \(f(u)\in L(u)\) f ( u ) L ( u ) for every element \(u\in V(G)\cup E(G)\) u V ( G ) E ( G ) . A graph G is said to be (p, 1)-k-total choosable if it admits an L-list (p, 1)-total labelling whenever the family L contains only sets of size at least k. The smallest k for which a graph G is (p, 1)-k-total choosable is the list (p, 1)-total labelling number of G, denoted by \(\lambda _{lp}^T(G)\) λ lp T ( G ) . In this paper, we firstly use some important theorems related to Combinatorial Nullstellensatz to prove that the upper bound of \(\lambda _{lp}^T(C_n)\) λ lp T ( C n ) for cycles \(C_n\) C n is \(2p+1\) 2 p + 1 with \(p\ge 2\) p 2 . Let G be a graph with maximum degree \(\Delta (G)\ge 6p+3\) Δ ( G ) 6 p + 3 . Then we prove that if G is a planar graph or a 1-planar graph without adjacent 3-cycles, then \(\lambda _{lp}^T(G)\le \Delta (G)+2p-1\) λ lp T ( G ) Δ ( G ) + 2 p - 1 ( \(p\ge 2\) p 2 ).