✦ LIBER ✦

Linearly independent vertices and minimum semidefinite rank

✍ Scribed by Philip Hackney; Benjamin Harris; Margaret Lay; Lon H. Mitchell; Sivaram K. Narayan; Amanda Pascoe

Publisher: Elsevier Science
Year: 2009
Tongue: English
Weight: 457 KB
Volume: 431
Category: Article
ISSN: 0024-3795
DOI: 10.1016/j.laa.2009.03.030

No coin nor oath required. For personal study only.

✦ Synopsis

We study the minimum semidefinite rank of a graph using vector representations of the graph and of certain subgraphs. We present a sufficient condition for when the vectors corresponding to a set of vertices of a graph must be linearly independent in any vector representation of that graph, and conjecture that the resulting graph invariant is equal to minimum semidefinite rank. Rotation of vector representations by a unitary matrix allows us to find the minimum semidefinite rank of the join of two graphs. We also improve upon previous results concerning the effect on minimum semidefinite rank of the removal of a vertex.

📜 SIMILAR VOLUMES

Unitary matrix digraphs and minimum semi

Unitary matrix digraphs and minimum semidefinite rank

✍ Yunjiang Jiang; Lon H. Mitchell; Sivaram K. Narayan 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 149 KB

Graphs with unique minimum edge dominati

Graphs with unique minimum edge dominating sets and graphs with unique maximum independent sets of vertices

✍ Jerzy Topp 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 816 KB

Topp, J., Graphs with unique minimum edge dominating sets and graphs with unique maximum independent sets of vertices, Discrete Mathematics 12 1 (1993) 199-210. A set I of vertices of a graph G is an independent set if no two vertices of I are adjacent. A set M of edges of G is an edge dominating s

A note on universally optimal matrices a

A note on universally optimal matrices and field independence of the minimum rank of a graph

✍ Liang-Hao Huang; Gerard J. Chang; Hong-Gwa Yeh 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 164 KB

For a simple graph G on n vertices, the minimum rank of G over a field F, written as mr F (G), is defined to be the smallest possible rank among all n × n symmetric matrices over F whose (i, j)th entry (for i / = j) is nonzero whenever {i, j} is an edge in G and is zero otherwise. A symmetric integ