| Author Name | Affiliation | | Baogen Xu | Department of Mathematics, East China Jiaotong University, Nanchang, Jiangxi 330013, China | | Chunhua Li | Department of Mathematics, East China Jiaotong University, Nanchang, Jiangxi 330013, China | | Zhizhu Fan | Department of Mathematics, East China Jiaotong University, Nanchang, Jiangxi 330013, China |
|
| Abstract: |
| LetG=(V,E) be a connected graph andW={w1,w2,…,wk} be an ordered subset ofV(G). For any vertexv∈V, the locating code ofv with respect toW is thekvectorCW(v)={d(v,w1),d(v,w2),…,d(v,wk)},W is said to be a locating set ofG if distinct vertices have the distinct locating code, and the locating number ofG is defined as:Loc(G)=min{|W|:W is a locating set of G}.We study the locating set and locating number of a graphG, obtain some bounds for the locating numbers of graphs, and determine the exact value ofLoc(G) for some special classes of graphs, such as cycles, wheels, completet partite graph and some Cartesian products of paths and cycles. In addition, we also prove thatLoc(T)≥Δ－1 holds for all treesT with maximum degreeΔ, and shows a treeT withLoc(T)=Δ－1. |
| Key words: graph locating code locating set locating number Cartesian products O157.5 |
| DOI：10.11916/j.issn.1005-9113.16198 |
| Clc Number:O157.5 |
| Fund: |
|
| Descriptions in Chinese: |
| 关于图的定位数 徐保根，李春华，范自柱 （华东交通大学 数学系，江西 南昌 30013）中文说明：设G=(V,E)为一个连通图， W={w1,w2,…,wk} 为V(G)上的一个有序子集，对于每个点v∈V， v点相对于W的定位码为一个k-维向量 CW(v)={d(v,w1),d(v,w2),…,d(v,wk)}，如果不同顶点具有不同的定位码，则称W为图G的一个定位集，图G的定位数定义为Loc(G)=min{|W|:W为图 G的一个定位集} 。 本文研究了图的定位集与定位数问题，获得了关于图的定位数的一些界限，对一些特殊图类给出其定位数的确切值，包括圈、轮图、完全t- 部图、路与圈的乘积图。此外也证明了Loc(T)≥Δ－1对一切最大度为Δ的树T均成立，并构造一棵满足Loc(T)=Δ－1的树T 。 关键词：图，定位码，定位集，定位数，笛卡尔积
|
