Upper bound of skew energy of an oriented graph in terms of its skew rank. (English) Zbl 1411.05174
Summary: Let \(G^\sigma\) be an oriented graph with skew adjacency matrix \(S(G^\sigma)\). The skew energy \(\mathcal{E}_s(G^\sigma)\) of \(G^\sigma\) is the sum of the norms of all eigenvalues of \(S(G^\sigma)\) and the skew rank \(r_s(G^\sigma)\) of \(G^\sigma\) is the rank of \(S(G^\sigma)\). F. Tian and D. Wong [Discrete Appl. Math. 222, 179–184 (2017; Zbl 1396.05078)] gave a lower bound of \(\mathcal{E}_s(G^\sigma)\) in terms of its skew rank. They proved that \(r_s(G^\sigma) \leq \mathcal{E}_s(G^\sigma)\) and they characterized the oriented graphs which satisfy the equality.
In this paper, we aim to establish an upper bound for skew energy of an oriented graph in terms of its skew rank and maximum vertex degree.
It is proved that \(\mathcal{E}_s(G^\sigma)\leq r_s(G^\sigma) \Delta\) for an arbitrary oriented graph \(G^\sigma\) with maximum degree \(\Delta\), and the upper bound is attained if and only if \(G^\sigma\) is the disjoint union of \(\frac{r_s(G^\sigma)}{2}\) copies of \((K_{\Delta, \Delta})^\sigma\) together with some isolated vertices, where the orientation \(\sigma\) is switching-equivalent to the elementary orientation of \(K_{\Delta, \Delta}\) which assigns all edges the same direction from a chromatic set to another one.
In this paper, we aim to establish an upper bound for skew energy of an oriented graph in terms of its skew rank and maximum vertex degree.
It is proved that \(\mathcal{E}_s(G^\sigma)\leq r_s(G^\sigma) \Delta\) for an arbitrary oriented graph \(G^\sigma\) with maximum degree \(\Delta\), and the upper bound is attained if and only if \(G^\sigma\) is the disjoint union of \(\frac{r_s(G^\sigma)}{2}\) copies of \((K_{\Delta, \Delta})^\sigma\) together with some isolated vertices, where the orientation \(\sigma\) is switching-equivalent to the elementary orientation of \(K_{\Delta, \Delta}\) which assigns all edges the same direction from a chromatic set to another one.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C75 | Structural characterization of families of graphs |
Citations:
Zbl 1396.05078References:
| [1] | Adiga, C.; Balakrishnan, R.; So, W., The skew energy of a digraph, Linear Algebra Appl., 432, 1825-1835 (2010) · Zbl 1217.05131 |
| [2] | Akbari, S.; Ghorbani, E.; Zare, S., Some relations between rank, chromatic number and energy of graphs, Discrete Math., 309, 601-605 (2009) · Zbl 1194.05075 |
| [3] | Anuradha, A.; Balakrishnan, R.; Chen, X.; Li, X.; Lian, H.; So, W., Skew spectra of oriented bipartite graphs, Electron. J. Combin., 20, Article P18 pp. (2013) · Zbl 1295.05114 |
| [4] | Cavers, M.; Cioaba, S. M.; Fallat, S.; Gregory, D. A.; Haemers, W. H.; Kirkland, S. J.; McDonald, J. J.; Tsatsomeros, M., Skew-adjacency matrices of graphs, Linear Algebra Appl., 436, 4512-4529 (2012) · Zbl 1241.05070 |
| [5] | Chen, X.; Li, X.; Lian, H., 4-Regular oriented graphs with optimum skew energy, Linear Algebra Appl., 439, 2948-2960 (2013) · Zbl 1282.05102 |
| [6] | Chen, X.; Li, X.; Lian, H., Lower bounds of the skew spectral radii and skew energy of oriented graphs, Linear Algebra Appl., 479, 91-105 (2015) · Zbl 1315.05084 |
| [7] | Cui, D.; Hou, Y., On the skew spectra of Cartesian products of graphs, Electron. J. Combin., Article P19 pp. (2013) · Zbl 1266.05132 |
| [8] | Godsil, C.; Royle, G., Algebraic Graph Theory, Grad. Texts in Math., vol. 207 (2001), Springer-Verlag: Springer-Verlag New York, Berlin, Heidelberg · Zbl 0968.05002 |
| [9] | Gong, S.; Li, X.; Xu, G., On oriented graphs with minimal skew energy, Electron. J. Linear Algebra, 27, 691-704 (2014) · Zbl 1320.05074 |
| [10] | Gong, S.; Xu, G., 3-Regular digraphs with optimum skew energy, Linear Algebra Appl., 436, 465-471 (2012) · Zbl 1235.05087 |
| [11] | Gong, S.; Zhong, W.; Xu, G., 4-regular oriented graphs with optimum skew energies, European J. Combin., 36, 77-85 (2014) · Zbl 1284.05161 |
| [12] | Hou, Y.; Lei, T., Characteristic polynomials of skew-adjacency matrices of oriented graphs, Electron. J. Combin., 18, Article P156 pp. (2011) · Zbl 1236.05093 |
| [13] | Hou, Y.; Shen, X.; Zhang, C., Oriented unicyclic graphs with extremal skew energy |
| [14] | Li, X.; Yu, G., The skew-rank of oriented graphs, Sci. Sin., Math., 45, 93-104 (2015) · Zbl 1488.05222 |
| [15] | Li, X.; Lian, H., Skew-spectra and skew energy of various products of graphs, Trans. Comb., 4, 2, 13-21 (2015) · Zbl 1463.05345 |
| [16] | Ma, X.; Wong, D.; Tian, F., Skew-rank of an oriented graph in terms of matching number, Linear Algebra Appl., 495, 242-255 (2016) · Zbl 1331.05181 |
| [17] | Ma, X.; Wong, D., The nullity of k-cyclic graphs of infinity-type, Linear Multilinear Algebra, 63, 2200-2211 (2015) · Zbl 1328.05107 |
| [18] | Qu, H.; Yu, G., Bicyclic oriented graphs with skew-rank 2 or 4, Appl. Math. Comput., 258, 182-191 (2015) · Zbl 1338.05103 |
| [19] | Shen, X.; Hou, Y.; Zhang, C., Bicyclic digraphs with extremal skew energy, Electron. J. Linear Algebra, 23, 340-355 (2012) · Zbl 1253.05076 |
| [20] | Tian, F.; Wong, D., Relation between the skew energy of an oriented graph and its matching number, Discrete Appl. Math., 222, 179-184 (2017) · Zbl 1396.05078 |
| [21] | Tian, F.; Wang, D.; Zhu, M., A characterization of signed planar graphs with rank at most 4, Linear Multilinear Algebra, 64, 807-817 (2016) · Zbl 1335.05079 |
| [22] | Wang, J.; Zhao, L.; Ye, C., Bicyclic oriented graphs with the second largest skew-energy, Linear Algebra Appl., 459, 43-57 (2014) · Zbl 1300.05165 |
| [23] | Wong, D.; Ma, X.; Tian, F., Relation between the skew-rank of an oriented graph and the rank of its underlying graph, European J. Combin., 54, 76-86 (2016) · Zbl 1331.05097 |
| [24] | Wong, D.; Zhu, M.; Lv, W., A characterization of long graphs of arbitrary rank, Linear Algebra Appl., 438, 1347-1355 (2013) · Zbl 1257.05090 |
| [25] | Wong, D.; Wang, X.; Chu, R., Lower bounds of graph energy in terms of matching number, Linear Algebra Appl., 549, 276-286 (2018) · Zbl 1390.05139 |
| [26] | Yang, X.; Gong, S.; Xu, G., Minimal skew energy of oriented unicyclic graphs with fixed diameter, J. Inequal. Appl., 418, 1-11 (2013) · Zbl 1291.05128 |
| [27] | Zhu, J., Oriented unicyclic graphs with the first \(\lfloor \frac{n - 9}{2} \rfloor\) largest skew energies, Linear Algebra Appl., 437, 2630-2649 (2012) · Zbl 1252.05140 |
| [28] | Zhou, Q.; Wong, D.; Sun, D., A lower bound for graph energy, Published online: 01 Dec 2018 |
| [29] | Zhou, Q.; Wong, D.; Sun, D., An upper bound of the nullity of a graph in terms of order and maximum degree, Linear Algebra Appl., 555, 314-320 (2018) · Zbl 1395.05105 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
