Bounds on the nullity, the \(H\)-rank and the Hermitian energy of a mixed graph. (English) Zbl 1472.05104
Summary: Given an \(n\)-vertex graph \(G\) with maximum degree \(\Delta\), the mixed graph \(D_G\) is constructed from \(G\) by orienting some of its edges, where \(G\) is called the underlying graph of \(D_G\). Let \(r_H (D_G)\) be the \(H\)-rank of \(D_G\) and let \(\alpha (G)\) be the independence number of \(G\). In this paper, we firstly determine the maximum nullity of \(n\)-vertex mixed graphs with maximum degree \(\Delta\). The corresponding extremal graphs are identified. We secondly establish upper and lower bounds on \(r_H (D_G) + \alpha (G), r_H (D_G)-\alpha (G), r_H (D_G)/\alpha (G)\), respectively. Finally, we characterize the relationship between the Hermitian energy and the \(H\)-rank of a mixed graph.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C35 | Extremal problems in graph theory |
| 05C75 | Structural characterization of families of graphs |
References:
| [1] | West, DB., Introduction to graph theory (1996), Upper Saddle River, NJ: Prentice Hall, Inc., Upper Saddle River, NJ · Zbl 0845.05001 |
| [2] | Ali, DA; Gauci, JB; Sciriha, I., Nullity of a graph with a cut-edge, MATCH Commun Math Comput Chem, 76, 3, 771-791 (2016) · Zbl 1461.05117 |
| [3] | Aouchiche, M.; Hansen, P., On the nullity number of graphs, Electron J Graph Theory Appl, 5, 2, 335-346 (2017) · Zbl 1467.05134 · doi:10.5614/ejgta.2017.5.2.14 |
| [4] | Feng, ZM; Huang, J.; Li, SC, Relationship between the rank and the matching number of a graph, Appl Math Comput, 354, 411-421 (2019) · Zbl 1428.05190 |
| [5] | Gutman, I.; Triantafillou, I., Dependence of graph energy on nullity: a case study, MATCH Commun Math Comput Chem, 76, 3, 761-769 (2016) · Zbl 1461.05127 |
| [6] | Metelsky, Y.; Schemeleva, K.; Werner, F., A finite characterization and recognition of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 in the class of threshold graphs, Discuss Math Graph Theory, 37, 1, 13-28 (2017) · Zbl 1354.05094 · doi:10.7151/dmgt.1916 |
| [7] | Wang, L.; Ma, XB., Characterization of sub-long graphs of arbitrary rank, Linear Multilinear Algebra, 65, 7, 1427-1445 (2017) · Zbl 1368.05026 · doi:10.1080/03081087.2016.1242128 |
| [8] | Adiga, C.; Rakshith, BR; So, W., On the mixed adjacency matrix of a mixed graph, Linear Algebra Appl, 495, 223-241 (2016) · Zbl 1331.05132 · doi:10.1016/j.laa.2016.01.033 |
| [9] | Gong, SC., On the rank of a real skew symmetric matrix described by an oriented graph, Linear Multilinear Algebra, 65, 10, 1934-1946 (2017) · Zbl 1387.05149 · doi:10.1080/03081087.2016.1201082 |
| [10] | Lu, Y.; Wang, LG; Zhou, QN., Skew-rank of an oriented graph in terms of the rank and dimension of cycle space of its underlying graph, Filomat, 32, 4, 1303-1312 (2018) · Zbl 1499.05378 · doi:10.2298/FIL1804303L |
| [11] | Luo, WJ; Huang, J.; Li, SC., On the relationship between the skew-rank of an oriented graph and the rank of its underlying graph, Linear Algebra Appl, 554, 205-223 (2018) · Zbl 1392.05077 · doi:10.1016/j.laa.2018.04.032 |
| [12] | Qu, H.; Yu, GH., Bicyclic oriented graphs with skew-rank 2 or 4, Appl Math Comput, 258, 182-191 (2015) · Zbl 1338.05103 |
| [13] | Wong, D.; Ma, XB; Tian, FL., 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 · doi:10.1016/j.ejc.2015.12.005 |
| [14] | Guo, K.; Mohar, B., Hermitian adjacency matrix of digraphs and mixed graphs, J Graph Theory, 85, 1, 324-340 (2017) · Zbl 1365.05173 · doi:10.1002/jgt.22057 |
| [15] | Liu, JX; Li, XL., Hermitian-adjacency matrices and hermitian energies of mixed graphs, Linear Algebra Appl, 466, 182-207 (2015) · Zbl 1302.05106 · doi:10.1016/j.laa.2014.10.028 |
| [16] | Nikiforov, V., The energy of graphs and matrices, J Math Anal Appl, 320, 1472-1475 (2007) · Zbl 1113.15016 · doi:10.1016/j.jmaa.2006.03.072 |
| [17] | Chen, C.; Huang, J.; Li, SC., On the relation between the H-rank of a mixed graph and the matching number of its underlying graph, Linear Multilinear Algebra, 66, 9, 1853-1869 (2018) · Zbl 1392.05071 · doi:10.1080/03081087.2017.1374327 |
| [18] | Chen, C.; Li, SC; Zhang, MJ., Relation between the H-rank of a mixed graph and the rank of its underlying graph, Discrete Math, 342, 5, 1300-1309 (2019) · Zbl 1407.05144 · doi:10.1016/j.disc.2019.01.009 |
| [19] | Hu, D.; Li, XL; Liu, XG, The spectral distribution of random mixed graphs, Linear Algebra Appl, 519, 343-365 (2017) · Zbl 1357.05082 · doi:10.1016/j.laa.2017.01.011 |
| [20] | Tian, FL; Chen, L.; Chu, R., Rank of the Hermitian-adjacency matrix of a mixed graph in terms of matching number, Ars Combin, 137, 221-232 (2018) · Zbl 1474.05263 |
| [21] | Wang, GF; Li, SC; Wei, W., On the characteristic polynomials and H-ranks of the weighted mixed graphs, Linear Algebra Appl, 581, 383-404 (2019) · Zbl 1419.05107 · doi:10.1016/j.laa.2019.07.027 |
| [22] | Wang, Y.; Yuan, BJ; Li, SD, Mixed graphs with H-rank 3, Linear Algebra Appl, 524, 22-34 (2017) · Zbl 1361.05076 · doi:10.1016/j.laa.2017.02.037 |
| [23] | Wang, L.; Wong, D., Bounds for the matching number, the edge chromatic number and the independence number of a graph in terms of rank, Discrete Appl Math, 166, 276-281 (2014) · Zbl 1283.05226 · doi:10.1016/j.dam.2013.09.012 |
| [24] | Ma, XB; Wong, D.; Tian, FL., Skew-rank of an oriented graph in terms of matching number, Linear Algebra Appl, 495, 242-255 (2016) · Zbl 1331.05181 · doi:10.1016/j.laa.2016.01.036 |
| [25] | Wei, W.; Li, SC., Relation between the Hermitian energy of a mixed graph and the matching number of its underlying graph, Linear and Multilinear Algebra (2018) · Zbl 1392.05071 |
| [26] | Wong, D.; Wang, XL; Chu, R., Lower bounds of graph energy in terms of matching number, Linear Algebra Appl, 549, 276-286 (2018) · Zbl 1390.05139 · doi:10.1016/j.laa.2018.03.040 |
| [27] | Tian, FL; 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 · doi:10.1016/j.dam.2017.01.004 |
| [28] | Zhou, Q.; Wong, D.; Sun, DQ., 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 · doi:10.1016/j.laa.2018.06.025 |
| [29] | Ma, XB; Fang, XW., An improved lower bound for the nullity of a graph in terms of matching number, Linear Multilinear Algebra (2019) |
| [30] | Huang, J.; Li, SC; Wang, H., Relation between the skew-rank of an oriented graph and the independence number of its underlying graph, J Comb Optim, 36, 1, 65-80 (2018) · Zbl 1398.05093 · doi:10.1007/s10878-018-0282-x |
| [31] | Li, XL; Xia, W., Skew-rank of an oriented graph and independence number of its underlying graph, J Comb Optim, 38, 1, 268-277 (2019) · Zbl 1420.05133 · doi:10.1007/s10878-019-00382-5 |
| [32] | Wang, L.; Fang, XW., Upper bound of skew energy of an oriented graph in terms of its skew rank, Linear Algebra Appl, 569, 195-205 (2019) · Zbl 1411.05174 · doi:10.1016/j.laa.2019.01.020 |
| [33] | Li, SC; Zhang, SQ; Xu, BG., The relation between the H-rank of a mixed graph and the independence number of its underlying graph, Linear and Multilinear Algebra, 67, 11, 2230-2245 (2019) · Zbl 1422.05064 · doi:10.1080/03081087.2018.1488936 |
| [34] | Mohar, B., Hermitian adjacency spectrum and switching equivalence of mixed graphs, Linear Algebra Appl, 489, 324-340 (2016) · Zbl 1327.05215 · doi:10.1016/j.laa.2015.10.018 |
| [35] | Shen, XL; Hou, YP; Zhang, CY., Bicyclic digraphs with extremal skew energy, Electron J Linear Algebra, 23, 340-355 (2012) · Zbl 1253.05076 |
| [36] | Haranta, J.; Schiermeyer, I., Note on the independence number of a graph in terms of order and size, Discrete Math, 232, 131-138 (2001) · Zbl 1030.05091 · doi:10.1016/S0012-365X(00)00298-3 |
| [37] | Cvetković, D.; Gutman, I., The algebraic multiplicity of the number zero in the spectrum of a bipartite graph, Mat Vesnik, 9, 24, 141-150 (1972) · Zbl 0263.05125 |
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.
