We study the local list number of graphs introduced by Lennerstad and Eriksson. A labelling of a graph on n vertices is a bijection from vertex set to the set {1,…, n}. Given such a labelling c a vertex u is distance consistent if for all vertices v and w |c(u)-c(v)|=|c(u)-c(w)|+1 implies d(u,w)≤ d(u,v). A graph G is k-distance consistent if there is a labelling with k distance-consistent vertices. The local list number of a graph G is the largest k such that G is k-distance consistent. We determine the local list number of cycles, complete bipartite graphs and some trees as well as prove bounds for some families of trees. We show that the local list number of even cycles is two, and of odd cycles is three. We also show that, if k, l≥ 3 , the complete bipartite graph Kk,l has local list number one, the star graph Sn=K1,n has local list number 3, and K2,k has local list number 2. Finally, we show that for each n≥3 and each k such that 3≤k≤n there is a tree with local list number k. / Vi studerar det lokala listtalet introducerat av Lennerstad och Eriksson. En märkning av en graf på n hörn är en bijektion från hörnmängden till mängden {1, . . . , n}. Givet en sådan märkning c är ett hörn u avståndskonsistent om för alla hörn v och w |c(u) − c(v)| = |c(u) − c(w)| = 1 implicerar d(u, w) ≤d(u, v). En graf G är k-avståndskonsistent om det nns en märkning med k avståndskonsistenta hörn. Det lokala listtalet av en graf G är det största k sådan att G är k -avståndskonsistent. Vi bestämmer den lokala listtalet av cykler, kompletta bipartita grafer och vissa träd och visar som gränser för några familjer av träd. Vi visar att det lokla listtalet av jämna cykler är två, och av udda cykler är tre. Vi visar också att, om k, l ≥ 3, den kompletta bipartita grafen Kk,l har lokalt listtal ett, stjärngrafen Sn = K1,n har lokalt listtal 3, och K2,k har lokalt listtal 2. Slutligen, visar vi att för varje n≥3 och varje k sådant att 3 ≤ k≤n finns ett träd med lokalt listtal k.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:liu-199624 |
| Date | January 2023 |
| Creators | Henricsson, Anders |
| Publisher | Linköpings universitet, Algebra, geometri och diskret matematik, Linköpings universitet, Tekniska fakulteten |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0015 seconds