The game L (d, 1) -labeling problem of graphs

Please use this identifier to cite or link to this item: https://ir.lib.ncu.edu.tw/handle/987654321/109294

Title:	The game L (d, 1) -labeling problem of graphs
Authors:	廖勝強;Chia, Ma-Lian;Hsu, Huei-Ni;Kuo, David;Liaw, Sheng-Chyang;Xu, Zi-teng
Contributors:	理學院數學系
Keywords:	Complete bipartite graphs;Complete graphs;Game [formula omitted]-labeling
Date:	2012-10-28
Issue Date:	2026-04-23 16:24:28 (UTC+8)
Publisher:	Elsevier;Elsevier B.V
Abstract:	摘要： Let G be a graph and let k be a positive integer. Consider the following two-person game which is played on G: Alice and Bob alternate turns. A move consists of selecting an unlabeled vertex v of G and assigning it a number a from {0,1,2,…,k} satisfying the condition that, for all u∈V(G),u is labeled by the number b previously, if d(u,v)=1, then \|a−b\|≥d, and if d(u,v)=2, then \|a−b\|≥1. Alice wins if all the vertices of G are successfully labeled. Bob wins if an impasse is reached before all vertices in the graph are labeled. The gameL(d,1)-labeling number of a graph G is the least k for which Alice has a winning strategy. We use λ̃1d(G) to denote the game L(d,1)-labeling number of G in the game Alice plays first, and use λ̃2d(G) to denote the game L(d,1)-labeling number of G in the game Bob plays first. In this paper, we study the game L(d,1)-labeling numbers of graphs. We give formulas for λ̃1d(Kn) and λ̃2d(Kn), and give formulas for λ̃1d(Km,n) for those d with d≥max{m,n}. 出版者： Elsevier B.V 出版日期： 2012-10-28 出處： Discrete mathematics, 2012-10, Vol.312 (20), p.3037-3045 資源來源： Elsevier ScienceDirect Journals Complete 版權： 2012 Elsevier B.V. 識別號： ISSN: 0012-365X 識別號： EISSN: 1872-681X 識別號： DOI: 10.1016/j.disc.2012.07.002
Appears in Collections:	[Department of Mathematics] journal & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	9	View/Open

社群 sharing

Loading...