仙人掌圖的（3,1）－全標號

On (3,1)－Total Labeling of Cactus Graphs

陳明偉(Ming-Wei Chen)

指導教授 ： 史青林

中原大學/理學院/應用數學研究所/碩士(2013年)

https://doi.org/10.6840/CYCU.2013.00034

摘要

令G是一個圖。一個G的(p,1)-全標號是一個函數，指定整數到G的各個邊和點，使得G的任何相鄰點是不同的數字，G的任何相鄰邊是不同的數字，且一個點和它的相鄰邊之差的絕對值至少p。全標號的跨度是指兩個標號之間最大的差值。G的全標號中最小的跨度就是G的(p,1)-全標數，符號寫作λ_p^T(G)。一個仙人掌圖是一個每塊區塊都是邊或圈的連通圖。

在本篇論文中，我們將研究的重點鎖定在有限個圈交於共同點的這一類仙人掌圖的(3,1)-全標號並證明任一個屬於這一類的仙人掌圖G,它的(3,1)-全標數等於Δ+2，其中Δ是G的最大度。

關鍵字

仙人掌圖 ； 全標號

並列摘要

Let G be a graph. A (p,1)-total labeling of G is an assignment of integers to each vertex and edge of G such that any adjacent vertices of G are labeled with distinct integers, any adjacent edges of G are labeled with distinct integers and a vertex and its incident edge receive integers that differ by at least p in absolute value. The span of a (p,1)-total labeling of G is the maximum difference between two labels. The minimum span of (p,1)-total labeling of G is called the (p,1)-total number and denote by λ_p^T(G). A cactus graph is a connected graph in which every block is either edge or a cycle.

In this thesis, we focus on the (3,1)-total labeling for the class of cactus graphs containing finite cycles joined with a common cut-vertex and show that for any cactus graph G in this class, λ_3^T(G)=Δ+2 where Δ is the maximum degree of G.

並列關鍵字

cactus graph ； total labeling

參考文獻

[1] J. R. Griggs and R. K. Yeh, Labeling graphs with a condition at distance two, SIAM J Discrete Math 5 (1992), 586-595.

[2] F. Havet and M. L. Yu, (p,1)-total labeling of graphs, Discrete Math.308 (2008) 496-513.

[5] V. G. Vizing, On an estimate of the chromatic class of a -graph. Diskret Analiz. 3(1964), 25-30.

[7] M. A. Whittlesey, J. P. Georges and D. W. Mauro, On theλ-number of Qn and related graphs, SIAM J Discrete Math 8 (1995) , 449-506.

[3] N. Khan, M. Pal and A. Pal, (2,1)-Total Labeling of Cactus Graphs, communicated, (2010) 243-260.