The Journal of the Indian Mathematical Society

Open Access Open Access  Restricted Access Subscription Access
Open Access Open Access Open Access  Restricted Access Restricted Access Subscription Access

Some Properties of Chain and Threshold Graphs


Affiliations
1 Department of Mathematics, Manipal Institute of Technology, Manipal Academy of Higher Education, Manipal, Karnataka 576104, India
     

   Subscribe/Renew Journal


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.

Keywords

Chain, Bipartite Graphs, Rank, Determinant, Permanent.
Subscription Login to verify subscription
User
Notifications
Font Size


  • 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.

  • 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.

  • 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.

  • M. Andelic, E. Ghorbani and S. K. Simic, Vertex types in threshold and chain graphs, Discrete Appl. Math., 269 (2019), 159–168.

  • 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.

  • R. B. Bapat, Graphs and Matrices, Hindustan Book Agency, New Delhi, 2010.

  • 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.

  • 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.

  • 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.

  • 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).


Abstract Views: 224

PDF Views: 1




  • Some Properties of Chain and Threshold Graphs

Abstract Views: 224  |  PDF Views: 1

Authors

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

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.

Keywords


Chain, Bipartite Graphs, Rank, Determinant, Permanent.

References