Oriented bipartite graphs with minimal trace norm

Abstract

The trace norm of a digraph D is the trace norm of its adjacency matrix A (i.e. the sum of the singular values of A). In particular, when G is a graph then its trace norm is the well-known energy of G introduced by I. Gutman in 1978. In this paper, we address the following problem: among all orientations of a given bipartite graph, which has minimal trace norm? We show that the minimal trace norm is attained in sink-source orientations (i.e. orientations in which every vertex is a sink vertex or a source vertex). Consequently, if $\mathrm{\Omega }$ is a set of connected bipartite graphs with minimal energy G, then the sink-source orientations of G have minimal trace norm among all orientations of graphs in $\mathrm{\Omega }$. This is a consequence of our main result which relates the energy of a graph with the trace norm of its orientations. As another application we find the extremal values of the trace norm among all orientations of unicyclic graphs.

Keywords:

• Trace norm
• orientations of graphs
• digraphs
• bipartite
• unicyclic
• extremal values

AMS Subject Classifications:

• 05C50
• 15A18
• 05C20

Acknowledgements

The author (J.M.) wishes to thank the support of COLCIENCIAS and Becas COLCIENCIAS, Convocatoria No. 727 de 2015, in his process as a Ph.D. Student of Universidad de Antioquia. We are grateful to the anonymous referee for his/her valuable comments which improved this paper.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by COLCIENCIAS [727].