Minimum rank of graphs

ค่าลำดับชั้นน้อยที่สุดของกราฟ

Name: Sarawut Rattanaprayoon

LCSH: Graph

LCSH: Minimum rank

Abstract: The minimum rank over a field F of a graph G is the smallest possible rank among all symmetric matrices over F whose ( i , j )th entry ( i ≠ j ) is nonzero whenever ij is an edge in G and is zero otherwise, where zero is the additive identity of F. A universally optimal matrix for a graph G is an integer symmetric matrix A such that every off-diagonal entry of A is 0, 1, or –1 and for all fields F, the rank of A is the minimum rank over F of G which is isomorphic to the graph of A. The fan graph, the book graph, the lotus graph and the hanging bridge graph are introduced and the minimum rank of these graphs over any field are presented. We use universally optimal matrices for these graphs to establish field independence of minimum rank. Examples verifying lack of field independence for some graphs are provided.

Abstract: ค่าลำดับชั้นน้อยที่สุดบนฟีลด์ F ของกราฟ G คือ ค่าลำดับชั้นน้อยที่สุดที่เป็นไปได้ในบรรดาเมทริกซ์สมมาตรบนฟีลด์ F ซึ่งสมาชิกแถวที่ i หลักที่ j (i ≠ j) ไม่เป็นศูนย์ ถ้า ij เป็นเส้นเชื่อมในกราฟ G และเป็นศูนย์ ถ้า ij ไม่เป็นเส้นเชื่อมในกราฟ G เมื่อ ศูนย์ คือ เอกลักษณ์การบวกบนฟีลด์ F เมทริกซ์เหมาะที่สุดเชิงเอกภพของกราฟ G คือ เมทริกซ์สมมาตร A ที่สมาชิกทุกตัวเป็นจำนวนเต็มแต่สมาชิกที่ไม่อยู่บนแนวทแยงมุมของเมทริกซ์ A คือ จำนวน 0, 1 หรือ –1 และสำหรับทุกฟีลด์ F ค่าลำดับชั้นของเมทริกซ์ A เท่ากับค่าลำดับชั้นน้อยที่สุดบนฟีลด์ F ของกราฟ G ซึ่ง สมสัณฐานกับกราฟของเมทริกซ์ A เราแนะนำกราฟพัด กราฟหนังสือ กราฟดอกบัว และกราฟสะพานแขวน และแสดงค่าลำดับชั้นน้อยที่สุดของกราฟเหล่านี้บนทุกฟีลด์ เราใช้เมทริกซ์เหมาะที่สุดเชิงเอกภพเพื่อแสดงว่าค่าลำดับชั้นน้อยที่สุดของกราฟเหล่านี้ไม่ขึ้นอยู่กับฟีลด์ และให้ตัวอย่างกราฟที่มีค่าลำดับชั้นน้อยที่สุดขึ้นอยู่กับฟีลด์

Chulalongkorn University. Office of Academic Resources

Address: BANGKOK

Email: cuir@car.chula.ac.th

Name: Wanida Hemakul

Role: advisor

Name: Thiradet Jiarasuksakun

Role: co-advisor

Created: 2009

Modified: 2014-02-28

Issued: 2014-02-28

วิทยานิพนธ์/Thesis

application/pdf

eng

DegreeName: Master of Science

Level: Master's Degree

Descipline: Mathematics

Grantor: Chulalongkorn University

©copyrights Chulalongkorn University

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	Sarawut_ra.pdf	2.61 MB	6	2022-04-17 13:29:12

ใช้เวลา

0.041093 วินาที