Chulalongkorn University Theses and Dissertations (Chula ETD)

Minimum rank of graphs

Other Title (Parallel Title in Other Language of ETD)

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

Year (A.D.)

2009

Document Type

Thesis

First Advisor

Wanida Hemakul

Second Advisor

Thiradet Jiarasuksakun

Faculty/College

Faculty of Science (คณะวิทยาศาสตร์)

Degree Name

Master of Science

Degree Level

Master's Degree

Degree Discipline

Mathematics

DOI

10.58837/CHULA.THE.2009.1203

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.

Other Abstract (Other language abstract of ETD)

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

Link to Full Text

Share

COinS