×

Relationship between the rank and the matching number of a graph. (English) Zbl 1428.05190

Summary: Given a simple graph \(G\), let \(A(G)\) be its adjacency matrix and \(\alpha'(G)\) be its matching number. The rank of \(G\), written as \(r(G)\), refers to the rank of \(A(G)\). In this paper, some relations between the rank and the matching number of a graph are studied. Firstly, it is proved that \(- 2 d(G) \leqslant r(G) - 2 \alpha^\prime(G) \leqslant N_o\), where \(d(G)\) and \(N_o\) are, respectively, the dimension of cycle space and the number of odd cycles of \(G\). Secondly, sharp lower bounds on both \(r(G) - \alpha^\prime(G)\) and \(r(G)/ \alpha '(G)\) are determined. All the corresponding extremal graphs are characterized, respectively.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C35 Extremal problems in graph theory

Software:

AutoGraphiX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aouchiche, M., Comparaison automatisée d’invariants en théorie des graphes Ph.D. thesis (2006), École Polytechnique de Montréal
[2] Aouchiche, M.; Bonnefoy, J. M.; Fidahoussen, A.; Caporossi, G.; Hansen, P.; Hiesse, L.; Lacher, J.; Monhait, A., Variable neighborhood search for extremal graphs. 14. the AutoGraphiX 2 system, (Liberti, L.; Maculan, N., Global Optimization: From Theory to Implementation (2005), Springer: Springer New York) · Zbl 1100.90052
[3] Bevis, J. H.; Blount, K. K.; Davis, G. J., The rank of a graph after vertex addition, Linear Algebra Appl., 265, 55-69 (1997) · Zbl 0884.05061
[4] Caporossi, G.; Hansen, P., Variable neighborhood search for extremal graphs. 1. the AutoGraphiX system, Discret. Math., 212, 29-44 (2000) · Zbl 0947.90130
[5] Caporossi, G.; Hansen, P., Variable neighborhood search for extremal graphs. 5. three ways to automate finding conjectures, Discret. Math., 276, 81-94 (2004) · Zbl 1031.05068
[6] Chang, G. J.; Huang, L. H.; Yeh, H. G., A characterization of graphs with rank 4, Linear Algebra Appl., 434, 1793-1798 (2011) · Zbl 1216.05071
[7] Chang, G. J.; Huang, L. H.; Yeh, H. G., A characterization of graphs with rank 5, Linear Algebra Appl., 436, 4241-4250 (2012) · Zbl 1241.05062
[8] Chen, L.; Tian, F. L., Skew-rank of an oriented graph with edge-disjoint cycles, Linear Multilinear Algebra, 64, 6, 1197-1206 (2016) · Zbl 1338.05098
[9] Chen, Y. H.; Liang, J.; Zhu, D. X., The characterization of tangent bicycle graph with nullity one, Int. J. Appl. Math. Stat., 34, 10-19 (2013)
[10] Cheng, B.; Liu, B. L., On the nullity of graphs, electron, J. Linear Algebra., 16, 60-67 (2007) · Zbl 1142.05336
[11] Cheng, B.; Liu, B. L., On the nullity of tricyclic graphs, Linear Algebra Appl., 434, 1799-1810 (2011) · Zbl 1216.05072
[12] Cvetković, D.; Doob, M.; Sachs, H., Spectra of Graphs (1995), Johann Ambrosius Barth: Johann Ambrosius Barth Heidelberg · Zbl 0824.05046
[13] Fan, Y. Z.; Qian, K. S., On the nullity of bipartite graphs, Linear Algebra Appl., 430, 2943-2949 (2009) · Zbl 1169.05346
[14] Godsil, C. D.; Royle, G. F., Chromatic number and the 2-rank of a graph, J. Combin. Theory Ser. B, 81, 142-149 (2001) · Zbl 1026.05046
[15] Gong, S. C.; Fan, Y. Z.; Yin, Z. X., On the nullity of graphs with pendant trees, Linear Algebra Appl., 433, 1374-1380 (2010) · Zbl 1194.05086
[16] Gong, S. C.; Xu, G. H., On the nullity of a graph with cut-points, Linear Algebra Appl., 436, 135-142 (2012) · Zbl 1243.05147
[17] Guo, J. M.; Yan, W. G.; Yeh, Y. N., On the nullity and the matching number of unicyclic graphs, Linear Algebra Appl., 431, 1293-1301 (2009) · Zbl 1238.05160
[18] Hu, S. B.; Tan, X. Z.; Liu, B. L., On the nullity of bicyclic graphs, Linear Algebra Appl., 429, 1387-1391 (2008) · Zbl 1144.05319
[19] Huang, J.; Li, S. C.; 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
[20] Luo, W. J.; Huang, J.; Li, S. C., 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
[21] Jiang, Q.; Chen, S. B., The nullity of 2-connected tricyclic graphs, Int. J. Contemp. Math. Sci., 6, 571-575 (2011) · Zbl 1231.05168
[22] Li, S. C., On the nullity of graphs with pendent vertices, Linear Algebra Appl., 429, 1619-1628 (2008) · Zbl 1144.05321
[23] Li, X. L.; Yu, G. H., The skew-rank of oriented graphs, Sci. Sin. Math., 45, 93-104 (2015) · Zbl 1488.05222
[24] Lu, Y.; Wang, L. G.; Zhou, Q., 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
[25] Ma, X. B.; Wong, D. Y., The nullity of \(k\)-cyclic graphs of ∞-type, Linear Multilinear Algebra, 63, 2200-2211 (2015) · Zbl 1328.05107
[26] Ma, X. B.; Wong, D. Y.; Tian, F. L., Nullity of a graph in terms of the dimension of cycle space and the number of pendant vertices, Discret. Appl. Math., 215, 171-176 (2016) · Zbl 1346.05144
[27] Ma, X. B.; Wong, D. Y.; Tian, F. L., Skew-rank of an oriented graph in terms of matching number, Linear Algebra Appl., 495, 242-255 (2016) · Zbl 1331.05181
[28] Rula, S.; Chang, A.; Zheng, Y. R., The extremal graphs with respect to their nullity, J. Inequal. Appl., 2016, 71 (2016) · Zbl 1331.05148
[29] Song, Y. Z.; Song, X. Q.; Tam, B. S., A characterization of graphs \(g\) with nullity \(| v(g) | - 2 m(g) + 2 c(g)\), Linear Algebra Appl., 465, 363-375 (2015) · Zbl 1303.05158
[30] Song, Y. Z.; Song, X. Q.; Zhang, M. C., An upper bound for the nullity of a bipartite graph in terms of its maximum degree, Linear Multilinear Algebra, 64, 1107-1112 (2016) · Zbl 1335.05115
[31] Tan, X. Z.; Liu, B. L., The nullity of \((k - 1)\)-cyclic graphs, Linear Algebra Appl., 438, 3144-3153 (2013) · Zbl 1259.05104
[32] Tan, X. Z.; Tan, X. G., The rank of multicyclic graphs, Chin. Ann. Math. Ser. A, 35, 533-542 (2014) · Zbl 1324.05119
[33] Wang, L., Characterization of graphs with given order, given size and given matching number that minimize nullity, Discret. Math., 339, 1574-1582 (2016) · Zbl 1333.05247
[34] Wang, L.; Wong, D. Y., Bounds for the matching number, the edge chromatic number and the independence number of a graph in terms of rank, Discret. Appl. Math., 166, 276-281 (2014) · Zbl 1283.05226
[35] Wang, Q. W.; Yu, G. H., On the maximal nullity of unicyclic graphs with fixed girth, Util. Math., 86, 217-223 (2011) · Zbl 1264.05084
[36] Wong, D. Y.; Ma, X. B.; Tian, F. L., Relation between the skew-rank of an oriented graph and the rank of its underlying graph, Eur. J. Comb., 54, 76-86 (2016) · Zbl 1331.05097
[37] Zhou, J.; Sun, L. Z.; Yao, H. M.; Bu, C. J., On the nullity of connected graphs with least eigenvalue at least \(- 2\), Appl. Anal. Discret. Math., 7, 250-261 (2013) · Zbl 1313.05260
[38] Zhu, W.; Wu, T. Z.; Hu, S. B., A note on the nullity of unicyclic graphs, J. Math. Res. Expos., 30, 817-824 (2010) · Zbl 1240.05210
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.