Matching number in relation with maximal-minimal nullity conditions and cyclomatic number by coefficient relations
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Let G be a simple graph. So called K2 deletion process was recently introduced by Wang. A subgraph G0 of G that is obtained as a result of some K2 deletion process will be called as a crucial subgroup. Let (G) and (G0) be the matching numbers of G and G0, respectively. In this study, we study the relation between (G), (G0) and the coe cients of the characteristic polynomials of G and G0. Several results are obtained on these notions. Moreover, conservation of maximal and minimal nullity conditions after applying K2 deletion process are studied. As a result of this, when G satis es the maximal or minimal nullity condition, we obtain the conditions for the equality c(G) = c(G0) where c(G) and c(G0) denote the cyclomatic numbers of G and G0, respectively. Finally, for some graphs, we state (G) in terms of c(G), c(G0), n(G), n(G0) and the coe cients of the characteristic polynomials of G and G0 where n(G), n(G0) are the numbers of vertices of G and G0, respectively.
Abstract
Let G be a simple graph. So called K2 deletion process was recently introduced by Wang. A subgraph G0 of G that is obtained as a result of some K2 deletion process will be called as a crucial subgroup. Let (G) and (G0) be the matching numbers of G and G0, respectively. In this study, we study the relation between (G), (G0) and the coe cients of the characteristic polynomials of G and G0. Several results are obtained on these notions. Moreover, conservation of maximal and minimal nullity conditions after applying K2 deletion process are studied. As a result of this, when G satis es the maximal or minimal nullity condition, we obtain the conditions for the equality c(G) = c(G0) where c(G) and c(G0) denote the cyclomatic numbers of G and G0, respectively. Finally, for some graphs, we state (G) in terms of c(G), c(G0), n(G), n(G0) and the coe cients of the characteristic polynomials of G and G0 where n(G), n(G0) are the numbers of vertices of G and G0, respectively.
참고문헌 (32)
- M. Aaghabali, "Order of the Largest Sachs Subgraphs in Graphs", Linear and Multilinear Algebra, 65(1), pp.204~209 (2017)
- F. Ashraf, "A Note on Graphs with Zero Nullity", MATCH Communications in Mathematical and in Computer Chemistry, 60, pp.15~19 (2008)
- R. B. Bapat, "Graphs and Matrices" (2014), Springer
- N. Biggs, "Algebraic Graph Theory" (1974), Cambridge University Press
- G. J. Chang, "A Characterization of Graphs with Rank 4", Linear Algebra and its Applications, 434, pp.1793~1798 (2011)
- G. J. Chang, "A Characterization of Graphs with Rank 5", Linear Algebra and its Applications, 436, pp.4241~4250 (2012)
- B. Chen, "On the Nullity of Tricyclic Graphs", Linear Algebra and its Applications, 434, pp.1799~1810 (2011)
- L. Collatz, U. Sinogowitz, "Spektren endlicher Grafen", Abhandlungen aus dem Mathematischen Seminar der Universitat Hamburg, 21, pp.63~77 (1957)
- B. Colman, "Elementary Linear Algebra with Applications" (2007), Prentice Hall
- D. M. Cvetkovic, "Spectra of Graphs-Theory and Applications" (1980), Academic Press
- S. Delen, "A New Graph Invariant", Turkish Journal of Analysis and Number Theory, 6(1), pp.30~33 (2018)
- S. Delen, "Extremal Problems on Components and Loops in Graphs", Acta Mathematica Sinica, English Series, 35(2), pp.161~171 (2019)
- Y. Z. Fan, "On the Nullity of Bipartite Graphs", Linear Algebra and its Applications, 430, pp.2943~2949 (2009)
- S. Fiorini, "Trees with Maximum Nullity", Linear Algebra and its Applications, 397, pp.245~251 (2005)
- C. Godsil, "Algebraic Graph Theory" (2001), Springer-Verlag
- J. M. Guo, "On the Nullity and the Matching Number of Unicyclic Graphs", Linear Algebra and its Applications, 431, pp.1293~1301 (2009)
- I. Gutman, "On the Nullity of Line Graphs of Trees", Discrete Mathematics, 232, pp.35~45 (2001)
- S. Hu, "On the Nullity of Bicyclic Graphs", Linear Algebra and its Applications, 429, pp.1387~1391 (2008)
- E. Hückel, "Grundzüge der Theorie ungesäutigter und aromatischer Verbindungen" (1940), Verlag Chemie
- X. Ma, "Nullity of a Graph in terms of the Dimension of Cycle Space and the Number of Pendant Vertices", Discrete Mathematics, 339, pp.1574~1582 (2016)
- G. R. Omidi, "On the Nullity of Bipartite Graphs", Graphs and Combinatorics, 25, pp.111~114 (2009)
- S. Rula, "The extremal graphs with respect to their nullity", Journal of Inequalities and Applications, 71 (2016)
- I. Sciriha, "Nut Graphs: Maximally Extending Cores", Utilitas Mathematica, 54, pp.257~272 (1998)
- I. Sciriha, "On Singular Line Graphs of Trees", Congressus Numerantium, 135, pp.73~91 (1998)
- I. Sciriha, "Combinatorics, Graph Theory and Algorithms, vol 2", pp.769~778 (1999)
- Y. Song, "A characterization of graphs G with nullity |V(G)|-2m(G)+2c(G)", Linear Algebra and its Applications, 465, pp.363~375 (2015)
- B. S. Tam, "Nullities of Graphs with Given Order, Matching Number and Cyclomatic Number Revisited", Linear Algebra and its Applications, 535, pp.105~140 (2017)
- N. Trinajstic, "Chemical Graph Theory" (1992), CRC Press
- L. Wang, "Characterization of Graphs with Given Order, Given Size, Given Matching Number that Minimize Nullity", Discrete Mathematics, 339, pp.1574~1582 (2016)
- L. Wang, "Bounds for the Matching Number, the Edge Chromatic Number and the Independence Number of a Graph in terms of Rank", Discrete Mathematics, 166, pp.276~281 (2014)
- D. Wong, "A Characterization of Long Graphs of Arbitrary Rank", Linear Algebra and its Applications, 438, pp.1347~1355 (2013)
- T. Xuezhong, "On the Nullity of Unicyclic Graphs", Linear Algebra and its Applications, 408, pp.212~220 (2005)