การกำหนดชื่อเชิงการจัดของกราฟพีเตอร์เซนทั่วไปและกราฟลอลลิพอพสำหรับบางกรณี Combinatorial Labelings of Generalized Petersen Graphs and Lollipop Graphs for Some Cases

สรศักดิ์ ลี้รัตนาวลี, กัณฐ์ญารัตธ์ ฐิติวัฒนาการ

Abstract


บทคัดย่อ

ให้ G=(V,E) เป็นกราฟเชิงเดียวและเชื่อมโยง มีจุดยอด n จุด และมีเส้น m เส้น โดย f. V ไปยัง {1,2,3,...n} เป็นการกำหนดชื่อจุดยอดให้กราฟ G เมื่อ f เป็นฟังก์ชันหนึ่งต่อหนึ่งและทั่วถึง ซึ่งนำไปสร้างฟังก์ชัน f^c จาก E ไปยัง N ที่เรียกว่าการกำหนดชื่อเส้นหรือการกำหนดชื่อเชิงการจัดของกราฟ G โดย เส้น uv อยู่ใน E ที่ f(u)>f(v) ถูกกำหนดชื่อเป็น f^c(uv) = C(f(u), f(v)) ถ้า f^c เป็นฟังก์ชันหนึ่งต่อหนึ่งแล้วเรียก f^c ว่าการกำหนดชื่อเชิงการจัดที่เหมาะสม และถ้ากราฟ G มีการกำหนดชื่อเชิงการจัดที่เหมาะสมแล้วเรียก G ว่าเป็นกราฟการจัดหมู่ ในบทความนี้แสดงว่ากราฟพีเตอร์เซนทั่วไป GP(n,3) และกราฟลอลลิพอพ H_{g,l} เมื่อ 3<=g<=6 และ g-1<=l เป็นกราฟการจัดหมู่

- - -

ABSTRACT

Suppose G(V, E) is a simple and connected graph with n vertices and m edges. A vertex-labeling is a bijective function f: V ® {1, 2, 3, …, n}. f induces a mapping f c: E ® ℕ  called the edge-labeling or combinatorial labeling of G. f c is defined by  for any edge uv Î E where f(u) > f(v). If f c is injective, we say that it is a valid combination labeling. If G has a valid combination labeling, then G is called a combination graph. In this article, Generalized Petersen graphs GP(n, 3) and Lollipop graphs Hg, l where 3 £ g £ 6 and g – 1 £ l are considered to be combination graphs.

 


Keywords


combinatorial labeling, Generalized Petersen graphs, Lollipop graphs, combination graphs

Full Text: PDF