ridm@nrct.go.th   ระบบคลังข้อมูลงานวิจัยไทย   รายการโปรดที่คุณเลือกไว้

การสร้างกราฟและกราฟทิศทางที่สอดคล้องกับสมบัติที่กำหนด

หน่วยงาน สำนักงานกองทุนสนับสนุนการวิจัย

รายละเอียด

ชื่อเรื่อง : การสร้างกราฟและกราฟทิศทางที่สอดคล้องกับสมบัติที่กำหนด
นักวิจัย : วัชรพงษ์ อนันต์ชื่น
คำค้น : adjacency property , n-e.c. property , Palcy graph , paley digraph 2000 Mathematics Subject Classification : 05C75 : 05C20
หน่วยงาน : สำนักงานกองทุนสนับสนุนการวิจัย
ผู้ร่วมงาน : -
ปีพิมพ์ : 2547
อ้างอิง : http://elibrary.trf.or.th/project_content.asp?PJID=BRG4580015 , http://research.trf.or.th/node/308
ที่มา : -
ความเชี่ยวชาญ : -
ความสัมพันธ์ : -
ขอบเขตของเนื้อหา : -
บทคัดย่อ/คำอธิบาย :

ให้ m และ n เป็นจำนวนเต็มบวกหรือศูนย์ และ k เป็นจำนวนเต็มบวกใดๆ เรากล่าวว่ากราฟ G มีสมบัติP( m , n , k ) ก็ต่อเมื่อ สำหรับทุกๆ สับเซต A และ B ที่เป็นเซตต่างสมาชิกของจุดของ G โดยที่ IAI = m และ IBI = n จะมีอีกอย่างน้อย k จุด ซึ่งแต่ละจุดต่างประชิดกับจุดทุกจุดใน A แต่ไม่ประชิดกับจุดใดๆ ใน B เลย ยิ่งไปกว่านั้น เรากล่าวว่ากราฟ G มีสมบัติ n-existentially closed หรือกล่าวว่าเป็นกราฟ n-e.c.c ก็ต่อเมื่อ สำหรับทุกๆ สับเซต A และ B ของจุดของ G ซึ่ง A ? B = ? และ I A ?B I = n จะมีจุด u ? A ? B ชึ่งประชิดกับจุดทุกจุดใน A แต่ไม่ประชิดกับจุดใดๆ ใน B เลย เป็นที่ทราบกันดีว่ากราฟส่วนใหญ่มีสมบัติ P ( m , n , k ) และ n-e.c. แต่อย่างไรก็ตามปัญหาการสร้างกราฟที่มีสมบัติ P ( m , n , k ) และ n-e.c. เป็นปัญหาที่ค่อนข้างยาก ในงานวิจัยนี้เราจะแสดงว่านัยทั่วไปของกราฟพาเลย์ที่สร้างโดยการใช้ส่วนตกค้างกำลังสูงกว่าบนสนามจำกัด ที่มีจำนวนจุดมากพอมีสมบัติ P ( m , n , k ) และ n-e.c. ทฤษฎีบทที่คล้ายกันสำหรับนัยทั่วไปของกราฟทิศทางพาเลย์ก็ได้รับการนำเสนอกล่าวคือกราฟทิศทาง D มีสมบัติ n-e.c. ก็ต่อเมื่อ สำหรับทุกๆ สับเซต A และ B ของจุดของ D ซึ่ง A ? B = ? และ I A ?B I = n จะมีจุด u ? A ? B ซึ่งครอบครองจุดทุกจุดใน A และถูกครอบครองด้วยจุดทุกจุดใน B ในงานวิจัยนี้เราจะแสดงว่านัยทั่วไปของกราฟทิศทางพาเลย์ที่สร้างโดยการใช้ส่วนตกค้างกำลังสูงกว่าบนสนามจำกัด ที่มีจำนวนจุดมากพอมีสมบัติ n-e.c. Let m and n be non-negative integers and k a positive integer. A graph G is said to have property P ( m, n, k ) if for any disjoint subsets A and B of vertices of G with I A I = m and I B I = n there exist at least k other vertices, each of which is adjacent to every vertex of A but not adjacent to any vertex of B. Furthermore , a graph G is called n-existentially closed or n-e.c. if for any two subsets A and B of vertices of G with A ? B = ? and I A ?B I = n , there is a vertex u ? A ? B that is adjacent to every vertex of A but not adjacent to any vertex of B. It is well-known that almost an graphs satisfy the P ( m , n , k ) property and the n-e.c. property. However, the problem of constructing graphs with the P ( m , n , k ) property and the n-e.c. property seems difficult. In this report, we show that all sufficiently large generalized Paley graphs defined by using higher order residues on finite fields satisfy the P ( m , n , k ) property and the n-e.c. property. Similar results for generalized Paley digraphs are also obtained. More specifically , a digraph D is n-e.c. if for any two subsets A and B of vertices of D with A ? B = ? and I A ?B I = n ,there is a vertex u ? A ? B such that u dominates every vertex of A and dominated by every vertex of B. In this report, we show that the all sufficiently large generalized Paley digraphs defined by using higher order residues on finite fields are n-e.c.

บรรณานุกรม :
วัชรพงษ์ อนันต์ชื่น . (2547). การสร้างกราฟและกราฟทิศทางที่สอดคล้องกับสมบัติที่กำหนด.
    กรุงเทพมหานคร : สำนักงานกองทุนสนับสนุนการวิจัย.
วัชรพงษ์ อนันต์ชื่น . 2547. "การสร้างกราฟและกราฟทิศทางที่สอดคล้องกับสมบัติที่กำหนด".
    กรุงเทพมหานคร : สำนักงานกองทุนสนับสนุนการวิจัย.
วัชรพงษ์ อนันต์ชื่น . "การสร้างกราฟและกราฟทิศทางที่สอดคล้องกับสมบัติที่กำหนด."
    กรุงเทพมหานคร : สำนักงานกองทุนสนับสนุนการวิจัย, 2547. Print.
วัชรพงษ์ อนันต์ชื่น . การสร้างกราฟและกราฟทิศทางที่สอดคล้องกับสมบัติที่กำหนด. กรุงเทพมหานคร : สำนักงานกองทุนสนับสนุนการวิจัย; 2547.