Invertible and pseudoinvertible simple connected graphs.
Their spectra, positive and negative (pseudo)invertibility

Soňa Pavlíková and Daniel Ševčovič

http://www.iam.fmph.uniba.sk/institute/sevcovic/inversegraphs/

By \(G_B\) we denorte a simple graph with an adjacency matrix \(B\). The following definitions and notions of integrally invertible positively and negatively graphs were introduced in [1], [2], [3].

Definition 1. A graph \(G_B\) is called positively (negatively) integrally invertible if \(det(B)=\pm 1\) and \(B^{-1}\) is signable to a nonnegative (nonpositive) integral matrix. If \(D\) is the corresponding signature matrix, the positive (negative) inverse graph \(H=G_B^{-1}\) is defined by the nonnegative integral adjacency matrix \(B_H=D B^{-1} D\) (\(B_H= - DB^{-1} D\) ).

Definition 2. A graph \(G_B\) is called positively (negatively) pseudoinvertible if the Moore-Penrose pseudoinverse matrix \(B^{\dagger}\) is signable to a nonnegative (nonpositive) matrix. If \(D\) is the corresponding signature matrix, the positive (negative) pseudoinverse graph \(H=G_B^{\dagger}\) is defined by the nonnegative weighted adjacency matrix \(B_H=D B^{\dagger} D\) (\(B_H= - DB^{\dagger} D\) )

The list of all connected graphs on \(m\le 10\) was constructed using McKay's list [4]. The complete list of positively/negatively integrally invertible and pseudoinvertible graphe is based on our own computations [3]

Summary report of positively (negatively) integrally invertible and positively (negatively) pseudoinvertible graphs:

Format of outputs:

graf 15, 
signabilita +1 -1, 
determinant = 1.000000, 
spectrum = -1.9319, -1.0000, -0.5176, 0.5176, 1.0000, 1.9319, ; 
B = [[0 0 0 1 0 1 ];[0 0 0 0 1 1 ];[0 0 0 0 0 1 ];[1 0 0 0 0 0 ];[0 1 0 0 0 0 ];[1 1 1 0 0 0 ];];    
Dpos = [[1 0 0 0 0 0 ];[0 1 0 0 0 0 ];[0 0 -1 0 0 0 ];[0 0 0 1 0 0 ];[0 0 0 0 1 0 ];[0 0 0 0 0 -1 ];];    
Dneg = [[-1 0 0 0 0 0 ];[0 -1 0 0 0 0 ];[0 0 1 0 0 0 ];[0 0 0 1 0 0 ];[0 0 0 0 1 0 ];[0 0 0 0 0 -1 ];];

Matlab command to display graph from adjacency matrix B:

plot(graph(B), 'LineWidth', 3, 'MarkerSize',10, 'NodeColor', 'b', 'NodeLabel','' ); axis off;

Examples:

Examples of pseudoinvertible graphs on 5 vertices with a singular or non-integrally invertible adjacency matrix

m=5 vertices, graph ID=3, positively pseudoinvertible graph \(det(B)=0\)	m=5 vertices, graph ID=16, negatively pseudoinvertible graph \(det(B)=2\)	m=5 vertices, graph ID=1, positively and negatively pseudoinvertible graph \(det(B)=0\)

Examples of invertible graphs on 6 vertices with an integrally invertible adjacency matrix

m=6 vertices, graph ID=16, positively integrally invertible graph	m=6 vertices, graph ID=29, negatively integrally invertible graph	m=6 vertices, graph ID=15, positively and negatively integrally invertible graph

Examples of pseudoinvertible graphs on 6 vertices with a singular adjacency matrix

m=6 vertices, graph ID=3, positively pseudoinvertible graph \(det(B)=0\)	m=6 vertices, graph ID=43, negatively pseudoinvertible graph \(det(B)=0\)	m=6 vertices, graph ID=1, positive and negatively pseudoinvertible graph \(det(B)=0\)

Examples of pseudoinvertible graphs on 9 vertices with a singular adjacency matrix

m=9 vertices, graph ID=4, positively pseudoinvertible graph \(det(B)=0\)

Examples of pseudoinvertible graphs on 10 vertices with a singular adjacency matrix

m=10 vertices, graph ID=54, negatively pseudoinvertible graph \(det(B)=0\)	m=10 vertices, graph ID=1, positively pseudoinvertible graph \(det(B)=0\)

References:

[1] S. Pavlíková, D. Ševčovič: On a Construction of Integrally Invertible Graphs and their Spectral Properties,  Linear Algebra and its Applications, 532 (2017), 512-533.
PDF file    arXiv 1707.02210  DOI: 10.1016/j.laa.2017.07.005

[2] S. Pavlíková, D. Ševčovič: Maximization of the Spectral Gap for Chemical Graphs by means of a Solution to a Mixed Integer Semidefinite Program, Computer Methods in Materials Science, 4 2016, 169-176.
PDF file     arXiv 1611.06959

[3] S. Pavlíková, D. Ševčovič: On the Moore-Penrose pseudoinversion of block symmetric matrices and its application in spectral gap maximization

[4] McKay's list of all connected simple graphs http://users.cecs.anu.edu.au/~bdm/data/graphs.html