Search

Advanced Search

Find results with:

Add another field

Search by date

to

Searching collections:

Institutional Repository

Add or remove collections

Home Graphs Whose Minimal Rank is Two: The Finite Fields Case

Rate

To link to this object, paste this link in email, IM or document

To embed this object, paste this HTML in website

Graphs Whose Minimal Rank is Two: The Finite Fields Case

View Description

Download

small (250x250 max)

medium (500x500 max)

large ( > 500x500)

Full Resolution

Print

PDF
Text

Description

Rating
Permanent URL	http://hdl.lib.byu.edu/1877/1483
Title	Graphs Whose Minimal Rank is Two: The Finite Fields Case
BYU Creator	Barrett, Wayne
Creator	Van Der Holst, Hein Loewy, Raphael
Keywords	Rank 2; Minimum rank; Symmetricma trix; Forbidden subgraph; Bilinear symmetric form; Finite field
Description/Abstract	Let F be a finite field, G = (V,E) be an undirected graph on n vertices, and let S(F,G) be the set of all symmetric n × n matrices over F whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. Let mr(F,G) be the minimum rank of all matrices in S(F,G). If F is a finite field with p^t elements, p does not = 2, it is shown that mr(F,G) ≤ 2 if and only if the complement of G is the join of a complete graph with either the union of at most (p^t+1)/2 nonempty complete bipartite graphs or the union of at most two nonempty complete graphs and of at most (p^t + 1)/2 nonempty complete bipartite graphs. These graphs are also characterized as those for which 9 specific graphs do not occur as induced subgraphs. If F is a finite field with 2t elements, then mr(F,G) ≤ 2 if and only if the complement of G is the join of a complete graph with either the union of at most 2^t +1 nonempty complete graphs or the union of at most one nonempty complete graph and of at most 2^t-1 nonempty complete bipartite graphs. A list of subgraphs that do not occur as induced subgraphs is provided for this case as well.
Source	Barrett, Wanye, Van Der Holst, Hein, and Loewy, Raphael, Graphs Whose Minimal Rank is Two: The Finite Fields case, Elec. Journal of Linear Algebra (2005): Vol. 14 p. 32-42.;
Publisher	International Linear Algebra Society
Date Original	2005-02
Language	English eng en
Publication Type	Articles
Type	Text
Format	application/pdf
Owning Institution	Brigham Young University
BYU College	College of Physical and Mathematical Sciences
BYU Department	Mathematics
Copyright Status	(c) 2005 American Mathematical Society;
Copyright Use Information	http://www.lib.byu.edu/generic_copyright.html

Tags

Add tags for Graphs Whose Minimal Rank is Two: The Finite Fields Case

View as list | View as tag cloud | report abuse

Comments

Post a Comment for Graphs Whose Minimal Rank is Two: The Finite Fields Case

you wish to report:

Your comment:

Your Name:

Submit

Cancel

...

Powered by CONTENTdm®