Some Properties of Chain and Threshold Graphs

Jump To References Section

Authors

  • Shahistha Hanif
     Department of Mathematics, Manipal Institute of Technology, Manipal Academy of Higher Education, Manipal, Karnataka-576104 ,IN
  • K. Arathi Bhat
     Department of Mathematics, Manipal Institute of Technology, Manipal Academy of Higher Education, Manipal, Karnataka-576104 ,IN
  • Sudhakara G.
     Department of Mathematics, Manipal Institute of Technology, Manipal Academy of Higher Education, Manipal, Karnataka-576104 ,IN

DOI:

https://doi.org/10.18311/jims/2023/27696

Keywords:

Chain, Bipartite Graphs, Rank, Determinant, Permanent.
05C76, 05C40, 05C50

Abstract

Chain graphs and threshold graphs are special classes of graphs which have maximum spectral radius among bipartite graphs and connected graphs with given order and size, respectively. In this article, we focus on some of linear algebraic tools like rank, determinant, and permanent related to the adjacency matrix of these types of graphs. We derive results relating the rank and number of edges. We also characterize chain/threshold graphs with nonzero determinant and permanent.

Downloads

Download data is not yet available.

Metrics

Metrics Loading ...

Downloads

Published

2023-03-24

How to Cite

Hanif, S., Bhat, K. A., & G., S. (2023). Some Properties of Chain and Threshold Graphs. The Journal of the Indian Mathematical Society, 90(1-2), 75–84. https://doi.org/10.18311/jims/2023/27696

Issue

Volume 90, Issue 1-2, January-June 2023

Section

Articles

License

Copyright (c) 2023 Shahistha Hanif, K. Arathi Bhat, Sudhakara G.

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Crossref
Scopus
Google Scholar
Europe PMC
Received 2021-04-26
Accepted 2022-01-23
Published 2023-03-24

 

References

A. Alazemi, M. Andelic, T. Koledin and Z. Stanic, Eigenvalue-free intervals of distance matrices of threshold and chain graphs, Linear Multilinear Algebra, 69(16) (2021), 2959–2975. DOI: https://doi.org/10.1080/03081087.2019.1701624

M. Andelic, C. M. D. Fonseca, S. K. Simic and D. V. Tosic, On bounds for the index of double nested graphs, Linear Algebra Appl., 435(10) (2011), 2475–2490. DOI: https://doi.org/10.1016/j.laa.2010.12.017

M. Andelic, C. M. D. Fonseca, S. K. Simic and D. V. Tosic, Connected graphs of fixed order and size with maximal Q-index: Some spectral bounds, Discrete Appl. Math., 160(4) (2012), 448–459. DOI: https://doi.org/10.1016/j.dam.2011.11.001

M. Andelic, E. Ghorbani and S. K. Simic, Vertex types in threshold and chain graphs, Discrete Appl. Math., 269 (2019), 159–168. DOI: https://doi.org/10.1016/j.dam.2019.02.040

M. Andelic, D. Zhibin, C. M. D. Fonseca and S. K. Simic, Tridiagonal matrices and spectral properties of some graph classes, Czech Math. J., 70 (2020), 1125-1138. DOI: https://doi.org/10.21136/CMJ.2020.0182-19

R. B. Bapat, Graphs and Matrices, Hindustan Book Agency, New Delhi, 2010. DOI: https://doi.org/10.1007/978-1-84882-981-7

F. K. Bell, D. Cvetkovic, P. Rowlinson and S. K. Simic, Graphs for which the least Eigen value is minimal, Linear Algebra Appl., 429 (2008), 2168–2179. DOI: https://doi.org/10.1016/j.laa.2008.06.018

K. A. Bhat, Shahistha and Sudhakara G., Metric dimension and its variations of chain graphs, Proc. Jangjeon Math. Soc., 24(3) (2021), 309–321.

A. Bhattacharya, S. Friedland and U. N. Peled, On the first eigen values of bipartite graphs, Electron. J. Combin., 15 (2008), DOI: 10.37236/868. DOI: https://doi.org/10.37236/868

E. Ghorbani, Some spectral properties of chain graphs, arXiv:1703.03581v1[math.CO], (2017).

E. Ghorbani, Eigenvalue–free interval for threshold graphs, Linear Algebra Appl., 583, (2019) 300–305. DOI: https://doi.org/10.1016/j.laa.2019.08.028

J. Lazzarin, F. Tura, No threshold graphs are cospectral, arXiv:1806.07358v1 [math.CO] (2018).

Shahistha H., K. A. Bhat and Sudhakara G., Wiener index of chain graphs, IAENG Int. J. Appl. Math., 50(4) (2020), 783–790.

F. Tura, Counting Spanning trees in Double nested graphs, arXiv:1605.04760v1 [math.CO], (2016).