|
|
双圈图的零强迫数与一般位置数
|
Abstract:
设F(G)是图G的零强迫数，gp(G)是图G的一般位置数。注意，gp(G)≥F(T)+1对所有树T都成立。Hua等人在中证明了此结果可以扩展到块图，并证明了对于连通单圈图G，gp(G)≥F(T)。在本文中，我们刻画了使得gp(G)≥F(T)成立的双圈图的结构。
Let F(G) be the zero forcing number of G and gp(G) be the general position number of G. Note that gp(G)≥F(T)+1 holds for any tree T. Hua et al. showed that this result can be extended to block graphs, and showed that gp(G)≥F(T) for connected unicyclic graphs. In this paper, we charac-terize the structure of bicyclic graphs satisfying gp(G)≥F(T).
| [1] | AIM Minimum Rank—Special Graphs Work Group (Barioli, F., Barrett, W., Butler, S., Cioaba, S.M., Cvetkovic, D., Fallat, S.M., Godsil, C., Haemers, W., Hogben, L., Mikkelson, R., Narayan, S., Pryporova, O., Sciriha, I., So, W., Stevanovic, D., van der Holst, H., Vander, M.K. and Wangsness, A.) (2008) Zero Forcing Sets and the Minimum Rank of Graphs. Linear Algebra and Its Applications, 428, 1628-1648. https://doi.org/10.1016/j.laa.2007.10.009 |
| [2] | Barioli, F., Barrett, W., Fallat ,S.M., et al. (2010) Zero Forcing Parameters and Minimum Rank Problems. Linear Algebra and Its Applications, 433, 401-411. https://doi.org/10.1016/j.laa.2010.03.008 |
| [3] | Edholm, C. J., Hogben, L., Huynh, M., et al. (2012) Vertex and Edge Spread of Zero Forcing Number, Maximum Nullity, and Minimum Rank of a Graph. Linear Algebra and Its Applications, 436, 4352-4372.
https://doi.org/10.1016/j.laa.2010.10.015 |
| [4] | Hogben, L. (2010) Minimum Rank Problems. Linear Algebra and Its Ap-plications, 432, 1961-1974.
https://doi.org/10.1016/j.laa.2009.05.003 |
| [5] | Montazeri, Z. and Soltankhah, N. (2020) On the Relationship between the Zero Forcing Number and Path Cover Number for Some Graphs. Bulletin of the Iranian Mathematical Society, 46, 767-776.
https://doi.org/10.1007/s41980-019-00290-8 |
| [6] | Davila, R. and Kenter, F. (2015) Bounds for the Zero-Forcing Number of Graphs with Large Girth. Theory and Applications of Graphs, 2, Article 1. https://doi.org/10.20429/tag.2015.020201 |
| [7] | Gentner, M., Penso, L.D., Rautenbach, D. and Souza, U.S. (2016) Ex-tremal Values and Bounds for the Zero Forcing Number. Discrete Applied Mathematics, 214, 196-200. https://doi.org/10.1016/j.dam.2016.06.004 |
| [8] | Lu, L., Wu, B. and Tang, Z. (2016) Proof of a Conjecture on the Zero Forcing Number of a Graph. Discrete Applied Mathematics, 213, 233-237. https://doi.org/10.1016/j.dam.2016.05.009 |
| [9] | Zhang, W., Wang, J., Wang, W. and Ji, S.J. (2022) On the Zero Forcing Number and Spectral Radius of Graphs. The Electronic Journal of Combinatorics, 29, Article No. P1.33. https://doi.org/10.37236/10638 |
| [10] | Eroh, L., Kang, C.X. and Yi, E. (2017) A Comparison between the Metric Dimension and Zero Forcing Number of Trees and Unicyclic Graphs. Acta Mathematica Sinica, English Series, 33, 731-747.
https://doi.org/10.1007/s10114-017-4699-4 |
| [11] | Barioli, F., Barrett, W., Fallat, S.M., et al. (2013) Parameters Related to Tree-Width, Zero Forcing, and Maximum Nullity of a Graph. Journal of Graph Theory, 72, 146-177. https://doi.org/10.1002/jgt.21637 |
| [12] | Anand, B.S., Sv, U.C., Changat M., et al. (2019) Characterization of General Posi-tion Sets and Its Applications to Cographs and Bipartite Graphs. Applied Mathematics and Computation, 359, 84-89.
https://doi.org/10.1016/j.amc.2019.04.064 |
| [13] | Klav？ar, S., Tan, E. and Tian, J. (2023) Extremal Edge General Position Sets in Some Graphs. (Preprint) |
| [14] | Hua, H., Hua, X. and Klav？ar, S. (2021) Zero Forcing Number Versus General Position Number in Tree-Like Graphs. (Preprint) |
