Minimum skew-rank of small order graphs

This website provides the code and data files for the paper [1].

Throughout graphs are listed using graph6 format (see http://cs.anu.edu.au/~bdm/data/formats.html).

We say that a graph is reduced if it is connected, has neither isolated nor duplciate vertices. It is known that the minimum skew rank of a graph is the sum of the minimum skew ranks of its connected components, and hence it is typical to restrict one's attention to connected graphs. It is also known that the removal of isolated or duplicate vertices does not change the minimum skew rank of a graph. Thus, we restrict our attention to reduced graphs.

Minimum rank realizations for reduced graphs on small order

Each of the text files lists, one graph at a time, the reduced graphs of a given order in graph6 notation, followed by a skew-symmetric matrix of rank 4 with the given graph. The list of reduced graphs is obtained by applying the Nobarbell and Nodup algorithms given below to McKay's lists of connected graphs (http://cs.anu.edu.au/~bdm/data/graphs.html). These graphs are given in the following files.

Reduced graphs of order 6

Reduced graphs of order 7

Reduced graphs of order 8

Reduced graphs of order 9

Realizations of rank at most 4 for each reduced graph of order 6, 7, or 8 are given in

Order 6

Order 7

Order 8

These were done by hand for order 6, and using the left-nullspace technique from [1] for order 7 or 8. The code used to accomplish this is available upon request but is not provided here as these results are readily verifiable; namely, one checks that the set of reduced graphs is correct, for each graph in the list check that the given realization is skew-symmetric, has rank 4 and has the correct graph. This is accomplished with the SAGE code: TestingRealizations.

Concrete realizations for graphs of order 9 were not given. Rather for all but the reduced graph HEhbtjK on 9 vertices,the following is given in the file below: the reduced graph G in graph6, a realization B of G\9 of rank 4, a 4 by 8 matrix R whose rows are a basis of the left nullspace of B, and list of minimally dependent sets of columns R whose union is the neighbors of 9 in G. By Corollary 4.9 of [2], it follows that such a G has minimum skew rank at most 4. It is shown in the above mentioned paper that the graph HEHbtjK has minimum skew rank at least 6.

Order 9

The results for order 9 can be verified using the SAGE code: TestingforOrder9

Programs

Below are commented programs, written in SAGE, that were used.

nocodiamond

This function inputs a graph G and outputs true if and only if G is co-diamond free

nobarbell

This function inputs a graph G and outputs true if and only if G is 2K_3+e free and has no duplicate vertices

References

[1] Sudipta Mallik and Bryan Shader, Probabilistic Methods for minimum skew rank of graphs,

under review.

[2] Sudipta Mallik and Bryan L. Shader, Classes of graphs with minimum skew rank 4, Linear Algebra Appl. 439 (2013) 3643-3657.