×

Some mixed graphs with \(H\)-rank 4, 6 or 8. (English) Zbl 1464.05256

Summary: The \(H\)-rank of a mixed graph \(G^{\alpha}\) is defined to be the rank of its Hermitian adjacency matrix \(H(G^{\alpha})\). If \(G^{\alpha}\) is switching equivalent to a mixed graph \((G^{\alpha})^\prime\), and two vertices \(u\), \(v\) of \(G^{\alpha}\) have exactly the same neighborhood in \((G^{\alpha})^\prime\), then \(u\) and \(v\) are said to be twins. The twin reduction graph \(T_{G^{\alpha}}\) of \(G^{\alpha}\) is a mixed graph whose vertices are the equivalence classes, and \([u][v]\in E(T_{G^{\alpha}})\) if \(uv\in E((G^{\alpha})^\prime)\), where \([u]\) denotes the equivalence class containing the vertex \(u\). In this paper, we give the upper (resp., lower) bound of the number of vertices of the twin reduction graphs of connected mixed bipartite graphs, and characterize all twin reduction graphs of the connected mixed bipartite graphs with \(H\)-rank 4 (resp., 6 or 8). Then, we characterize all connected mixed graphs with \(H\)-rank 4 (resp., 6 or 8) among all mixed graphs containing induced mixed odd cycles whose lengths are no less than 5 (resp., 7 or 9).

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bapat, RB, Graphs and matrices. Universitext (2010), London: Springer, London · Zbl 1248.05002 · doi:10.1007/978-1-84882-981-7
[2] Brown, M.; Kennedy, JW; Servatius, B., Graph singularity, Graph Theory Notes N. Y., 25, 23-32 (1993)
[3] Chang, GJ; Huang, LH; Yeh, HG, A characterization of graphs with rank 4, Linear Algebra Appl, 434, 8, 1793-1798 (2011) · Zbl 1216.05071 · doi:10.1016/j.laa.2010.09.040
[4] Chang, GJ; Huang, LH; Yeh, HG, A characterization of graphs with rank 5, Linear Algebra Appl, 436, 11, 4241-4250 (2012) · Zbl 1241.05062 · doi:10.1016/j.laa.2012.01.021
[5] 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
[6] 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
[7] Collatz, L.; Sinogowitz, U., Spektren endlicher Grafen, Abh Math Sem Univ dui Hamburg, 21, 63-77 (1957) · Zbl 0077.36704 · doi:10.1007/BF02941924
[8] Feng, ZM; Huang, J.; Li, SC; Luo, XB, Relationship between the rank and the matching number of a graph, Appl Math Comput, 354, 411-421 (2019) · Zbl 1428.05190
[9] Guo, K.; Mohar, B., Hermitian adjacency matrix of digraphs and mixed graphs, J Graph Theory, 85, 217-248 (2017) · Zbl 1365.05173 · doi:10.1002/jgt.22057
[10] Guo, K.; Mohar, B., Digraphs with Hermitian spectral radius below 2 and their cospectrality with paths, Discrete Math, 340, 11, 2616-2632 (2017) · Zbl 1369.05092 · doi:10.1016/j.disc.2017.01.018
[11] Gutman I, Borovićanin B (2011) Nullity of graphs: an updated survey. In: Selected topics on applications of graph spectra. Zb Rad (Beogr), vol 14, no 22, pp 137-154 · Zbl 1289.05287
[12] He, SJ; Hao, RX; Lai, HJ, Bounds for the matching number and cyclomatic number of a signed graph in terms of rank, Linear Algebra Appl, 572, 273-291 (2019) · Zbl 1411.05107 · doi:10.1016/j.laa.2019.03.012
[13] 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
[14] 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
[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] Lu, Y.; Wang, LG; Zhou, QN, Bicyclic oriented graphs with skew-rank 6, Appl Math Comput, 270, 899-908 (2015) · Zbl 1410.05080
[17] Lu, Y.; Wang, LG; Xiao, P., Complex unit gain bicyclic graphs with rank 2, 3 or 4, Linear Algebra Appl, 523, 169-186 (2017) · Zbl 1370.05139 · doi:10.1016/j.laa.2017.02.031
[18] Lu, Y.; Wang, LG; Zhou, QN, The rank of a signed graph in terms of the rank of its underlying graph, Linear Algebra Appl, 538, 166-186 (2018) · Zbl 1374.05133 · doi:10.1016/j.laa.2017.10.013
[19] Lu, Y.; Wang, LG; Zhou, QN, The rank of a complex unit gain graph in terms of the rank of its underlying graph, J Comb Optim, 38, 2, 570-588 (2019) · Zbl 1420.05087 · doi:10.1007/s10878-019-00397-y
[20] 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
[21] 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
[22] Qu, H.; Yu, GH, Bicyclic oriented graphs with skew-rank 2 or 4, Appl Math Comput, 258, 182-191 (2015) · Zbl 1338.05103
[23] Rosàrio, F.; Cecília, P., The minimum rank of matrices and the equivalence class graph, Linear Algebra Appl, 427, 161-170 (2007) · Zbl 1129.15002 · doi:10.1016/j.laa.2007.07.002
[24] Sciriha, I., A characterization of singular graphs, Electron J Linear Algebra, 16, 451-462 (2007) · Zbl 1142.05344 · doi:10.13001/1081-3810.1215
[25] Wang CJ (2017) The nullity of unicyclic and bicyclic mixed graphs. Master thesis, Anhui University
[26] Wang, Y.; Yuan, BJ; Li, SD; Wang, CJ, Mixed graphs with \(H\)-rank 3, Linear Algebra Appl, 524, 22-34 (2017) · Zbl 1361.05076 · doi:10.1016/j.laa.2017.02.037
[27] Zhou, Q.; Wong, DI; 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
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.